IT 5433

Logic Programming and Deductive Reasoning

Prof. N. G. J. Dias
Senior Professor
Department of Computer Systems Engineering,
Faculty of Computing and Technology,
University of Kelaniya,
Kelaniya
Learning outcomes
At the end of this course module student should be able to
• demonstrate skills in writing programs using Prolog.
- SWI Prolog
• apply programming concepts to solve real world problems in Artificial Intelligence.

3 May 2025 NGJD@FCT-UoK 2

 References
• Bratko, Ivan, (2012), Prolog Programming for Artificial Intelligence, 4th
Edition, Pearson Range Extension Paul.
• Sterling, L & Shapiro, E., (1994), The Art of Prolog: Advanced Programming
Techniques, 2nd Edition, The MIT Press.
• Kaushik Saroj, (2008), Logic and Prolog Programming, 1st Edition, New Age
International Publishers, India.
• Russel, S. and Norvig, P., (2009), Artificial Intelligence – A Modern Approach,
3rd Edition, Prentice-Hall of India Private Limited.
• Shinghal, R., (1992), Formal Concepts in Artificial Intelligence, 1st Edition,
Chapman & Hall.
• Luger, G. F.& Stubblefield, W. A., (2008), Artificial intelligence, 6th Edition,
The Benjamin/ Cummings Publishing Company, Inc.
3 May 2025 NGJD@FCT-UoK 3
 • Mc Donald C, Yazdani M., (1990), Prolog Programming, 1st Edition, Blackwell
Scientific Publications.
• Max Bramer, (2013), Logic Programming with Prolog, 2nd Edition, Springer.

3 May 2025 NGJD@FCT-UoK 4

Part 1 - Logic Programming
 Chapter 1

Introduction to Prolog

3 May 2025 NGJD@FCT-UoK 6

Learning outcomes
At the end of this chapter student should be able to
• Understand many important concepts and basic mechanisms of Prolog through an
example program.
• Download and install a suitable Prolog system on your computer.
• Create, save and execute a Prolog program.
• Distinguish between declarative and procedural meanings of Prolog.

3 May 2025 NGJD@FCT-UoK 7

1.1 Introduction to Logic Programming

• This lesson discuss how Logic has been used to introduce a new paradigm called,
Logic Programming.
• Here we learn about Prolog as a Logic Programming language.
• At this point, it is worth mentioning that Prolog has been recognized as the major
language for Programming in Artificial Intelligence (AI).
• As such thousands of Expert Systems and Natural Language Processing Systems
have been implemented using Prolog.
• This lesson covers fundamentals of Prolog and writing of simple programs in
Prolog.

3 May 2025 NGJD@FCT-UoK 8

1.2 What is Prolog?

• Prolog stands for programming in logic - an idea that emerged in the early 1970s to
use logic as a programming language.
• Prolog is a programming language based on the system of predicate logic
(predicate calculus).
• So it is often described as a logic programming language.
• Prolog is a programming language centred around a small set of basic built-in
mechanisms, including pattern matching, tree-based data structuring and
automatic backtracking.
• This small set constitutes a surprisingly powerful and flexible programming
framework.
• Prolog is a programming language for symbolic, non-numeric computation.
• Prolog is especially well suited for problems that involve objects - in particular,
structured objects - and relations between them.
3 May 2025 NGJD@FCT-UoK 9
1.3 An example program: Defining family relations by Facts
• Consider the following set of facts about a family:
Tom is a parent of Bob.
Pam is a parent of Bob.
Tom is a parent of Liz.
Bob is a parent of Ann.
Bob is a parent of Pat.
Pat is a parent of Jim.

The figure on the right depicts the above family relations:

3 May 2025 NGJD@FCT-UoK 10

• Now consider the first fact about the family.
Tom is a parent of Bob.
This fact gives a relationship between objects Tom and Bob.
In Prolog this fact can be written as
parent(tom,bob).
• Here we choose parent as the name of a 2-place relation (2- place predicate); tom
and bob are as its arguments.
Hence, the 2-place predicate,
parent(p,c) is true if and only if p is a parent of c.

3 May 2025 NGJD@FCT-UoK 11

• Thus, the above set of six facts about the family is defined by the following program.
parent(tom,bob).
parent(pam,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).
Program 1.1

