Logic Programming


Advertisements


Introduction to PROLOG Programming

To introduce readers to the syntax and semantics of logic programming, we
first take a look at a few examples. Let us, for instance, consider the problem of a ‘classroom scene’ interpretation We assume that the scene has been passed
through various stages of low and medium level image processing and the
objects in the scene thus have been recognized and labeled by a computing
machine. The data (clauses) received from the scene and the knowledge used to
analyze it are presented in both English and Predicate Logic below.

Database:
Object (board)
Writes-on (john, board, classhour)
Sits-on (mita, bench, classhour)
Sits-on (rita, bench, classhour)
Person (john)
Person (rita)
Person (mita)
The above are called clauses in PROLOG.


Logic Programs - A Formal Definition

We are now in a position to formally define Logic Programs. We first define
a Horn clause, the constituents of a logic program

Definition: A clause consists of two parts: the head and the body. One
side of the clause to which the arrowhead (if-then operator) points to is called
the head and the other side of it is called the body. A Horn clause contains at
most one literal (proposition / predicate) at the head of the clause.

Example: The following are two examples of Horn clauses.
i) P (X), Q (Y) → W (X,Y)
ii) R (X, Y), Q (Y) → ?

In (i) W (X, Y) is the head and P (X), Q (Y) is the body. In (ii) R(X, Y),
Q(Y) is the body and the head comprises of a null clause (sub-clause). In fact
(ii) represents a query, asking whether R (X, Y), Q (Y) is true, or what are the
set of instantiations for X and Y, which makes R (X, Y) ^ Q (Y) true.

Definition: A Logic Program is a program, comprising of Horn
clauses.

The following example illustrates a logic program.

Example: Consider the following two sentences in Predicate Logic with
one head clause in each sentence.
Father (X, Y) ← Child (Y, X), Male (X).
Son (Y, X ) ← Child (Y, X), Male (Y).
The above two clauses being horn clauses are constituents of a Logic
Program. Let us now assume that along with the above knowledge, we have
the following three data clauses:

Child (ram, dasaratha).
Male (ram).
Male (dasaratha).

Suppose that the above set of clauses is properly structured in PROLOG
and the program is then compiled and executed. If we now submit the
following queries (goals), the system responds correctly as follows.

  1. Goal: Father (X, Y)?
    Response: Father (dasaratha, ram).
  2. Goal: Son (Y, X)?
    Response: Son (ram, dasaratha).

But how does the system respond to our queries? We shall discuss it
shortly. Before that let us learn a little bit of syntax of PROLOG programs. We
take up the scene interpretation problem as an example to learn the syntax of
PROLOG programming.

A Scene Interpretation Program

/* PROLOG PROGRAM FOR SCENE INTERPRETATION */
Domains
Time, X, Y, Z, W, board, classhour, bench = symbol
Predicates
Teacher (X)
Writes-on (X, board, Time )
Equal (Time, classhour)
Person (X) Person (Y) Person (Z) Person (W)
Sits-on (Y, bench, Time) Sits-on (Z, bench, Time)
Student (Y)
Student (Z)
Object (W)
Clauses
Object (board). 1
Writes-on (john, board, classhour). 2
Male (dasaratha).
Sits-on (mita, bench, classhour). 3
Sits-on (rita, bench, classhour). 4
Person (john). 5
Person (mita). 6
Person (rita). 7
Equal (Time, classhour):- 8
Object (board),
Writes-on (X, board, Time),
Teacher (X).
Equal (Time, classhour):- 9
Person (Y),
Sits-on (Y, bench, classhour),
Person (X),
Writes-on (X, board, Time).
Teacher (X):- 10
Person (X),
Writes-on (X, board, classhour).
Student (Y) :- 11
Person (Y),
Sits-on (Y, bench, Time),
Equal (Time, classhour).
This is all about the program. Readers may note that we mentioned no
procedure to solve the problem of scene interpretation; rather we stated the
facts only in the program. Here lies the significance of a logic program.
Now, suppose, the user makes a query:
Goal: Teacher (X)?
System prompts: Teacher (john).
Further, if the user asks:
Goal: Equal (Time, classhour) ?
System prompts: Yes.


Illustrating Backtracking by
Flow of Satisfaction Diagrams

To explain how the system answers these queries, we have to learn a very
useful phenomenon, called backtracking.
Let us now concentrate on the query: Teacher (X)?
Since
Teacher (X) ←
 Person (X),
  Writes-on (X, board, classhour).
to satisfy the Goal: Teacher (X), one has to satisfy the sub-goals: Person (X),
Writes-on (X, board, classhour). Now, PROLOG searches a sub-goal Person( )
for the predicate Person (X). At clause 5, it finds a match and X is instantiated
to john . PROLOG puts a marker at clause 5. Now, it continues
searching Writes-on (john, board, classhour) in the remaining clauses. But it
fails to find so, since Writes-on (john, board, classhour) is at 2nd position in
the list of clauses . So, it has to trace back above the marker place
and then ultimately it finds Writes-on (john, board, classhour)
. Since the sub-goals are succeeded, the goal also succeeds,
yielding a solution: Teacher (john).

For answering the query Equal (Time, classhour), a number of
backtracking is required. We omit this for space constraints and ask the reader
to study it herself. The next important issue that we will learn is SLD (Select
Linear Definite clauses) resolution.