CSCE 5214: Software

Development for Artificial

Intelligence

Chapter 6: Prolog Programming Language

Outline

• 6.1. Introduction
• 6.2. Logic Programming in Prolog

2
6.1. Introduction

• Logic (declarative) programming emerged as a distinct paradigm in the 1970s.

• Logic programming is distinct from the other paradigms because it requires the programmer to
• declare the goals of the computation, rather than the detailed algorithm by which these
• goals can be achieved.
• The goals are expressed as a collection of statements, or rules about the outcomes and
constraints of the computation.
• For this reason, logic programming is sometimes called rule-based programming.
• Applications of declarative programming fall into two major domains: artificial intelligence and
database information retrieval.
• Across the artificial intelligence area, Prolog has been influential [1].

• [1] Ivan Bratko, Prolog Programming for Artificial Intelligence, Pearson, Fourth Edition, New York, 2012.

3
6.1. Introduction

• Two interesting and distinguishing features of logic programs are nondeterminism and
backtracking.
• A nondeterministic logic program may find several solutions to a problem rather than just one,
as would be the norm in other programming domains.
• Further, the backtracking mechanism which enables nondeterminism is built into the Prolog
interpreter and therefore is implicit in all Prolog programs.
• A logic program expresses the specifications for problem solutions using expressions in
mathematical logic.
• This style evolved out of the needs of researchers in natural language processing and
automatic theorem proving.
• Conventional programming languages are not particularly well suited to these researchers'
needs.
4
6.1. Introduction

• Prolog is a programming language for symbolic, non-numeric computation.

• It is specially well suited for solving problems that involve objects and relations between
objects.

• Objects and relations between objects are created using File/New path of the Prolog menu and
saved as knowledge base files with extension pl.
• Queries are written in workspace of Prolog.
• To obtain Prolog answer to user query, knowledge base file should be connected to Prolog by
File/Consult of the Prolog menu.

5
6.2. Logic Programming in Prolog

• Prolog is the principal language used in logic programming.

• The development of Prolog is based on two powerful principles discovered by Robinson
[Robinson, 1965] called resolution and unification.
• Prolog itself emerged in 1970, out of the work of Colmerauer, Rousseau, and Kowalski
[Kowalski and Kuehner, 1970] and has been the major logic programming language to the
present day.
• Applications of logic programming are widespread in the areas of
• Natural Language Processing,
• Automatic Reasoning and Theorem Proving,

6
6.2. Logic Programming in Prolog

• Expert Systems,
• Intelligent Database Retrieval,
• Specification Language,
• Machine Learning,
• Robot Planning,
• Automation System,
• Problem Solving.

7
6.2. Logic Programming in Prolog

• Prolog or PROgramming in LOGics is a logical and declarative programming language.

• It is one major example of the fourth-generation language that supports the declarative
programming paradigm.
• This is particularly suitable for programs that involve symbolic or non-numeric computation.
• This is the main reason to use Prolog as the programming language in Artificial Intelligence,
where symbol manipulation and inference manipulation are the fundamental tasks.

• Prolog Program Elements