3 May 2025 NGJD@FCT-UoK 12

• This program consists of six clauses.
• Each of these clauses declare one fact about the parent relation.
• For example, parent(tom,bob) is a particular instance of the parent relation.
• When this program has been communicated to the Prolog system, Prolog can
posed some questions (queries) about the parent relation in response to the Prolog
prompt |?_ .

• Now consider the following queries about the parent relation.

1. The query ‘Is Bob a parent of Pat?’ can be communicated to the Prolog system
by typing in to the terminal:
|?_parent(bob,pat).
Having found this as a asserted fact in the program, Prolog will answer “yes”.

3 May 2025 NGJD@FCT-UoK 13

 2. The answer to the query
|?_parent(liz,pat).
is “no”, because the program does not mention anything about Liz being a
parent of Pat.
3. It also answer “no” to the question
|?_parent(tom,ben).
because the program has not even heard the name Ben.
4. The question ‘Who is Liz’s parent?’ can be communicated to Prolog as
|?_parent(X,liz).
Prolog’s answer will not be just “yes” or “no” this time.
Prolog tells us what is the (yet unknown) value of X such that the above
statement is true.
So the answer is
X=tom
3 May 2025 NGJD@FCT-UoK 14
 5. The question “Who are Bob’s children” can be communicated to Prolog as,
|?_parent(bob,X).
This time there is more than one possible answer.
Prolog first answer with one solution.
X=ann
and while the user responds by entering a semicolon, Prolog will continue to
printout any other solutions:
X=ann;
X=pat;
no
|?_
The “no” indicates that no other solution can be deduced from the information
available in the program.

3 May 2025 NGJD@FCT-UoK 15

 6. Consider the query “Who is parent of whom?”.
Another formulation of this question is
find X,Y such that X is a parent of Y.
This is expressed in Prolog by:
|?_parent(X,Y).
Prolog now finds all the parent-child pairs one after another.
The solutions will be displayed one at time as long as we tell Prolog we want
more solutions, until all the solutions have been found.

3 May 2025 NGJD@FCT-UoK 16

 The answers are output as
X=pam
Y=bob;
X=tom
Y=bob;
X=tom
Y=liz;
X=bob
Y=ann;
X=bob
Y=pat;
X=pat
Y=jim;
no

• We can always stop the stream of solutions by typing a period (.) instead of
semicolon (;).
3 May 2025 NGJD@FCT-UoK 17
 7. Our example program 1.1 can be asked still more complicated questions.

(i) Who is a grandparent of Jim?

As our program does not directly know the ‘grandparent’ relation this
query has to be broken down in to two steps as illustrated bellow.
grandparent

parent parent
X Y jim

(a) Who is parent_of Jim? ⇒ parent(Y,jim).

(b) Who is parent_of Y? ⇒ parent(X,Y).

3 May 2025 NGJD@FCT-UoK 18

 Hence, we have to find such X and Y that satisfy the following
requirements.
parent(Y,jim) and parent(X,Y).
This can be written in Prolog as a sequence of two simple ones,
|?_ parent(Y,jim), parent(X,Y).
The answer will be
X=bob
Y=pat;
no
|?_

3 May 2025 NGJD@FCT-UoK 19

 Since,
parent(Y,jim) ∧ parent(X,Y) and parent(X,Y) ∧ parent(Y,jim)
are logically equivalent, the query,
|?_parent(X,Y), parent(Y,jim).
will produce the same result.

3 May 2025 NGJD@FCT-UoK 20

 (ii) In a similar way we can ask: Who are Tom’s grand children?
|?_parent(tom,X), parent(X,Y)
X=bob
Y=ann;
X=bob
Y=pat ;
no
|?_

3 May 2025 NGJD@FCT-UoK 21

 (iii) Consider the query
Do Ann and Pat have a common parent?
This can be expressed again in two steps:
(a) Who is parent, X, of Ann? ⇒ parent(X,ann).
(b) Is (this name) X a parent of Pat? ⇒ parent(X,pat).

The corresponding question to Prolog is then

|?_parent(X,ann), parent(X,pat).
The answer is
X=bob

3 May 2025 NGJD@FCT-UoK 22

