K thut lp trình Prolog 129
hn, thay vì s dng cp ôi cut-fail, ngi ta s dng not. Tuy nhiên, phép ph
nh not c#ng không phi không gây ra nhng phin phc cho ngi dùng.
Nhiu khi s dng not không hoàn toàn chính xác vi phép ph nh trong Toán
hc. Ch ng hn n!u trong chng trình có nh ngha quan h man, mà ta a ra
mt câu h+i i loi nh :
?- not( man( marie)).
Khi ó, Prolog s- tr li No n!u ã có nh ngha man( marie), tr li Yes
n!u cha có nh ngha nh vy. Tuy nhiên, khi tr li No, không phi Prolog nói
r$ng «Marie không phi là mt ngi», mà nói r$ng «Không tìm thy trong
chng trình thông tin  chng minh Marie là mt ngi». Khi th,c hin phép
not, Prolog không chng minh tr,c ti!p mà tìm cách chng minh iu ngc li.
N!u chng minh c, Prolog suy ra r$ng ích not thành công. Cách lp lun
nh vy c gi là gi thuyt v th gii khép kín (hypothesis of the enclosed
world). Theo gi thuy!t này, th! gii khép kín có ngha là nhng gi tn ti (úng)
u n$m trong chng trình hoc c suy ra t' chng trình. Nhng gì không
n$m trong chng trình, hoc không th suy ra t' chng trình, thì s- là không
úng (sai), hay iu ph nh là úng. Vì vy, cn chú ý khi s dng ph nh do
thông thng, ngi ta ã không gi thi!t r$ng th! gii là khép kín. Trong
chng trình, do thi!u khai báo mnh  :
man( marie).
nên Prolog không chng minh c r$ng Marie là mt ngi.
Sau ây là mt ví d khác s dng phép ph nh not :
r( a).
q( b).
p( X ) :- not( r( X )).
N!u t câu h+i :
?- q( X ), p( X ).
thì Prolog s- tr li :
X=b
Yes
Nhng n!u t câu h+i :
?- p( X ), q( X ).
thì Prolog s- tr li :
No
) hiu c vì sao cùng mt chng trình nhng vi hai cách t câu h+i
khác nhau li có hai cách tr li khác nhau, ta cn tìm hiu cách Prolog lp lun.
130 Lp trình lägich trong Prolog
Trong trng hp th nht, bi!n X c ràng buc giá tr là b khi th,c hin ích
q( X ). Ti!p tc th,c hin ích con p( X ), nh ràng buc X=b, ích not(
r( X )) tho mãn vì ích r( b ) không tho mãn, Prolog tr li Yes.
Trái li trong trng hp th hai, do Prolog th,c hin ích con p( X ) trc
nên s, tht bi ca not( r( X )), tc r( X ) thành công vi ràng buc X=a,
d0n !n câu tr li No.
 GE"
