Transcript document

CMPB454
ARTIFICIAL INTELLIGENCE
(AI)
CHAPTER 6
LOGIC PROGRAMMING
USING PROLOG
Instructor: Alicia Tang Y. C.
UNIVERSITI TENAGA NASIONAL
PROLOG
STANDS FOR PROGRAMMING IN LOGIC
 Features:

SYMBOLIC LANGUAGE
CLEAN SYNTAX
See last example
BACKTRACKING
PATTERN MATCHING
Refer diagram
BUILT-IN SEARCH ENGINE
RECURSION
Look at “List”
UNIFICATION
2
Prolog as a Language for AI Problem
Solving

Introduction to PROLOG
– PROLOG is a language, an
environment, and as a powerful
problem solving tool.
– As a representational formalism,
PROLOG offers an interpreter for
predicate calculus specifications.
3
PROLOG




It is based on Predicate Logic (Horn
clause, a special type of clausal form).
It makes use of resolution to proof goals.
Search is done depth first with
backtracking.
The primitive form is a predicate:
– father(kasim, hani).
Kasim is the father of Hani
– age(kasim, 60).
Kasim is 60 years old
– retired(kasim).
Kasim has retired
– intake(bit, june, 2004). BIT intake is in June’04
– pi(3.145).
Pi = 3.145
4
First Prolog Program
FACTS (KNOWLEDGE)
parent(john,bob).
parent(mary,alice).
parent(mary,bob).
parent(john,alice).
parent(lee, june).
sex(john,male).
sex(mary,female).
sex(bob, male).
sex(alice,female).
sex(june,female).
sex(lee,male).
5
mother(Mother,Child):parent(Mother,Child).
sex(Mother, female).
female is a fact
or “constant”
mother_1(Mother,Child):sex(Mother, female),
parent(Mother, Child).
sibling(Child1, Child2):parent(M,Child1),
sex(M, female),
parent(F, Child1),
sex(F, male),
parent(M, Child2),
parent(F, Child2).
In English,
the statements read as:
“Siblings are those who
share the same parents”.
You will get funny answer. Try it out in Lab.
6
Simpler is better. Define extra predicates.
mother(M, Child):parent(M,Child),
sex(M, female).
father(F, Child):parent(F,Child),
sex(M, male).
sibling(Child1, Child2):mother(M, Child1),
Checks that generated answers
father(F,Child1),
are not the same, then return them
mother(M, Child2),
father(F, Child2),
Child1 \= Child2.
7
Prolog Queries
Queries use the format as a predicate. Predicates must be
terminated by a full stop.
?- parent(Who, unix).
Who = thompson;
Who = ritchie;
no
Prolog variables are designated with a capitalised first letter
in a word.
?- father(tom, pat).
yes
(Prolog answers ‘yes’ indicating query success)
8
Prolog Queries
?- father(tom,Who).
Who = pat;
Who = jane
yes
(Prolog answers and the user types a semicolon;
Prolog gives another solution)
9
Prolog Queries
Note: Whenever Prolog gives an answer and the user
responds with a semicolon (‘;’),
Prolog backtracks and looks for alternative answers.
?- father(X,pat), age(X,Age).
X = tom, Age = 42
yes
Note: A multi-condition query can be specified
using the commas (‘,’) to separate the conditions.
This represents a conjunction (‘and’) of literals.
10
Prolog “Rules”
Prolog programs consists of statements called clauses
which are similar to sentences in Natural Language.
Prolog clauses consists of a head and a body and
generally has the form:
head :-
body.
The head of a clause consists of a single positive literal
and the body consists of one or more literals.
A fact is a clause that has an empty body thus having the form:
P.
11
Prolog Rules
A rule is a clause that has a head and a non-empty body.
The simplest form of a rule is the following:
P :- Q.
Examples of rules are:
parent(X,Y) :- child(Y,X).
% X is a parent of Y if
% Y is a child of X.
nice(DAY):- sunny(DAY),
not windy(DAY),
neighbour(X,Y) :- address(X, Street, Num),
address(Y, Street, Num1),
not equal(Num, Num1).
12
Prolog Symbols and Structures
p(X,Y) : predicate symbol p describes relationship between
arguments X and Y.
: Logical “and”.
: Logical “or”.
: Logical “not”.
: Terminator (same as ; in Pascal).
: Implication symbol (PQ) is written as (Q if P).
: “Cut” symbol, used to control backtracking to
make program more deterministic.
[]
: List symbol. Example: [1,2,3], [anne, arthur, ada].
[Head|Tail] : A format used for list manipulation where
Head is head of list and tail is tail of the list.
E.g. [1,2,3]: Head is 1 and Tail is [2,3].
,
;
not
.
:!
13
Lists