1.4 Some important points to note
• It is easy in Prolog to define a n-place relation (n-place predicate), such as parent
relation, by stating the n-tuples of objects that satisfy the relation.
• 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 (among other things) be: concrete objects, or
constants (such as tom and ann), or general objects such as X and Y.
- Objects of the first kind in our program are called atoms.
- Objects of the second kind are called variables.

3 May 2025 NGJD@FCT-UoK 23

• Questions to the system consists of one or more goals.
A sequence of goals such as
|?_parent(X,ann), parent(X,pat).
means the conjunction of goals:
X is a parent of Ann and X is a parent of Pat.
The word ‘goals’ is used because Prolog interprets questions as goals that are to be
satisfied.
To ‘satisfy a goal’ means to logically deduce the goal from the program.
5. An answer to the question can be either positive or negative depending on
whether the corresponding goal can be satisfied or not.
In the case of positive answer we say the corresponding goal was satisfiable and
that the goal is succeeded.
Otherwise the goal was unsatisfiable and it failed.
6. If several answers satisfy the question, then Prolog will find many of them as
desired by the user.
3 May 2025 NGJD@FCT-UoK 24
Exercises
1. Assuming the parent relation as defined in this section, what will be Prolog's
answers to the following questions?
(a) |?_parent( jim, X).
(b) |?_parent( X, jim).
(c) |?_parent( pam, X), parent( X, pat).
(d) |?_ parent( pam, X), parent( X, Y), parent( Y, jim).
2. Formulate in Prolog the following questions about the parent relation:
(a) Who is Pat's parent?
(b) Does Liz have a child?
(c) Who is Pat's grandparent?

3 May 2025 NGJD@FCT-UoK 25

1.5 Extending the example program by rules
• As an extension, let us introduce the ‘offspring’ relation as the inverse of the
“parent” relation.
• We could define ‘offspring’ in a similar way as ‘parent’ relation; i.e., by simply
providing a list of simple fact about the ‘offspring’ relation.
Each fact mentioning one pair of people such that one is an offspring the other.
For example,
offspring(tom,bob).
• However, ‘offspring’ relation can be defined much more elegantly by making the
use of fact that it is inverse of ‘parent’, and that ‘parent’ has already been defined.

3 May 2025 NGJD@FCT-UoK 26

 This alternative way can be based on following logical statement:
Y is an offspring of X if X is a parent of Y.

Then corresponding Prolog representation which has same meaning is

offspring(Y,X):-parent(X,Y).

Prolog clauses such as “offspring(Y,X):-parent(X,Y).” are called rules.

• The symbol ‘:-’ is read as ‘if’.

3 May 2025 NGJD@FCT-UoK 27

 The following program 1.2 is an extension to the program 1.1 by adding a new rule.

parent(tom,bob).
parent(pam,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).
offspring(Y,X):-parent(X,Y).
Program 1.2

3 May 2025 NGJD@FCT-UoK 28

 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 offspring in the program.
Therefore the only way to consider this question is to apply the rule about offspring.
The rule is general in the sense that it is applicable to any object X and Y.
Therefore, it can also be applied to such particular objects Liz and Tom.
To apply the rule to Liz and Tom, Y has to be substituted with Liz and X with Tom.
We say that variable X and Y become instantiated to
X=tom and Y=liz.

3 May 2025 NGJD@FCT-UoK 29

 After the instantiation we have obtain the special case of our general rule.
The special case is
offspring(liz,tom):-parent(tom,liz).
The condition part as become
parent(tom,liz).
Now Prolog tries to find out whether the condition part is true.
So the initial goal
offspring(liz,tom)
has been replaced with the sub goal
parent(tom,liz).
This (new) goal happens to be trivial as it can be found as a fact in our program.
This means that the conclusion part of the rule is also true and Prolog will answer
the question with “yes”.
3 May 2025 NGJD@FCT-UoK 30
• Note:
There is an important difference between facts and rules.
A fact like
parent(tom,bob)
is the something that is always unconditionally true.

On the other hand, rules specify things that may be true if some conditions may be
satisfied.
Therefore we say that rules have,
- a condition part (The right hand side of the rule)
- a conclusion part (The left hand side of the rule)
The conclusion part also called the head of a clause, and the condition part is
called the body of the clause.
3 May 2025 NGJD@FCT-UoK 31
 This terminology is illustrated by the following example:

offspring(Y,X) :- parent(X,Y).

Head Body

