Transcript PPT - CCS

Chương 3
Tri thức và lập luận
Nội dung chính chương 3
I.
Lecture 1
Lecture 2
Lecture 3,4
Logic – ngôn ngữ của tư duy
II. Logic mệnh đề (cú pháp, ngữ nghĩa,
sức mạnh biểu diễn, các thuật toán
suy diễn)
III. Prolog (cú pháp, ngữ nghĩa, lập trình
prolog, bài tập và thực hành)
IV. Logic cấp một (cú pháp, ngữ nghĩa,
sức mạnh biểu diễn, các thuật toán
suy diễn)
Lecture 2:
Prolog, Lập trình prolog
Lecture2-outline
I.
Cơ bản về Prolog, lập trình prolog
II. Suy diễn trong Prolog (kiểm tra,Suy diễn
lùi, đệ qui)
III. CUT và Phủ định
I. Cơ bản về ngôn ngữ Prolog,
lập trình prolog
27/09/04
AIPP Lecture 2: Prolog Fundamentals
5
Chương trình và thực hiện chương
trình trong prolog
• Program is a database of facts and rules.
– Some are always true (facts):
father( john, jim).
– Some are dependent on others being true (rules):
parent( Person1, Person2 ) :father( Person1, Person2 ).
• To run a program, we ask questions about
the database.
parent(john,jim).
parent(john,X).
16:10 23/09/04
Lecture 1: An Introduction
6
Prolog in English
Example Database:
John is the father of Jim.
Jane is the mother of Jim.
Jack is the father of John.
Person 1 is a parent of Person 2 if
Person 1 is the father of Person 2 or
Person 1 is the mother of Person 2.
Person 1 is a grandparent of Person 2 if
some Person 3 is a parent of Person 2 and
Person 1 is a parent of Person 3.
Example questions:
Who is Jim's father?
Is Jane the mother of Fred?
Is Jane the mother of Jim?
Does Jack have a grandchild?
16:10 23/09/04
Lecture 1: An Introduction
7
Prolog in Prolog
Example Database:
Example Database:
John is the father of Jim.
Jane is the mother of Jim.
Jack is the father of John.
father( john, jim ).
mother( jane, jim ).
father( jack, john ).
Person 1 is a parent of Person 2 if
Person 1 is the father of Person 2 or
Person 1 is the mother of Person 2.
parent( Person1, Person2 ) :father( Person1, Person2 ).
parent( Person1, Person2 ) :mother( Person1, Person2 ).
Person 1 is a grandparent of Person 2 if
some Person 3 is a parent of Person 2 and
Person 1 is a parent of Person 3.
grandparent( Person1, Person2 ) :parent( Person3, Person2 ),
parent( Person1, Person3 ).
Example questions:
Example questions:
Who is Jim's father?
Is Jane the mother of Fred?
Is Jane the mother of Jim?
Does Jack have a grandchild?
16:10 23/09/04
?- father( Who, jim ).
?- mother( jane, fred ).
?- mother( jane, jim ).
?- grandparent( jack, _ ).
Lecture 1: An Introduction
8
Cú pháp
• Prolog program consist of clauses.
• A clause has a head and a body (Rule) or just a
head (Fact).
• A head consists of a predicate name and
arguments.
• A clause body consists of a conjunction of terms.
• Terms can be constants, variables, or compound
terms.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
9
Clauses - Câu
• Prolog program consist of clauses.
A clause = An individual definition (whether it be a
fact or rule).
e.g.
mother(jane,alan). = Fact
parent(P1,P2):- mother(P1,P2). = Rule
head
body
• A clause consists of a head
• and sometimes a body.
– Facts don’t have a body because they are always
true.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
10
Predicate – Vị từ
• A predicate denotes a property or relationship
between objects
• ‘Predicate’ is the name given to the word
occurring before the bracket in a fact or rule:
parent(jane,alan).
Predicate name
• By defining a predicate you are specifying
which information needs to be known for the
property denoted by the predicate to be true.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
11
Arguments – Các tham số của vị từ
• A predicate head consists of a predicate name and
sometimes some arguments contained within
brackets and separated by commas.
mother(jane,alan).
Predicate name
Arguments
• A body can be made up of any number of subgoals
(calls to other predicates) and terms.
• Arguments also consist of terms, which can be:
– Constants e.g. jane,
– Variables e.g. Person1, or
– Compound terms (explained in later lectures).
27/09/04
AIPP Lecture 2: Prolog Fundamentals
12
Terms: Constants
Hạng thức hằng
Constants can either be:
• Numbers:
– integers are the usual form (e.g. 1, 0, -1, etc), but
– floating-point numbers can also be used (e.g. 3.0E7)
• Symbolic (non-numeric) constants:
– always start with a lower case alphabetic character and
contain any mixture of letters, digits, and underscores
(but no spaces, punctuation, or an initial capital).
• e.g. abc, big_long_constant, x4_3t).
• String constants:
– are anything between single quotes e.g. ‘Like this’.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
13
Terms: Variables
Hạng thức biến
• Variables always start with an upper case
alphabetic character or an underscore.
• Other than the first character they can be made up
of any mixture of letters, digits, and underscores.
e.g. X, ABC, _89two5, _very_long_variable
• There are no “types” for variables (or constants) – a
variable can take any value.
• All Prolog variables have a “local” scope:
– they only keep the same value within a clause; the same
variable used outside of a clause does not inherit the value
(this would be a “global” scope).
27/09/04
AIPP Lecture 2: Prolog Fundamentals
14
Naming tips – Một số qui ước khi
đặt các tên
• Use real English when naming predicates,
constants, and variables.
e.g.
Could be:
Not:
“John wants to help Somebody.”
wants(john,to_help,Somebody).
x87g(j,_789).
• Use a Verb Subject Object structure:
wants(john,to_help).
• BUT do not assume Prolog Understands the
meaning of your chosen names!
– You create meaning by specifying the body (i.e.
preconditions) of a clause.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
15
Using predicate definitions
Xây dựng vị từ
• Command line programming is tedious
e.g. | ?- write(‘What is your name?’), nl, read(X),
write(‘Hello ‘), write(X).
• We can define predicates to automate
commands:
greetings:write(‘What is your name?’),
nl,
read(X),
write(‘Hello ‘),
write(X).
Prolog Code
27/09/04
| ?- greetings.
What is your name?
|: tim.
Hello tim
X = tim ?
yes
AIPP Lecture 2: Prolog Fundamentals
Terminal
16
Using multiple clauses (Định nghĩa
vị từ bởi nhiều câu)
• Different clauses can be used to deal with
different arguments.
greet(hamish):write(‘How are you doin, pal?’).
greet(amelia):write(‘Awfully nice to see you!’).
= “Greet Hamish or Amelia” = a disjunction of goals.
| ?- greet(hamish).
How are you doin, pal?
yes
| ?- greet(amelia).
Awfully nice to see you!
yes
• Clauses are tried in order from the top of the file.
• The first clause to match succeeds (= yes).
27/09/04
AIPP Lecture 2: Prolog Fundamentals
17
Re-trying Goals – Câu truy vấn có
nhiều đáp số
• When a question is asked with a variable as an
argument (e.g. greet(Anybody).) we can ask the
Prolog interpreter for multiple answers using: ;
| ?- greet(Anybody).
How are you doin, pal?
Anybody = hamish? ;  “Redo that match.”
Anybody = amelia? ;  “Redo that match.”
no
 “Fail as no more matches.”