A list is a Prolog structure used to
represent an ordered sequence of items.
For example:
[prolog, miranda, lisp, clips]
[1,2,3,4,5,6,7,8,9,10]
[ [a,b], [a], [c], [] ]
A list with no elements is an empty list and is denoted as
[]. The empty list is a Prolog atom. A non-empty list
consists of a head and a tail. The head is the first element
of the list and the tail is the list of all the other elements.
14
List Examples





list
[1,2,3]
[ [a,b], [a], [c]]
[mon,tue,wed]
[a]
head
1
[a,b]
mon
a
tail
[2,3]
[[a],[c]]
[tue,wed]
[]


An empty list has no head and no tail.
15
sum_fr_zero_to_n(0,0).
sum_fr_zero_to_n(N,S):sum_fr_zero_to_n(N1,S1),
N is N1+1,
S is S1+N.
factorial(0,1).
factorial(N,R):factorial(N1,R1),
N is N1+1,
R is N*R1.
16
rev_print([]).
rev_print([H|R]):rev_print(R),
write(H), nl.
reverse([],[]).
reverse([H|T], L):reverse(T,R),
append(R,[H],L).
append([], L, L).
append([H|T], L, [H|T1]):append(T,L,T1).
17
del(X,[],[]).
del(X,[X|Y],Y):-!.
del(X,[Y|Z],[Y|W]):del(X,Z,W).
member(X,[X|Tail]).
member(X, [_Head|Tail]):member(X,Tail).
count([],0).
count([Head|Tail],Count):count(Tail,Tailcount),
Count is Tailcount + 1.
18
Backtracking
… very powerful
Suppose that we have developed
a knowledge base of:
boss(dick,harry).
boss(tom,dick).
boss(ann,mary).
boss(mary,harry).
and, query is made as:
?- boss(X,Y), boss(Y,Z).
19
Let see how backtracking in Prolog works
and get a feel of how “intelligent” Prolog as
a logic language.
 The first predicate expression in the query will match the
first fact in the database, with X=dick and Y= harry.
 Moving to the second predicate expression in the query,
the interpreter searches for a boss fact with harry as its first argument.
There is no such fact in the database, so the second expression in
the query fails.
 So the interpreter backtracks, returning to the first expression
to make another choice
(this happens every time a Prolog interpreter fails).
It now has to go backward to a point where there exists
a choice not explored yet. So now it uses the second fact
and sets X=tom and Y=dick.
20
 The old match for the second expression was from
the first fact, so mow it examines the second, third
and the fourth facts in order. Unfortunately, none have
dick as their first argument, so the expression fails.
 Now the interpreter returns to the first predicate
expression yet again. The first and the second facts
have been tried, so it uses the third fact and sets
X=ann and Y=mary.
 It succeeds again and Z=harry again.
21
 The interpreter goes to the second predicate expression,
and searches from the start of the database for a boss fact
where dick is the first argument. And, yes there is such a fact
(i.e. the first fact in the knowledge base).
 So Z=harry, and since we are at the end of the query,
the query succeeds.
Therefore tom is the super-boss.
The interpreter displays X=tom, Y=dick, Z=harry.
 If the user now types a semicolon,
the interpreter forces a failure and start backtracking.
The interpreter goes back to what it just finished,
the second expression of the query, and try to find a different
match.
22