3 May 2025 NGJD@FCT-UoK 32

1.6 Further extension to our example program
• Our example program 1.2 can be easily extended in many interesting ways.
• Let us first add the following information on the sex of the people that occur in the
“parent” relation.
Pam is a female.
Tom is a male.
Bob is a male.
Liz is a female.
Pat is a female.
Ann is a female.
Jim is a male.
• Each of these facts represents some property of the object.
3 May 2025 NGJD@FCT-UoK 33
• If we introduce the 1-place relations or 1-place predicate male(X) and female(X) by
male(X) is true if and only if X is a male,
and
female(Y) is true if and only if Y is a female,
the above set of facts can be written in Prolog as
female(pam).
male(tom).
male(bob).
female(liz).
female(pat).
female(ann).
male(jim).

3 May 2025 NGJD@FCT-UoK 34

• As our next extension to the program, let us introduce “mother” and “father”
relations.
• The specification of the “mother” and “father” relations can be based on the
following logical statements:
X is the mother of Y if X is a parent of Y, and X is a female.
X is the father of Y if X is a parent of Y, and X is a male.
These are translated into Prolog as the following rules:
mother(X,Y):-parent(X,Y), female(X).
father(X,Y):-parent(X,Y), male(X).

3 May 2025 NGJD@FCT-UoK 35

• Note:
1. The comma between goals in the body means conjunction: for the body to be
true, all the goals in the body have to be true.
2. If the condition part ‘parent(X,Y), female(X)’ is true then a logical
consequence of this is ‘mother(X,Y)’.
mother(X,Y) :- parent(X,Y), female(X).
Goal Goal

Head Body

3 May 2025 NGJD@FCT-UoK 36

• Now let us try to define the ‘grandparent’ relation.
The ‘grandparent’ relation is based on the following logical statement:
X is a grandparent of Z if X is a parent of Y and Y is a parent of Z.
In Prolog this can be written as,
grandparent(X,Z):-parent(X,Y),parent(Y,Z).

3 May 2025 NGJD@FCT-UoK 37

• Now let us try to define the ‘sister’ relation.

‘Sister’ relation is based on following logical statement:

X is a sister of Y if
(a) Both X and Y have the same parent
and (b) X is a female.
In Prolog this can be written as,

sister(X,Y):-parent(Z,Y),parent(Z,X),female(X).

3 May 2025 NGJD@FCT-UoK 38

• Now our program 1.2 with the relations ‘male’, ‘female’, ‘mother’, ‘father’,
‘grandparent’ and ‘sister’ constitute the following program 1.3.

3 May 2025 NGJD@FCT-UoK 39

 Program 1.2
+
female(pam).
male(tom).
male(bob).
female(liz). Program 1.3
female(pat).
female(ann).
male(jim).
mother(X,Y):-parent(X,Y),female(X).
father(X,Y):-parent(X,Y),male(X).
grandparent(X,Z):-parent(X,Y),parent(Y,Z).
sister(X,Y):-parent(Z,Y),parent(Z,X),female(X).

3 May 2025 NGJD@FCT-UoK 40

• Now we can ask
|?_ sister(ann,pat).
The answer will be ‘yes’ as expected.
Therefore, we might conclude that the ‘sister’ relation, as defined, works correctly.

If we ask the question who is Pat’s sister?:

|?_sister(X,pat).

Prolog will find two answers, one of which may come as a surprise:
X=ann;
X=pat

So, Pat is a sister of her self!.

3 May 2025 NGJD@FCT-UoK 41

 According to rule about sisters, Prolog answer is perfectly logical.

Our rule about sisters does not mention that X and Y must be different if there to be
sisters.

To correct our rule about sisters we have to add that X and Y must be different.
We can state this as X \= Y (this means X and Y are not the same).

An improved rule for the ‘sister’ relation can then be

sister(X,Y):-parent(Z,Y),parent(Z,X),female(X),X \= Y.

3 May 2025 NGJD@FCT-UoK 42