• Prolog programs are made from terms, which can be constants, variables, or structures.
• A constant is either an atom (like the, zebra, 'Bob', and ' . ‘) or a nonnegative integer (like 24 ).
• A variable is a series of letters (A- Z, a- z) that must begin with a capital letter (like Bob).
• A structure is a predicate with zero or more arguments, written in functional notation.

8
6.2. Logic Programming in Prolog

• In Prolog, we need not mention the way how one problem can be solved, we just need to
mention what the problem is, so that Prolog automatically solves it.
• However, in Prolog we are supposed to give clues as the solution method.

• Knowledge Base − This is one of the fundamental parts of logic programming.

• Facts, Rules and Queries − These are the building blocks of logic programming.
• Here, we will discuss about the essential building blocks of logic programming.
• These building blocks are Facts, Rules and the Queries.

9
6.2. Logic Programming in Prolog

• Facts
• We can define fact as an explicit relationship between objects, and properties these objects
might have.
• So, facts are unconditionally true in nature. Suppose we have some facts as given below −
• Tom is a cat.
• Kunal loves to eat Pasta.
• Hair is black.
• Nawaz loves to play games.
• Pratyusha is lazy.
• So, these are some facts, that are unconditionally true.
• These are statements that we consider as true.

10
6.2. Logic Programming in Prolog

• Following are some guidelines to write facts −

• Names of properties/relationships begin with lower case letters.
• The relationship name appears as the first term.
• Objects appear as comma-separated arguments within parentheses.
• A period "." must end a fact.
• Objects also begin with lower case letters. They also can begin with digits (like 1234) and can
be strings of characters enclosed in quotes, e.g.,
• color(pink, red).
• phoneno(agnibha, 1122334455).
• which are also called predicates or clauses.

11
6.2. Logic Programming in Prolog

• Syntax
• The syntax for facts is as follows −

• Example 6.1.
• Following is an example of the above concept −

12
6.2. Logic Programming in Prolog

• Rules
• We can define rule as an implicit relationship between objects.
• Facts are conditionally true.
• When one associated condition is true, then the predicate is also true.
• Suppose we have some rules as given below −
• Lili is happy if she dances.
• Tom is hungry if he is searching for food.
• Jack and Bili are friends if both of them love to play cricket.
• He will go to play if school is closed, and he is free.

13
6.2. Logic Programming in Prolog

• These are some rules that are conditionally true, so when the right-hand side is true, then the
left-hand side is also true.
• The symbol ( :- ) that is used in this relation is pronounced as if or is implied by.
• This is also known as neck symbol, the left-hand side of this symbol is called the Head, and
right-hand side is called Body.
• We can use comma (,) which is known as conjunction, and we can also use semicolon, that is
known as disjunction.

14
6.2. Logic Programming in Prolog

• Syntax

15
6.2. Logic Programming in Prolog

• Example 6.2.

16
6.2. Logic Programming in Prolog

• Queries
• Queries are some questions on the relationships between objects and object properties.
• Question can be anything, as given below −
• Is Tom a dog?
• Does Brian love to eat fruits?
• Is Ann happy?
• Will Mark go to play?

• According to these queries, logic programming language can find the answer and return it.

17
6.2. Logic Programming in Prolog

• Knowledge Base in Logic Programming

• As it was already mentioned, there are three main components in logic programming − Facts,
Rules and Queries.
• Among these three if we collect the facts and rules, then that forms a knowledge base.
• We can say that the knowledge base is a collection of facts and rules.
• Now, let us see how to write some knowledge bases.
• Suppose we have our very first knowledge base called KB1.
• Here in the KB1, we have some facts.
• The facts are used to state things, that are unconditionally true of the domain of interest.

18
6.2. Logic Programming in Prolog

• Knowledge Base 1
• Suppose we have some knowledge, that Ann, Mary, and Kathryn are three girls, among them,
Ann can cook.
• Let us try to write these facts in a more generic way as shown below −

• Note − Here we have written the name in lowercase letters, because in Prolog, a string starting
with uppercase letter indicates a variable.

19
6.2. Logic Programming in Prolog

• Now we can use this knowledge base by posing some queries.

• Is ann a girl?, it will reply Yes (True),
• Is jasmine a girl? then it will answer No (False), because it does not know who jasmine is.
• Our next question is Can Ann cook?, it will say Yes,
• but if we ask the same question for Kathryn, it will say No.

20
6.2. Logic Programming in Prolog

• Let us see another knowledge base, where we have some rules.

• Rules contain some information that are conditionally true about the domain of interest.
Suppose our knowledge base is as follows −

• There are some facts and rules given above.

• The first two are facts, but the rest are rules.
• As we know that Ananya sings a song, this implies she also listens to music.
• So, if we ask Does Ananya listen to music?, the answer will be True.
21
6.2. Logic Programming in Prolog

• Similarly, is Rohit happy?, this will also be true because he listens to music.
• But if our question is does Ananya play guitar?, then according to the knowledge base, it will
say No.
• These are some examples of queries based on this Knowledge base.

22
6.2. Logic Programming in Prolog

• The facts and rules of Knowledge Base 3 are as follows −

• Suppose we want to see the members who can cook, we can use one variable in our query.
• The variables should start with uppercase letters.
• In the result, it will show one by one.
• If we press enter, then it will come out, otherwise if we press semicolon (;), then it will show
the next result.
• Let us see one practical demonstration output to understand how it works.

23
6.2. Logic Programming in Prolog

• Output:

24
6.2. Logic Programming in Prolog

• Relations
• It is easy in Prolog to define a relation.
• The user can easily query the Prolog system about relations defined in the program.
• A Prolog program consists of clauses. Each clause terminates with a full stop.
• The arguments of relations can be
– Atoms: concrete objects or constants
– Variables: general objects such as X and Y
• Questions to the system consist of one or more goals.
• An answer to a question can be either positive (succeeded) or negative (failed).
• If several answers satisfy the question, then Prolog will find as many of them as desired by the
user.

25
6.2. Logic Programming in Prolog

• Relationship is one of the main features in Prolog.

• The relationships can be expressed as facts and rules.
• In Prolog programs, relations specify relationship between objects and properties of the
objects.
• Suppose, there is a statement, John has a bike, then we are actually declaring the ownership
relationship between two objects one is John and the other is bike.
• If we ask a question, Does John own a bike?, we are actually trying to find out about one
relationship.

26
6.2. Logic Programming in Prolog

• There are various kinds of relationships, of which some can be rules as well.
• A rule can find out about a relationship even if the relationship is not defined explicitly as a
fact.

• E.g., we can define a brother relationship as follows −

• Two person are brothers, if,
• They both are male.
• They have the same parent.

27
6.2. Logic Programming in Prolog

• Now consider we have the below phrases −

• These clauses can give us the answer that Mark and David are brothers, but we will get three
pairs of outputs here.
• They are: (mark, mark), (mark, david), (david, david).
• For these pairs, given conditions are true, but for the pairs (mark, mark), (david, david), they
are not actually brothers, they are the same persons.
• We have to create the clauses properly to form a relationship.

28
6.2. Logic Programming in Prolog

• The revised relationship can be as follows −

• A and B are brothers if −
• A and B, both are male
• They have same father
• They have same mother
• A and B are not same

29
6.2. Logic Programming in Prolog

• Family Relationship in Prolog

• Here we will see the family relationship.
• This is an example of complex relationship that can be formed using Prolog.
• Let us make a family tree that will be mapped into facts and rules and run some queries on
them.
• Suppose the family tree is as follows (Fig. 6.1) −

30
6.2. Logic Programming in Prolog

• Fig. 6.1. A family tree.

31
6.2. Logic Programming in Prolog

• The whole family tree of Fig. 6.1 is defined by the following Prolog program:

• This program consists of six clauses.

• Each of these clauses declares one fact about the parent relation.

32
6.2. Logic Programming in Prolog

• Facts can be written in two different ways,

• like sex of family members can be written in the following form:

• An alternative piece of program would then be:

33
6.2. Logic Programming in Prolog

• The grandparent relation can be expressed as composition of two parent relations (Fig. 6.2).

• Fig. 6.2.

34
6.2. Logic Programming in Prolog

• We can ask our program different questions and obtain corresponding answers,
• e.g.:
• ?- parent( Y, jim), parent( X, Y).
• The answer will be

• The query means find such X and Y that satisfy the following two requirements:
• parent( Y, jim) and parent( X, Y).

35
6.2. Logic Programming in Prolog

• We also can ask who are Tom’s grandchildren?

• ?- parent( tom, X), parent( X, Y).
• Prolog answers are:
• X=bob
• Y=ann;
• X=bob
• Y=pat

• Another question could be: Do Ann and Pat have a common parent?
• ?- parent( X, ann), parent( X, pat).
• The answer is
• X=Bob
36
6.2. Logic Programming in Prolog

• The next relation is offspring that can be defined similarly to parent relation,
• e.g., offspring( liz, tom).

• It can be also done based on the following statement:

• For all X and Y, Y is offspring of X if X is a parent of Y.
• The corresponding Prolog clause

• This clause can also be read as:

• For all X and Y,
• if X is a parent of Y, then Y is an offspring of X.
37
6.2. Logic Programming in Prolog

• As it was mentioned above, Prolog clauses such as

• are rules.
• There is an important difference between facts and rules.
• A fact like parent( tom, liz). is always, unconditionally, true.
• On the other hand, rules specify things that may be true if some condition is satisfied.
• The conclusion part is called the head of a clause, and the condition part is the body of a
clause.
• E.g.:

38
6.2. Logic Programming in Prolog

• If the condition parent( X, Y) is true, then a logical consequence of this is

• offspring( Y, X).

• How rules are actually used by Prolog is illustrated by the following example.
• Let us ask our program whether Liz is an offspring of Tom:
• ?- offspring( liz, tom).
• There is no fact about offsprings in the program, therefore the only way
• to consider this question is to apply the rule about offsprings.
• The rule is general in the sense that it is applicable to any objects X and Y;
• Therefore, it can also be applied to such particular objects as liz and tom.
• To apply the rule to liz and tom, Y should be substituted with liz, and X with tom.
39
6.2. Logic Programming in Prolog

• We say that the variables X and Y become instantiated (created) to:

• After the instantiation, we obtain a special case of our general rule.

• The special case is:

• The condition part has become

• parent( tom, liz).

40
6.2. Logic Programming in Prolog

• Now Prolog tries to find out whether the condition part is true.
• So, the initial goal
• offspring( liz, tom).
• has been replaced with the subgoal
• parent( tom, liz).

• This means that the conclusion part of the rule is also true, and Prolog will answer
• the question with yes/true.

41
6.2. Logic Programming in Prolog

• Let us add more family relations to our example program.

• The specification of the mother relation can be based on the following logical statement:

• This is translated into Prolog as the following rule:

• We remind that comma between two conditions indicates the conjunction (connection) of the
conditions, meaning that both conditions should be true.

42
6.2. Logic Programming in Prolog

• Relations such as parent, offspring and mother can be illustrated by diagrams shown in Fig.
6.3.

• Fig. 6.3.

• Offspring Relationship

• The grandparent relation can be, according to Fig. 6.3, written in Prolog as the following rule:

43
6.2. Logic Programming in Prolog

• Fig. 6.4 illustrates the sister relation:

• Fig. 6.4.

• The graph in Fig. 6.4 can be translated into Prolog as:

• We can now ask:

• ?- sister( ann, pat).
• The answer will be ‘yes/true', as expected.
44
6.2. Logic Programming in Prolog

• We can ask the question “Who is Pat's sister?”

• ?- sister( X, pat).
• The Prolog will answer as follows:
• X = ann

• A recursive rule definition

• Let us add one more relation to our family program, the predecessor relation.
• This relation will be defined in terms of the parent relation.
• The whole definition can be expressed with two rules.
• The first rule will define the direct (immediate) predecessors and the second rule the indirect
predecessors (Fig. 6.5).

45
6.2. Logic Programming in Prolog

• Fig. 6.5. Examples of the predecessor

• relation: (a) X is a direct predecessor
• of Y; (b) X is an indirect predecessor
• of Z. (a)
•

• (b)
46
6.2. Logic Programming in Prolog

• The first rule can be formulated as:

• For all X and Z,
• X is a predecessor of Y if
• X is a parent of Y.

• This is straightforwardly translated into Prolog as:

• predecessor( X, Y) := parent( X, Y).

47
6.2. Logic Programming in Prolog

• The second rule, on the other hand, is more complicated

because the chain of parents may present some problems.

• One attempt to define indirect predecessors

could be as shown in Fig. 6.6.

• Fig. 6.6a.

• According to this, the predecessor relation

would be defined by a set of clauses as follows:

48
6.2. Logic Programming in Prolog

• Fig. 6.6b.

49
6.2. Logic Programming in Prolog

• The predecessor relation

• can be also defined
• in terms of itself (Fig. 6.5b):

• A Prolog clause with the above meaning is:

50
6.2. Logic Programming in Prolog

• A complete program for the predecessor relation consisting of two rules:

• one for direct predecessors and one for indirect predecessors is given by
• predecessor( X, Z) :- parent( X, Z).
• predecessor( X, Z) :- parent( X, Y), predecessor( Y, Z).

• We can ask Prolog: Who are Pam's successors?

• That is: Who is a person that Pam is his or her predecessor?
• ?- predecessor( pam, X).
• X = bob;
• X = ann;
• X = pat;
• X =jim

51
6.2. Logic Programming in Prolog

• Let us put together all the pieces of our family program, which was extended gradually by
adding new facts and rules.

• The final form of the program is shown in Fig. 6.7.

52
6.2. Logic Programming in Prolog

• Fig. 6.7.

53
6.2. Logic Programming in Prolog

• The program in Fig. 6.7 defines several relations - parent, male, female, predecessor, etc.
• The predecessor relation, for example, is defined by two clauses.

• Comments:
/* This is a comment */
% This is also a comment

54
6.2. Logic Programming in Prolog

• How Prolog answers questions?

• To answer questions, Prolog tries to satisfy all the goals.
• To satisfy a goal means to demonstrate that the goal is true, assuming that the relations in the
program are true.
• Prolog accepts facts and rules as a set of axioms, and the user’s question as a conjectured
(supposed) theorem.
• Example:
– Axioms: All men are fallible.
Socrates is a man.
– Theorem: Socrates is fallible.
– For all X, if X is a man, then X is fallible.
fallible( X) :- man( X)
man(socrates).
• ?- fallible( socrates).

55
6.2. Logic Programming in Prolog
pam tom
• ?- predecessor( tom, pat).
predecessor( X, Z) :- parent( X, Z). % Rule pr1 bob liz
predecessor( X, Z) :- parent( X, Y), % Rule pr2
predecessor( Y, Z). ann pat

(1) parent( bob, pat) ➔ predecessor( bob, pat) jim

• From parent( bob, pat) it follows that predecessor( bob, pat), by rule pr1.
(2) parent( tom, bob) is fact.
(3) parent( tom, bob) and parent( bob, pat) ➔
predecessor( tom, pat).
• Using the fact and the derived fact parent( bob, pat) we can conclude
predecessor( tom, pat).

56
6.2. Logic Programming in Prolog
pam tom
• ?- predecessor( tom, pat).
predecessor( X, Z) :- parent( X, Z). % Rule pr1 bob liz
predecessor( X, Z) :- parent( X, Y), % Rule pr2
predecessor( Y, Z).
ann pat
– How does the Prolog system find a proof sequence?
• Prolog first tries that clause which appears first in the program. (rule
pr1) jim
• Now, X= tom, Z = pat.
• The goal predecessor( tom, pat) is then replaced by parent( tom, pat).
• There is no clause in the program whose head matches the goal
parent( tom, pat).
• Prolog backtracks to the original goal to try an alternative way (rule pr2).

57
6.2. Logic Programming in Prolog

pam tom
• ?- predecessor( tom, pat).
predecessor( X, Z) :- parent( X, Z). % Rule pr1
predecessor( X, Z) :- parent( X, Y), % Rule pr2
predecessor( Y, Z). bob liz

• Apply rule pr2, X = tom, Z = pat, but Y is not instantiated yet.

• The top goal predecessor( tom, pat) is replaced by two goals: ann pat
– parent( tom, Y)
– predecessor( Y, pat)
• The first goal matches one of the facts. (Y = bob) jim
• The remaining goal has become
predecessor( bob, pat)
• Using rule pr1, this goal can be satisfied.
– predecessor( bob, pat) :- parent( bob, pat) (Fig. 6.8).

58
6.2. Logic Programming in Prolog

• Fig. 6.8.

59
6.2. Logic Programming in Prolog

• Declarative and procedural meaning of programs

• Two levels of meaning of Prolog programs:
– The declarative meaning
• concerned only with the relations defined by the program
• determines what will be the output of the program
• The programmer should concentrate mainly on the declarative meaning and avoid
being distracted by the executional details.
– The procedural meaning
• determines how this output is obtained
• determines how the relations are evaluated by the Prolog system

60