Kiu d liu cu trúc, danh sách, k1 thut so khp, quay lui và nhát ct là
nhng im mnh trong lp trình Prolog. Chng này s- ti!p tc trình bày mt s
ví d tiêu biu v :
Truy cp thông tin cu trúc t' mt c s d liu.
Mô ph+ng mt ôtômat hu hn không n nh và máy Turing.
Lp k! hoch i du lch
Bài toán tám quân hu
)ng thi, ta c#ng trình bày cách Prolog tr'u tng hoá d liu.
' JyL1T"-#VUN
Sau ây là mt ví d cho phép biu din và thao tác các d liu cu trúc. T'
ó, ta c#ng hiu cách s dng Prolog nh mt ngôn ng truy vn c s d liu.
Trong Prolog, mt c s c biu din di dng mt tp hp các s, kin.
Ch ng hn, mt c s d liu v các gia ình s- mô t mi gia ình (family)
nh mt mnh . Mi gia ình s- gm ba phn t ln lt : chng, v
(individual) và các con (children). Do các phn t này thay (i tuy theo
t'ng gia ình, nên các con s- c biu din bi mt danh sách  có th nhn
c mt s lng tu ý s con. Mi ngi trong gia ình c biu din bi
bn thành phn : tên, h, ngày tháng n&m sinh và vic làm. Thành phn vic làm
có th có giá tr “tht nghip” (inactive), hoc ch" rõ tên c quan công tác và
thu nhp theo n&m.
Gi s c s d liu cha mnh  u tiên nh sau :
family(
individual( tom, smith, date(7, may, 1960),
work(microsoft, 30000) ),
individual( ann, smith, date(9, avril, 1962),
inactive),
[ individual( roze, smith, date(16, june, 1991),
inactive),
individual( eric, smith, date(23, march, 1993),
inactive) ] ).
K thut lp trình Prolog 131
D liu v nhng gia ình khác ti!p tc c b( sung di dng các mnh
tng t,. Hình 5.1 di ây minh ho cách t( chc c s d liu.
Prolog là mt ngôn ng rt thích hp cho vic khôi phc thông tin : ngi s
dng có th gi các i tng mà không nht thi!t ch" rõ tt c các thành phn.
Ngi s dng ch" cn ch" ra cu trúc ca các i tng mà h quan tâm mt
cách t,ng trng, không cn phi ch" ra h!t. Hình 1.2 minh ho nhng cu trúc
nh vy. Ví d,  biu din nhng gia ình dòng h Smith, trong Prolog vi!t :
family( individual( _ , smith, _ , _ ), _ , _ )
Hình II.1. Cu trúc cây biu din thông tin v mt gia ình
Hình II.2. tính cht cu trúc ca các i tưng Prolog cho phép biu din :
(a) mt gia ình Smith nào ó ; (b) nhng gia ình có úng ba con ; (c) nhng gia ình
family
individual individual .
tom smith date work ann smith date inactive children
.
7 may 1960 microsoft 30000 9 avril 1962 roze smith
date inactive children [ ]
16 june 1991 eric smith date
inactive
(a) family
individual _ _
_ bob _ _
(b) family
_ _ .
_ .
_ .
_ [ ]
(c) family
_ individual .
Firstname Lastname _ _ _ .
_ .
_ _
132 Lp trình lägich trong Prolog
có ít nht ba con. Riêng trưng hp (c) còn cho phép biu din tên ca ngưi v nh s
ràng buc các bin Firstname và Lastname.
Nhng du gch di dòng nh ã bi!t là các bi!n nc danh, ngi s dng
không cn quan tâm !n giá tr ca chúng. Mt cách tng t,, nhng gia ình có
ba con c biu din bi :
family( _ , _ , [ _ , _ , _ ] )
Ta c#ng có th t câu h+i tìm nhng ngi v trong nhng gia ình có ít
nht ba con :
?- family( _ , individual( Firstname, Lastname, _ , _
), [ _ , _ , _ | _ ] ).
Nhng ví d trên ây ch" ra r$ng ta có th biu din các i tng bi cu
trúc ca chúng mà không cn quan tâm !n ni dung, b$ng cách b+ qua nhng
tham i vô nh.
Sau ây là mt s mnh  c a thêm vào c s d liu các gia ình 
có th t các câu h+i vn tin khác nhau (có th b( sung thêm các gia ình mi bi
mnh  family) :
husban( X ) :- % X là mt ngi chng
family( X , _ , _ ).
wife( X ) :- % X là mt ngi v
family( _, X , _ ).
chidren( X ) :- % X là mt ngi con, chú ý các tên bi!n ch hoa
family( _, _ , Chidren ),
ismember( X, Chidren ).
ismember( X, [ X | L ] ). % có th s dng mnh  member ca
Prolog
ismember( X, [ Y | L ] ) :-
ismember( X, L ).
exist( Individual ) :- % mi thành viên ca gia ình
husban( Individual ) ;
wife( Individual ) ;
chidren( Individual ).
dateofbirth( individual( _ , _, Date , _ ), Date ).
salary( individual( _ , _, _ , work( _ , S ) ), S ). %
thu nhp ca ngi lao ng
salary( individual( _ , _, _ , inactive ), 0 ). % ngi
không có ngun thu nhp
Bây gi ta có th t các câu h+i nh sau :
1. Tìm tên h ca nhng ngi có mt trong c s d liu :
K thut lp trình Prolog 133
?- exist( individual( Firstname, Lastname, _ , _ ) ).
2. Tìm nhng ngi con sinh n&m 1991 :
?- chidren( X ), dateofbirth( X, date( _ , _ , 1991 )
).
3. Tìm nhng ngi v có vic làm :
?- wife( individual( Firstname, Lastname, _ , work( _
, _ ) ) ).
4. Tìm nhng ngi không có vic làm sinh trc n&m 1975 :
?- exist( individual(
Firstname, Lastname, date( _ , _ , Year ), inactive
) ),
Year < 1975.
5. Tìm nhng ngi sinh trc n&m 1975 có thu nhp di 10000 :
?- exist( Individual ),
dateofbirth( Individual, date( _ , _ , Year ) ),
Year < 1975,
salary( Individual, Salary ),
Salary < 10000.
6. Tìm nhng gia ình có ít nht ba con :
?- family( individual( _, Name, _ , _ ), _, [ _, _, _
| _ ] ).
) tính t(ng thu nhp ca mt gia ình, ta có th nh ngha mt quan h nh
phân cho phép tính t(ng các thu nhp ca mt danh sách nhng ngi ang có
vic làm dng :
total( List_of_ individual, Sum_of_ salary )
Ta vi!t trong Prolog nh sau :
total( [ ], 0 ) % danh sách rng
total( [ Individual | List ], Sum ) :-
salary( Individual, S ), % S là thu nhp ca ngi u tiên
total( List, Remain ), % Remain là thu nhp ca tt c nhng
ngi còn li
Sum is S + Remain.
Nh vy, t(ng thu nhp ca mt gia ình c tính bi câu h+i :
?- family( Husban, Wife, Chidren ),
total( [ Husban, Wife | Chidren ], Income ).
Các phiên bn Prolog u có th tính  dài (length) ca mt danh sách
(xem mc III chng 1 trc ây, ta c#ng ã tìm cách xây d,ng quan h này).