1.7 Some important points to note
• Prolog programs can be extended by simply adding new clauses.
• Prolog clauses are of three types: facts, rules and questions.
• Facts declare things that are always, unconditionally true.
• Rules declare things that are true depending on a given condition.
• By means of questions the user can ask the program what things are true.
• A Prolog clause consist of the head and the body.
The body is a list of goals separated by commas. Commas between goals are
understood as conjunctions.
Goals
H :- C1, C2,…, Cn
Head Body
3 May 2025 NGJD@FCT-UoK 43
• Facts are clauses that have the empty body. Questions only have the body. Rules
have the head and the (non-empty) body.
• In the course of computation, a variable can be substituted by another object. We
say that a variable becomes instantiated.
• Variables are assumed to be universally quantified and are read as ‘for all’.
Alternative readings are, however, possible for variables that appear only in the
body.
For example,
hasachild(X) :- parent(X, Y).
can be read in two ways:
(a) For all X and Y, if X is a parent of Y then X has a child.
(b) For all X, X has a child if there is some Y such that X is a parent of Y.
Logically, both readings are equivalent.

3 May 2025 NGJD@FCT-UoK 44

Exercises
1. Translate the following statements into Prolog rules:
(a) Everybody who has a child is happy (introduce a one-argument relation
‘happy’).
(b) For all X, if X has a child who has a sister then X has two children (introduce
new relation ‘hastwochildren’).
2. Define the relation ‘grandchild’ using the ‘parent’ relation. Hint: It will be similar to
the ‘grandparent’ relation.
3. Define the relation aunt(X, Y) in terms of the relations ‘parent’ and ‘sister’.

3 May 2025 NGJD@FCT-UoK 45

1.8 Recursive Programming in Prolog
• Let us add one more relation to our family program, the ‘ancestor’ 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) ancestors and the second rule the
indirect ancestors.
• We say that some X is an indirect ancestor of some Z if there is a chain of parents
between X and Z, as illustrated in Figure below.

3 May 2025 NGJD@FCT-UoK 46

 Direct Ancestors Indirect Ancestors
X X X
X

parent ancestor parent parent parent

ancestor Y1 Y1
Y1
Z ancestor
parent parent parent

Z Y2 Y2

parent
ancestor
Z
Yn

parent

3 May 2025 NGJD@FCT-UoK 47

 Consider the following two rules:
X is a direct ancestor of Z, if X is a parent of Z.
X is an indirect ancestor of Z, if there is a parentship chain of people between
X and Z.

The first rule will defines the direct (immediate) ancestors and the second rule
defines the indirect ancestors.

So that first rule of the definition is simple and can be formulated as follows:
X is a ancestor of Z if X is parent of Z.

This is represented by the Prolog clause:

ancestor(X,Z):-parent(X,Z).

3 May 2025 NGJD@FCT-UoK 48

 The second part of definition is more complicated because the chain of parents has
arbitrary length.

According to the above figure ancestor of relation could be defined by a set of

clauses as follows:
ancestor(X,Z):-parent(X,Y1), parent(Y1,Z).
ancestor(X,Z):-parent(X,Y1), parent(Y1,Y2), parent(Y2,Z).
⋮
ancestor(X,Z):-parent(X,Y1), parent(Y1,Y2),…, parent(Yn-1,Yn), parent(Yn,Z).

This program is lengthy and more importantly it work to some extent.

It would only discover ancestor to certain depth in the family tree because the
length of the chain of people between the ancestor and successor would be limited
by the length of our ‘ancestor’ clauses.
3 May 2025 NGJD@FCT-UoK 49
 There is, however, a much more elegant and correct formulation of the ‘ancestor’
relation.
It will work for ancestors at any depth.
The key idea is to define the ‘ancestor’ relation in terms of itself.
X
The following figure illustrate the idea:
parent
For all X and Z, Y
X is an ancestor of Z if there exist a Y such that
(a) X is a parent of Y and, ⋮ ancestor
(b) Y is an ancestor of Z. ancestor

Z
3 May 2025 NGJD@FCT-UoK 50
 The Prolog clause with the above meaning is:
ancestor(X,Z):-parent(X,Y), ancestor(Y,Z).
The main feature of the definition is the use of ancestor to define ancestor. Such
definitions are called recursive definitions.
Recursive programming is, in fact, one of the fundamental principles of
programming in Prolog, and replaces loop structures used in procedural languages.
It is not possible to solve tasks of any significant complexity in Prolog without use of
recursion.

3 May 2025 NGJD@FCT-UoK 51

 Thus, we have constructed a complete program for the ancestor relation, which