• This fails the last clause used and searches down
the program for another that matches.
• RETURN = accept the match
• ; = reject that match
27/09/04
AIPP Lecture 2: Prolog Fundamentals
18
Ordering of clauses (Thứ tự các câu
là quan trọng)
• The order of multiple clauses is important.
greet(Anybody):write('Hullo '), write(Anybody).
greet(hamish):write('How are you doin, pal?').
greet(amelia):write('Awfully nice to see you!').
| ?- greet(hamish).
Hullo hamish?
yes
• The most specific clause should always be at the top.
• General clauses (containing variables) at the bottom.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
19
Ordering of clauses (thứ tự các câu)
• The order of multiple clauses is important.
greet(hamish):write('How are you doin, pal?').
| ?- greet(hamish).
How are you doin,
pal?.
yes
greet(amelia):write('Awfully nice to see you!').
greet(Anybody):write('Hullo '), write(Anybody).
• The most specific clause should always be at the top.
• General clauses (containing variables) at the bottom.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
20
Unification (hợp nhất hai hạng thức)
• When two terms match we say that they unify.
– Their structures and arguments are compatible.
• This can be checked using =/2
|?- loves(john,X) = loves(Y,mary).
X = mary,
Y = john?
yes
 unification leads to instantiation

Terms that don’t unify
fred = jim.
‘Hey you’ = ‘Hey me’.
frou(frou) = f(frou).
foo(bar) = foo(bar,bar).
foo(N,N) = foo(bar,rab).
27/09/04
Terms that unify
Outcome
fred = fred.
yes.
‘Hey you’ = ‘Hey you’.
yes
fred=X.
X=fred.
X=Y.
Y = X.
foo(X) = foo(bar).
X=bar.
foo(N,N) = foo(bar,X). N=bar, X=bar.
foo(foo(bar)) = foo(X) X = foo(bar)
AIPP Lecture 2: Prolog Fundamentals
21
Asking questions of the database
Truy vấn cơ sở dữ liệu
We can ask about facts directly:
|?- mother(X,alan).
X = jane?
Yes
Or we can define rules that prove
if a property or relationship holds
given the facts currently in the
database.
mother(jane,alan).
father(john,alan).
parent(Mum,Child):mother(Mum,Child).
parent(Dad,Child):father(Dad,Child).
|?- parent(jane,X).
X = alan?
yes
27/09/04
AIPP Lecture 2: Prolog Fundamentals
22
Summary
•
•
•
•
•
•
Prolog program consist of clauses.
A clause has a head and a body (Rule) or just a head (Fact).
A head consists of a predicate name and arguments.
A clause body consists of a conjunction of terms.
Terms can be constants, variables, or compound terms.
We can set our program goals by typing a command that unifies
with a clause head.
• A goal unifies with clause heads in order (top down).
• Unification leads to the instantiation of variables to values.
• If any variables in the initial goal become instantiated this is
reported back to the user.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
23
II. Suy diễn trong prolog (kiểm
tra, suy diễn lùi, đệ qui)
27/09/04
AIPP Lecture 2: Prolog Fundamentals
24
Tests – Kiểm tra
• When we ask Prolog a question we are asking for
the interpreter to prove that the statement is true.
?- 5 < 7, integer(bob).
yes = the statement can be proven.
no = the proof failed because either
– the statement does not hold, or
– the program is broken.
Error = there is a problem with the question or program.
*nothing* = the program is in an infinite loop.
• We can ask about:
– Properties of the database: mother(jane,alan).
– Built-in properties of individual objects: integer(bob).
– Absolute relationships between objects:
• Unification: =/2
• Arithmetic relationships: <, >, =<, >=, =:=, +, -, *, /
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
25
Arithmetic Operators – Các phép toán số
• Operators for arithmetic and value comparisons are
built-in to Prolog
= always accessible / don’t need to be written
• Comparisons: <, >, =<, >=, =:= (equals), =\= (not equals)
= Infix operators: go between two terms.
=</2 is used
• 5 =< 7. (infix)
• =<(5,7). (prefix)  all infix operators can also be prefixed
• Equality is different from unification
=/2 checks if two terms unify
=:=/2 compares the arithmetic value of two expressions
?- X=Y.
yes
30/09/04
?- X=:=Y.
Instantiation error
?-X=4,Y=3, X+2 =:= Y+3.
X=4, Y=3? yes
AIPP Lecture 3: Rules, Results, and Backtracking
26
Arithmetic Operators (2)
• Arithmetic Operators: +, -, *, /
= Infix operators but can also be used as prefix.
– Need to use is/2 to access result of the arithmetic
expression otherwise it is treated as a term:
|?- X = 5+4.
X = 5+4 ?
yes
(Can X unify with 5+4?)
|?- X is 5+4.
X = 9 ?
yes
(What is the result of 5+4?)
• Mathematical precedence is preserved: /, *, before +,• Can make compound sums using round brackets
– Impose new precedence
– Inner-most brackets first
30/09/04
| ?- X is (5+4)*2.
5+4*2.
X = 13
18 ?
yes
AIPP Lecture 3: Rules, Results, and Backtracking
27
Tests within clauses – Các phép toán
bool trong các câu
• These operators can be used within the
body of a clause:
– To manipulate values,
sum(X,Y,Sum):Sum is X+Y.
–
To distinguish between clauses of a predicate definition
bigger(N,M):N < M, write(‘The bigger number is ‘), write(M).
bigger(N,M):N > M, write(‘The bigger number is ‘), write(N).
bigger(N,M):N =:= M, write(‘Numbers are the same‘).
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
28
Backtracking – Suy diễn lùi
|?- bigger(5,4).
bigger(N,M):N < M,
write(‘The bigger number is ‘), write(M).
bigger(N,M):N > M,
write(‘The bigger number is ‘), write(N).
bigger(N,M):N =:= M,
write(‘Numbers are the same‘).
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
29
Backtracking – Suy diễn lùi
|?- bigger(5,4).
Backtrack
bigger(5,4):5 < 4,  fails
write(‘The bigger number is ‘), write(M).
bigger(N,M):N > M,
write(‘The bigger number is ‘), write(N).
bigger(N,M):N =:= M,
write(‘Numbers are the same‘).
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
30
Backtracking – Suy diễn lùi
|?- bigger(5,4).
bigger(N,M):N < M,
write(‘The bigger number is ‘), write(M).
bigger(5,4):5 > 4,
write(‘The bigger number is ‘), write(N).
bigger(N,M):N =:= M,
write(‘Numbers are the same‘).
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
31
Backtracking – Suy diễn lùi
|?- bigger(5,4).
bigger(N,M):N < M,
write(‘The bigger number is ‘), write(M).
bigger(5,4):5 > 4,  succeeds, go on with body.
write(‘The bigger number is ‘), write(5).
The bigger number is 5
yes
|?-
30/09/04
Reaches full-stop
= clause succeeds
AIPP Lecture 3: Rules, Results, and Backtracking
32
Backtracking – Suy diễn lùi
|?- bigger(5,5).
 If our query only matches the final clause
