[CSUSB] >> [CompSci] >> /pool/faculty/dick/cs320/sebesta/16

## CS320 Notes on Logic Programming

```	http://www.csci.csusb.edu/cs320/sebesta/16.html

```

```
```

## 16.2 The Predicate Calculus

```      Books introduction is OK but does not define a predicate.
A proposition is some true/false statement.
A predicate is a proposition that contains variables
and constants of some type or other.
In class we will list some example predicates(semantics).

In logic programming predicates have the familiar syntax
of conditions or boolean expressions but a totally different
semantics.

```

## 16.2.1 Propositions.

```	Definition of atomic propositions, terms and functor comes
from Prolog.  The word 'functor' is used because they look
like 'functions' but DON'T return a value when 'invoked'.

The book uses a rather strange notation for propositions
that is neither standard nor ASCII.
I recommend you use the notation in
http://www.csci.csusb.edu/dick/maths/intro_logic.html
Examples (Page 608, 4th edn., page 537, 3rd edn):
for all X (if woman(X) then human(X))
for some X( mother(mary,X) and male(X))

```

## 16.2.2 Clausal Form

```
The book introduces this because these clauses explain what
Prolog does.  Therefore use Prolog's symbol in place of the
REVERSED HOOK
used in the book:
B1 or B2 or ... or Bn :- A1 and A2 and... and An

P:-Q::=if Q then P.
Page 609
likes(bob, trout):- likes(bob,fish) and fish(trout).
father(louis, al) and father(louis, violet) :- father(al,bob) and mother(violet, bob) and grandfather(louis,bob).

Page 538, old edition.

```

## 16.3 Resolution.

```	This is a beautiful improvement over the way that computers normally work!

Instead of following instructions that calculate a unique state
from a previous one,
we look for a state that fits all the current constraints,
and
if its not good enough we look for another one.

Notice the words
unification
instantiation
Nothing makes much sense without them.

RESOLUTION is a generic way of combining two statements
into a single conclusion.  I think of it as being like
multiplying two factions and seeing what cancels out.
(123/234)*(234/567) ====> (123/567)
(P:-Q) and (Q:-R)   ====> (P:-R)
But it only works with statements in a particular form.
They are called Horn Clauses.  They have form: P if Q.

UNIFICATION is a way to handle variables and constants.
It is used to handle arguments in Prolog.
The idea is a simple comparing and matching two structures.
When we match up a variable with a constant we know the value.

Algorithm to UNIFY to structures or formula
Case 1: Two atoms(constants).
If they are equal then they unify
else unification fails.
Case 2: Two variables,
Take note of the fact that they are ACTUALLY the same
variable
Case 3: A variable and a non-variable.  Take note
that this variable(and those equal to it) must
all match the non-variable.
Case 3: Two structures (recursive)
F1(X1,X2,X3,....)
vs
F2(Y1,Y2,.......)
Then F1 and F2 must be the same atom
and they must have the same number of arguments(arities),
and X1 must unify with Y1
and X2 must unify with Y2
and so on.

Sample:
How can a(X,1,Y)=a(2, Z, c(X))?
Unify a(X,1,Y) with a(2, Z, c(X))
this is case 3 above, F1=F2=a, and there are 3 things two compare.
Unify   X=2
1=Z
Y=c(X)
So X is 2, Z is 1 and so Y is c(2)...
a(1,1,c(2)) = a(2,1,c(2)).

Notice.  The meaning of a and c is not used.  Prolog/unifications
aims to solve the equality for ALL POSSIBLE MEANINGS.

The Prolog experiments in the labs and the homework
have lots of examples of unification.

Instanciation.
Prolog variables are NOT normal.  They are more like
mathematical variables.  They start out without any
values (prolog numbers them _0, _1, _2, _3, ...).
Unification can bind a variable to a a structure
(which can have variable in it!)
Once bound the value stays the same and the variable
starts to behave like a constant (almost).
However, if a step fails the prolog system
back-tracks and systematically turns these
pseudo-constants back into undefined variables again.
Only then can they be given a new value.

When a command or query finishes, it has removed
all variables....

This is different enough for us to not talk about
assignment
but to talk about a variable having different
instances
and the process of
instantiation
is that of binding a variable to a temporary instance.

```

## 16.4

```	The idea is that

THE SPECIFICATION AUTOMATICALLY DETERMINES THE PROGRAM.

It is not quite that simple, however.

But it IS an EXCELLENT idea to note down the requirements for a
program, in logic, prior to writing the program.
(for a BIG, undefined problem that is).
You'll find lots of bugs this way before you waste time programming them!

Do not make the mistake of going straight into Prolog
without sorting out the logic first.
You end up fighting on two fronts.  On one side you fight your
lack of understanding and on the other you fight with Prolog
itself.

In http://www.csci.csusb.edu/cs320/ are two sample solutions to
a problem:
\$CS320/prolog/compsci.plg  is such a failed attempt.
\$CS320/prolog/compsci2.plg was done after analyzing the problem better.

```

## 16.5 History

```
Know the names and dates

```

## 16.6 Basic Elements

```
Our prolog is like the one Sebesta describes.
SWI-prolog.
It is compiled from Source and is available fro UNIX, DOS,
Windows1 through to 95

To store input - finish with a full-stop.
Beware of tapping enter without typing a ".", "!" or "?".

atoms can be a string enclosed in single quotes.
This is useful for naming files:
consult('metro.plg')!

```

```
```

```
```

## 16.6.6 Arithmetic --- the pernicious 'is'

```
The book is NOT joking....

```

```

```

## 16.7 Deficiencies

```	The Cut
The Closed World assumption
The Negation Problem
Intrinsic Limitation
The Negation Problem

```

## 16.8 Applications

```	Relational DBs - most don't use prolog (pity!)
Expert Systems - the only successful every day use of AI.
Natural Language
Education - We have discussed using it here...

```

## 16.9 Conclusions.

```
ALSO - A little logic never hurt anyone
as long as they can use it creatively.

I've had more fun and frustration with 'prolog' than with any
language I've learned for the last 10 years....

Problems 3,4,5,6,7 Are good portfolio material.

```