consists of two rules: one for direct ancestors and one for indirect ancestors.
Both rules are rewritten together here:
ancestor(X,Z):-parent(X,Z).
% Rule 1: X is ancestor of Z
ancestor(X,Z):-parent(X,Y),ancestor(Y,Z).
% Rule 2: X is ancestor of Z

The complete program up to this point is given in the next slide.

3 May 2025 NGJD@FCT-UoK 52

 parent(pam, bob). % Pam is a parent of Bob.
:
parent(pat, jim). % Pat is a parent of Jim.
female(pam). % Pam is a female.
:
male(jim). % Jim is a male.
offspring(Y,X):-parent(X,Y).
mother(X,Y):-parent(X,Y),female(X).
father(X,Y):-parent(X,Y),male(X).
grandparent(X,Z):-parent(X,Y),parent(Y,Z).
sister(X,Y):-parent(Z,Y),parent(Z,X),female(X).
ancestor(X,Z):-parent(X,Z).
% Rule 1: X is ancestor of Z
ancestor(X,Z):-parent(X,Y),ancestor(Y,Z).
% Rule 2: X is ancestor of Z
Program 1.4

3 May 2025 NGJD@FCT-UoK 53

 Let us see how Prolog would find someone’s ancestors using recursive definition of
ancestor.

We can ask Prolog: Who is a person that Pam is his or her ancestor? by
|?_ancestor(pam,X).

Which yields the answers,

X=bob;
X=ann;
X=pat;
X=jim;
no
|?_

3 May 2025 NGJD@FCT-UoK 54

• Prolog's answers to the above question are of course correct and they logically
follow from our definition of the ancestor and the parent relation.
• Now, we have a rather important question: How did Prolog actually use the
program to find these answers?
An informal explanation of how Prolog does this is given in the section 1.11.

3 May 2025 NGJD@FCT-UoK 55

1.9 Prolog procedures and comments
• The ancestor relation, for example, is defined by two clauses.
Sometimes it is convenient to consider a whole set of clauses defining the same
relation as a single unit called a procedure.
• Comments can be added to a Prolog program as in other programming
languages.
Comments are distinguished in Prolog from the rest of the program by being
enclosed in special brackets ‘/*' and '*/' .
Thus comments in Prolog look like this:
/* This is a comment */.

3 May 2025 NGJD@FCT-UoK 56

 Another method, more practical for short comments, uses the percent character
'%'.
Everything between ‘%’ and the end of the line is interpreted as a comment:
% This is also a comment.

3 May 2025 NGJD@FCT-UoK 57

1.10 Running the program with a Prolog system
• There are several good quality and freely available Prolog versions, such as SWI
Prolog, YAP Prolog and CIAO Prolog.
• In this course module we are going to use SWI Prolog. Download and install SWI
Prolog system on your computer.
• Now follow the following steps to create, save and execute a Prolog program:
1. Suppose that your program, for example your family program, has already
been typed into the computer using a plain text editor, such as Notepad.
2. Suppose that the file has been saved into a chosen directory, say
‘Prolog_programs’, as a file with the extension ‘.pl’, for example ‘family.pl’.
3. Now you can start your Prolog system.
It will be displaying the prompt ‘?-’, which means that Prolog is waiting for your
questions or commands.
3 May 2025 NGJD@FCT-UoK 58
 4. First, you need to tell Prolog that the ‘working directory’ will be your chosen
directory ‘Prolog_programs’.
This can be done through the ‘Working directory’ entry in the ‘File’ menu.
Prolog will now except to read program files from the selected directory
‘Prolog_programs’.
5. Then you tell Prolog to read in your program from file ‘family.pl’ by typing:
?-consult(family).
or equivalently:
?-[family].
Prolog will read the file family.pl and answer something to the effect ‘File
family.pl successfully consulted’, and again display the prompt ‘?-’.
6. Now you can pose questions to the Prolog system only on the relations defined
in the file ‘family.pl’.
3 May 2025 NGJD@FCT-UoK 59
 For example, consider the conversation with Prolog system:
?-parent(tom,X).
X = bob;
X = liz;
no
?-ancestor(X,ann).
X = bob;
X = pam;
⋯

3 May 2025 NGJD@FCT-UoK 60