bigger(N,M):N < M,
write(‘The bigger number is ‘), write(M).
bigger(N,M):N > M,
write(‘The bigger number is ‘), write(N).
bigger(5,5):5 =:= 5,  Is already known as the first two clauses failed.
write(‘Numbers are the same‘).
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
33
Backtracking – Suy diễn lùi
|?- bigger(5,5).
 If our query only matches the final clause
bigger(N,M):N < M,
write(‘The bigger number is ‘), write(M).
bigger(N,M):N > M,
write(‘The bigger number is ‘), write(N).
bigger(5,5): Satisfies the same conditions.
write(‘Numbers are the same‘).
Numbers are the same
yes
Clauses should be ordered according to specificity
Most specific at top
Universally applicable at bottom
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
34
Satisfying Subgoals – Đích trung gian
• Most rules contain calls to other predicates in their
body. These are known as Subgoals.
• These subgoals can match:
– facts,
– other rules, or
– the same rule = a recursive call
1) drinks(alan,beer).
2) likes(alan,coffee).
3) likes(heather,coffee).
4) likes(Person,Drink):drinks(Person,Drink).  a different subgoal
5) likes(Person,Somebody):likes(Person,Drink),
 recursive subgoals
likes(Somebody,Drink). 
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
35
Representing Proof using Trees
Cây biểu diễn chứng minh
To help us understand Prolog’s proof strategy we can
represent its behaviour using AND/OR trees.
1. Query is the top-most point (node) of the tree.
2. Tree grows downwards (looks more like roots!).
3. Each branch denotes a subgoal.
1.
The branch is labelled with the number of the matching clause and
2.
any variables instantiated when matching the clause head.
4. Each branch ends with either:
1. A successful match
2. A failed match
, or
3. Another subgoal.
|?- likes(alan,X).
,
2
X/coffee
1st solution
= “Alan likes coffee.”
X = coffee
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
36
Representing Proof using Trees (2)
• Using the tree we can see what happens when we ask
for another match ( ; )
|?- likes(alan,X).
Backtracking
2
X/coffee
4
X = coffee
drinks(alan,X).
1st match is failed
and forgotten
1
X/beer
X = beer
2nd solution
= “Alan likes beer because Alan drinks beer.”
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
37
Recursion using Trees
Cây đệ qui
• When a predicate calls itself within its body we say
the clause is recursing
|?- likes(alan,X).
Conjoined subgoals
2
X/coffee
X = coffee
4
5
drinks(alan,X). likes(alan,Drink)
likes(Somebody,Drink)
1
X/beer
X/coffee 2
X = beer
X = coffee
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
38
Recursion using Trees (2)
• When a predicate calls itself within its body we say
the clause is recursing
|?- likes(alan,X).
2
X/coffee
X = coffee
4
5
drinks(alan,X). likes(alan,coffee)
likes(Somebody,coffee)
1
X/beer
X/coffee 2
Somebody 2
/alan
X = beer
X = coffee
Somebody = alan
3rd solution = “Alan likes Alan because Alan likes coffee.”
30/09/04
AIPP Lecture 3: Rules, Results, and Backtracking
39
Recursion using Trees (3)
• When a predicate calls itself within its body we say
the clause is recursing
|?- likes(alan,X).
2
X/coffee
X = coffee
5
4
drinks(alan,X).
1
likes(alan,coffee)
X/beer
X/coffee
X = beer
4th
solution =
“Alan likes Heather
because Heather likes coffee.”
30/09/04
2
likes(Somebody,coffee)
Somebody
/alan
X = coffee
Somebody
= alan
AIPP Lecture 3: Rules, Results, and Backtracking
Somebody
3 / heather
2
Somebody
= heather
40
Infitite Recursive Loop
• If a recursive clause is called with an incorrect goal it will loop
as it can neither prove it
nor disprove it.
likes(Someb,coffee)
Somebody
= alan
2
3
5
likes(Someb,coffee)
2
Somebody
= heather
likes(coffee,coffee)
Someb = alan
likes(coffee,X)
likes(coffee,X2)
likes(coffee,X3)
30/09/04
likes(coffee,X)
likes(X,X2)
likes(X2,X3)
AIPP Lecture 3: Rules, Results, and Backtracking
41
II. CUT và phủ định và findall
27/09/04
AIPP Lecture 2: Prolog Fundamentals
42
CUT
a(X, Y) :- b(X), !, c(Y).
b(1). b(2). b(3).
c(1). c(2). c(3).
-----------------Kết quả truy vấn thế nào?
?- a(Q, R).
Q = 1,
R=1;
Q = 1,
R=2;
Q = 1,
R = 3.
Tai sao?
27/09/04
AIPP Lecture 2: Prolog Fundamentals
43
CUT
a(X) :- b(X), !, c(X).
b(1). b(2). b(3).
c(2).
---------------------?- a(Q).
false.
?- a(2).
true.
Tại sao?
27/09/04
AIPP Lecture 2: Prolog Fundamentals
44
Green Cuts ! (Sử dụng CUT khi nào?)
f(X,0):- X < 3, !.
f(X,1):- 3 =< X, X < 6, !.
f(X,2):- 6 =< X.
If you reach this point don’t
bother trying any other clause.
|?- trace, f(2,N).
1
1 Call: f(2,_487) ?
2
2 Call: 2<3 ?
2
2 Exit: 2<3 ? ?
1
1 Exit: f(2,0) ?
N=0?;
no
• Notice that the answer is still the same, with or without the cut.
– This is because the cut does not alter the logical behaviour of the
program.
– It only alters the procedural behaviour: specifying which goals get
checked when.
•
•
This is called a green cut. It is the correct usage of a cut.
Be careful to ensure that your clauses are actually mutually
exclusive when using green cuts!
14/10/04
AIPP Lecture 7: The Cut
45
Red Cuts ! (Không sử dụng CUT khi nào?)
f(X,0):- X < 3, !.
f(X,1):- 3 =< X, X < 6, !.
f(X,2):- 6 =< X.
Redundant?
| ?- f(7,N).
1
1 Call: f(7,_475) ?
2
2
Call: 7<3 ?
2
2 Fail: 7<3 ?
3
2 Call: 3=<7 ?
3
2
Exit: 3=<7 ?
4
2 Call: 7<6
?
4
2 Fail: 7<6 ?
5
2 Call: 6=<7 ?
5
2 Exit:
6=<7 ?
1
1 Exit: f(7,2) ?
N=2?
yes
• Because the clauses are mutually exclusive and ordered
we know that once the clause above fails certain
conditions must hold.
• We might want to make our code more efficient by
removing superfluous tests.
14/10/04
AIPP Lecture 7: The Cut
46
Phủ định
parents(a,b).
parents(c,d).
parents(b,c).
parents(a,e).
nochild(X):- \+ parents(X,_).
-----------------------?- parents(f,X).
false.
?- nochild(a).
false.
?- nochild(e).
true.
27/09/04
\+ X means not(X) that
is the way to implement
negation in Prolog;
however not(X) does
not mean that X is false,
it means that X can't be
proved true from the
database.
AIPP Lecture 2: Prolog Fundamentals
47
Phủ định (tiếp)
• Kiểm tra một số có là nguyên tố?.
is_prime(2).
is_prime(3).
is_prime(P):-integer(P), P>3, P mod 2 =\= 0, \+ has_factor(P,3).
has_factor(P,N):- P mod N =:=0.
has_factor(P,N):- L is N+2, L*L<P, has_factor(P,L).
-----------------------?- is_prime(97).
true.
?- is_prime(18).
false.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
48
findall
parents(a,b).
parents(c,d).
parents(b,c).
parents(a,e).
--------------Sử dụng dấu “;” nếu muốn
?- parents(a,X).
Prolog in các kết quả khác
X=b;
X = e.
?- findall(X,parents(a,X),F).
Vị từ xây dựng sẵn trong
Prolog cho phép tìm tập F
F = [b, e]
?- findall([X,Y],parents(X,Y),F).
F = [[a, b], [c, d], [b, c], [a, e]].
27/09/04
gồm tất cả các X thỏa mãn
parents(a,X).
AIPP Lecture 2: Prolog Fundamentals
49
Bài tập chữa trên lớp
1. Tim phan tu cuoi cung cua mot danh sach.
Chu y: [X|R]: X la 1 phan tu, R la 1 list.
2. Hoanvi
3. Sap xep danh sach
4. Giai phuong trinh bac nhat
5. Hop va giao 2 tap hop.
6. Thay the 1 ky tu boi 1 ky tu khac trong danh sach
7. Trich xau con tu vi tri K den L cua mot xau.
8. Tim thua so chung lon nhat 2 so
9. Do thi va tim duong di trong do thi.
27/09/04
AIPP Lecture 2: Prolog Fundamentals
50