1.11 How Prolog answer questions
• This section gives an informal explanation of how Prolog answers questions.
• A question to Prolog is always a sequence of one or more goals.
• To answer a question, Prolog tries to satisfy all the goals.
• To satisfy a goal means to demonstrate that the goal is true, assuming that all the
relations in the program are true.
In other words, to satisfy a goal means to demonstrate that the goal logically
follows from the facts and rules in the program.
• If the question contains variables, Prolog also has to find what are the particular
objects (in place of variables) for which the goals are satisfied.
The particular instantiation of variables to these objects is displayed to the user.
If Prolog cannot demonstrate for some instantiation of variables that the goals
logically follow from the program, then Prolog's answer to the question will be 'no'.
3 May 2025 NGJD@FCT-UoK 61
• In mathematical terms: Prolog accepts facts and rules as a set of axioms, and try to
prove that the user's question can be logically derived from the axioms.
• This can be illustrated through the following set of examples:
1. Let us consider the two statements:
All men are fallible,
Socrates is a man.
A consequence that logically follows from these two statements is:
Socrates is fallible.
The first axiom above can be rewritten as:
For all X, if X is a man then X is fallible.

3 May 2025 NGJD@FCT-UoK 62

 Accordingly, if we define two relations, man(X) and fallible(X), then the two
statements in the example can be translated into Prolog as follows:
fallible(X) :- man(X). % All men are fallible
man(socrates). % Socrates is a man
?- fallible(socrates). % Socrates is fallible?
yes

3 May 2025 NGJD@FCT-UoK 63

 2. A more complicated example from the family program 1.4 is:
|?-ancestor(tom, pat).
Prolog will try to satisfy this (initial) goal with the clauses in the program about
the ancestor relation through matching.
There are only two clauses relevant to this end: the clauses labeled Rule1 and
Rule2.
We say that the heads of these two rules match with the goal.
This matching is done according to the order of clauses appear in the program.
Applying the Rule1 (which is the first) with the variable instantiations X = tom
and Z = pat, we obtain a special case of our Rule1:
ancestor(tom, pat):-parent(tom,pat).

3 May 2025 NGJD@FCT-UoK 64

 Now the original goal ancestor(tom, pat) is then replaced by a new goal,
parent(tom,pat).
There is no clause in the program whose head matches the goal
parent(tom,pat), therefore this goal fails.
This means the first alternative with Rile1 has failed.
Now Prolog backtracks to the original goal in order to try the second alternative
to original goal parent(tom,pat).
Now Prolog will try to match our original goal, ancestor(tom,pat), with the head
of Rule2 (which is the second matching clause in the program).
As before, the variables X and Z becomes instantiated as:
X = tom and Z = pat
and we obtain the special case of our Rule2:
ancestor(tom, pat):-parent(tom,Y),ancestor(Y,pat).
3 May 2025 NGJD@FCT-UoK 65
 But Y is not instantiated yet.
So the initial goal, ancestor(tom, pat), has been replaced with two sub goals:
parent(tom,Y), ancestor(Y,pat).
Now Prolog tries to satisfy the two goals in the order in which they appear.
The first goal, parent(tom,Y), matches two facts in the program 1.4:
parent(tom,bob) and parent(tom,liz).
Prolog first tries to satisfy the first goal, parent(tom,Y), by matching with the
fact that appears first in the program.
This force Y to become instantiated to bob.
Thus the first goal has been satisfied, and the remaining goal has become:
ancestor(bob,pat).
To satisfy this goal the Rule1 is used again.

3 May 2025 NGJD@FCT-UoK 66

 Note that this (second) application of the same rule has nothing to do with its
previous application.
Therefore, Prolog uses new set of variables in the rule each time the rule is
applied.
To indicate this we shall rename the variables in Rule1 for this application as
follows:
ancestor(X’,Z’) :- parent( X’, Z’).
The head has to match our current goal ancestor(bob, pat).
Therefore, X’ = bob, Z’ = pat.
The current goal is replaced by:
parent(bob, pat).

3 May 2025 NGJD@FCT-UoK 67

 This goal is immediately satisfied because it appears in the program as a fact.
This completes the execution trace which is graphically shown in the following
Figure.
ancestor(tom,pat)

by Rule1 by Rule2

parent(tom,pat) parent(tomY),
no
ancestor(Y,pat)
by fact parent(tom,bob), Y = bob

ancestor(bob,pat)

by Rule1

parent(bob,pat)
yes, by fact parent(bob,pat)
3 May 2025 NGJD@FCT-UoK 68
• In the above graphical illustration of the execution trace has the form of a tree.
- The nodes of the tree correspond to goals, or to lists of goals that are to be
satisfied.
- The arcs between the nodes correspond to the application of (alternative) program
clauses that transform the goals at one node into the goals at another node.
- The top goal is satisfied when a path is found from the root node (top goal) to a
leaf node labelled ‘yes’.
- A leaf is labelled ‘yes’ if it is a simple fact.
- The execution of Prolog programs is the searching for such paths.
- During the search, Prolog may enter an unsuccessful branch.
- When prolog discovers that a branch fails it automatically backtracks to the
previous node and tries to apply an alternative clause at that node.
- Automatic backtracking is one of the distinguishing features of Prolog.
3 May 2025 NGJD@FCT-UoK 69
• In Prolog to establish whether an object satisfies a query is often a complicated
process that involves logical inference, exploring among alternatives and possible
automatic backtracking.
• All this is done automatically by the Prolog system and is, in principle, hidden from
the user.
• This hidden process is known as the inference engine or the inference mechanism in
Prolog.
• The automatic backtracking process can be explained as follows:
When Prolog fails to satisfy a goal through matching with particular rule/fact, Prolog
automatically tries similar rule/fact until there are no more rules/facts. In other
words, failing the consideration of rule/fact, Prolog automatically backtracks to find
other rules/facts that may satisfy the goal.
• Automatic backtracking is the mechanism that facilitates the process of finding
multiple solutions to a question, if exists.

3 May 2025 NGJD@FCT-UoK 70

1.12 Declarative and procedural meaning of programs
• In our examples so far it has always been possible to understand the results of the
program without exactly knowing how the system actually found the results.
• It therefore makes sense to distinguish between two levels of meaning of Prolog
programs; namely,
o the declarative meaning and
o the procedural meaning.
• The declarative meaning is concerned only with the relations defined by the
program.
The declarative meaning thus determines what will be the output of the program.
• On the other hand, the procedural meaning also determines how this output is
obtained; that is, how are the relations actually evaluated by the Prolog system.

3 May 2025 NGJD@FCT-UoK 71

• The ability of Prolog to work out many procedural details on its own is considered to
be one of its specific advantages.
• It encourages the programmer to consider the declarative meaning of programs
relatively independently of their procedural meaning.
• Since the results of the program are, in principle, determined by its declarative
meaning, this should be (in principle) sufficient for writing programs.
• This is of practical importance because the declarative aspects of programs are
usually easier to understand than the procedural details.
• To take full advantage of this, the programmer should concentrate mainly on the
declarative meaning and, whenever possible, avoid being distracted by the
executional details.
• These should be left to the greatest possible extent to the Prolog system itself.

3 May 2025 NGJD@FCT-UoK 72

• This declarative approach indeed often makes programming in Prolog easier than in
typical procedurally oriented programming languages such as C and Pascal.
• Unfortunately, however, the declarative approach is not always sufficient.
• It will later become clear that, especially in large programs, the procedural aspects
cannot be completely ignored by the programmer for practical reasons of
executional efficiency.

3 May 2025 NGJD@FCT-UoK 73

Summary
• Prolog programming consists of defining relations and querying about relations.
• A program consists of clauses. These are of three types: facts, rules and questions.
• A relation can be specified by facts, simply stating the n-tuples of objects that satisfy
the relation, or by stating rules about the relation.
• A procedure is a set of clauses about the same relation.
• Querying about relations, by means of questions, resembles querying a database.
Prolog's answer to a question consists of a set of objects that satisfy the question.
• In Prolog, to establish whether an object satisfies a query is often a complicated
process that involves logical inference, exploring among alternatives and possibly
backtracking.
All this is done automatically by the Prolog system and is, in principle, hidden from
the user.
3 May 2025 NGJD@FCT-UoK 74
• Two types of meaning of Prolog programs are distinguished: declarative and
procedural.
• The declarative view is advantageous from the programming point of view.
• Nevertheless, the procedural details often have to be considered by the
programmer as well.

3 May 2025 NGJD@FCT-UoK 75