Lập trình Prolog_chương 1-2-3
Prolog là ngôn ngữ được sử dụng phổ biến nhất trong dòng các ngôn ngữ lập trình logic ( Prolog có nghĩa là Programming in logic). Ngôn ngữ Prolog do giáo sư người Pháp Alain colmerauer in logic.
LÅÌI NOÏI ÂÁÖU
Cuäún saïch naìy nhàòm cung cáúp cå såí lyï thuyãút vaì caïc phæång phaïp
láûp trçnh cå baín nháút cuía män hoüc «Láûp trçnh lägich» (Programming in Logic).
Ngæåìi âoüc seî âæåüc laìm quen våïi mäüt säú kyî thuáût láûp trçnh lägich âæåüc æïng duûng
tæång âäúi phäø biãún vaì chuí yãúu trong lénh væûc trê tuãû nhán taûo (Artificial
Intelligence) nhæ cäng nghãû xæí lyï tri thæïc, maïy hoüc, hãû chuyãn gia, xæí lyï ngän
ngæî tæû nhiãn, troì chåi, v.v...
Cuäún saïch gäöm nàm chæång vaì phuû luûc nhæ sau :
− Chæång 1 giåïi thiãûu ngän ngæî láûp trçnh Prolog lägich dæûa trãn lägich
Horn (Horn logic). Ngæåìi âoüc laìm quen våïi caïc kiãøu dæî liãûu cuía Prolog,
khaïi niãûm vãö luáût, sæû kiãûn vaì viãút caïc chæång trçnh Prolog âån giaín.
− Chæång 2 trçnh baìy caïc mæïc nghéa khaïc nhau cuía mäüt chæång trçnh
Prolog : nghéa lägich, nghéa khai baïo vaì nghéa thuí tuûc, caïch Prolog traí
låìi caïc cáu hoíi, caïch laìm thoaí maîn âêch.
− Chæång 3 trçnh baìy caïc pheïp toaïn säú hoüc, pheïp so saïnh vaì âënh nghéa
haìm sæí duûng pheïp âãû quy trong Prolog.
− Chæång 4 trçnh baìy cáúu truïc danh saïch vaì caïc pheïp xæí lyï cå baín trãn
danh saïch cuía Prolog.
− Chæång 5 trçnh baìy kyî thuáût láûp trçnh náng cao våïi Prolog.
− Pháön phuû luûc giåïi thiãûu ngän ngæî láûp trçnh SWI-Prolog, hæåïng dáùn
caïch caìi âàût sæí duûng pháön mãöm naìy vaì mäüt säú chæång trçnh vê duû tiãu
biãøu viãút trong SWI Prolog.
Cuäún saïch naìy duìng laìm giaïo trçnh cho sinh viãn ngaình Tin hoüc vaì caïc
âäüc giaí muäún tçm hiãøu thãm vãö kyî thuáût láûp trçnh cho lénh væûc trê tuãû nhán taûo.
Trong quaï trçnh biãn soaûn, taïc giaí âaî nháûn âæåüc tæì caïc baûn âäöng nghiãûp
nhiãöu âoïng goïp bäø êch vãö màût chuyãn män, nhæîng âäüng viãn khêch lãû vãö màût
tinh tháön, sæû giuïp âåî vãö biãn táûp âãø cuäún saïch âæåüc ra âåìi. Taïc giaí xin âæåüc
baìy toí loìng biãút ån sáu sàõc. Taïc giaí cuîng chán thaình caím ån moüi yï kiãún phã
bçnh âoïng goïp cuía baûn âoüc gáön xa vãö näüi dung cuía cuäún saïch naìy.
Âaì Nàông, ngaìy 27/05/2004
Taïc giaí.
MUÛC LUÛC
CHÆÅNG 1 MÅÍ ÂÁÖU VÃÖ NGÄN NGÆÎ PROLOG................................. 1
I. GIÅÏI THIÃÛU NGÄN NGÆÎ PROLOG ........................................ 1
I.1. Prolog laì ngän ngæî láûp trçnh lägich ........................................... 1
I.2. Cuï phaïp Prolog........................................................................... 2
I.2.1. Caïc thuáût ngæî ............................................................................. 2
I.2.2. Caïc kiãøu dæî liãûu Prolog .............................................................. 3
I.2.3. Chuï thêch .................................................................................... 4
II. CAÏC KIÃØU DÆÎ LIÃÛU SÅ CÁÚP CUÍA PROLOG......................... 5
II.1. Caïc kiãøu hàòng (træûc kiãûn) .......................................................... 5
II.1.1. Kiãøu hàòng säú ............................................................................... 5
II.1.2. Kiãøu hàòng lägich......................................................................... 5
II.1.3. Kiãøu hàòng chuäùi kyï tæû ................................................................ 5
II.1.4. Kiãøu hàòng nguyãn tæí .................................................................. 5
II.2. Biãún ............................................................................................. 6
III. SÆÛ KIÃÛN VAÌ LUÁÛT TRONG PROLOG .................................... 6
III.1. Xáy dæûng sæû kiãûn ........................................................................ 6
III.2. Xáy dæûng luáût ........................................................................... 10
III.2.1. Âënh nghéa luáût ........................................................................ 10
III.2.2. Âënh nghéa luáût âãû quy ............................................................ 15
III.2.3. Sæí duûng biãún trong Prolog ....................................................... 18
IV. KIÃØU DÆÎ LIÃÛU CÁÚU TRUÏC CUÍA PROLOG ......................... 19
IV.1. Âënh nghéa kiãøu cáúu truïc cuía Prolog ....................................... 19
IV.2. So saïnh vaì håüp nháút caïc haûng ................................................. 22
CHÆÅNG 2 NGÆÎ NGHÉA CUÍA CHÆÅNG TRÇNH PROLOG ..........31
I. QUAN HÃÛ GIÆÎA PROLOG VAÌ LÄGICH TOAÏN HOÜC .......... 31
II. CAÏC MÆÏC NGHÉA CUÍA CHÆÅNG TRÇNH PROLOG .......... 32
II.1. Nghéa khai baïo cuía chæång trçnh Prolog................................. 33
II.2. Khaïi niãûm vãö goïi mãûnh âãö ....................................................... 34
i
II.3. Nghéa lägich cuía caïc mãûnh âãö.................................................. 35
II.4. Nghéa thuí tuûc cuía Prolog ......................................................... 37
II.5. Täø håüp caïc yãúu täú khai baïo vaì thuí tuûc ..................................... 47
III. VÊ DUÛ : CON KHÈ VAÌ QUAÍ CHUÄÚI ....................................... 48
III.1. Phaït biãøu baìi toaïn .................................................................... 48
III.2. Giaíi baìi toaïn våïi Prolog............................................................ 49
III.3. Sàõp âàût thæï tæû caïc mãûnh âãö vaì caïc âêch .................................. 54
III.3.1. Nguy cå gàûp caïc voìng làûp vä haûn ............................................. 54
III.3.2. Thay âäøi thæï tæû mãûnh âãö vaì âêch trong chæång trçnh ............. 56
CHÆÅNG 3 CAÏC PHEÏP TOAÏN VAÌ SÄÚ HOÜC .......................................65
I. SÄÚ HOÜC .................................................................................... 65
I.1. Caïc pheïp toaïn säú hoüc ................................................................ 65
I.2. Biãøu thæïc säú hoüc ....................................................................... 65
I.3. Âënh nghéa caïc pheïp toaïn trong Prolog ................................... 68
II. CAÏC PHEÏP SO SAÏNH CUÍA PROLOG .................................... 73
II.1. Caïc pheïp so saïnh säú hoüc ........................................................... 73
II.2. Caïc pheïp so saïnh haûng............................................................. 75
II.3. Vë tæì xaïc âënh kiãøu ................................................................... 77
II.4. Mäüt säú vë tæì xæí lyï haûng ............................................................ 77
III. ÂËNH NGHÉA HAÌM ................................................................. 79
III.1. Âënh nghéa haìm sæí duûng âãû quy.............................................. 79
III.2. Täúi æu pheïp âãû quy................................................................... 87
III.3. Mäüt säú vê duû khaïc vãö âãû quy..................................................... 88
III.3.1. Tçm âæåìng âi trong mäüt âäö thë coï âënh hæåïng ........................ 88
III.3.2. Tênh âäüü daìi âæåìng âi trong mäüt âäö thë .................................... 89
III.3.3. Tênh gáön âuïng caïc chuäùi .......................................................... 90
CHÆÅNG 4 CÁÚU TRUÏC DANH SAÏCH.................................................95
I. BIÃØU DIÃÙN CÁÚU TRUÏC DANH SAÏCH .................................. 95
II. MÄÜT SÄÚ VË TÆÌ XÆÍ LYÏ DANH SAÏCH CUÍA PROLOG ........... 98
III. CAÏC THAO TAÏC CÅ BAÍN TRÃN DANH SAÏCH .................... 99
III.1. Xáy dæûng laûi mäüt säú vë tæì coï sàôn ............................................. 99
III.2. Hoaïn vë ................................................................................... 107
ii
III.3. Mäüt säú vê duû vãö danh saïch...................................................... 109
CHÆÅNG 5 KYÎ THUÁÛT LÁÛP TRÇNH PROLOG ..............................117
I. NHAÏT CÀÕT ............................................................................. 117
I.1. Khaïi niãûm nhaït càõt ................................................................ 117
I.2. Kyî thuáût sæí duûng nhaït càõt ..................................................... 118
I.3. Pheïp phuí âënh ........................................................................ 126
II. SÆÍ DUÛNG CAÏC CÁÚU TRUÏC .................................................. 131
II.1. Truy cáûp thäng tin cáúu truïc tæì mäüt cå såí dæî liãûu .................. 132
II.2. Træìu tæåüng hoaï dæî liãûu .......................................................... 136
II.3. Mä phoíng ätämat hæîu haûn ..................................................... 138
II.4. Vê duû : láûp kãú hoaûch âi du lëch bàòng maïy bay ....................... 144
II.5. Baìi toaïn taïm quán háûu .......................................................... 150
III. QUAÏ TRÇNH VAÌO-RA VAÌ LAÌM VIÃÛC VÅÏI TÃÛP .................. 163
III.1. Khaïi niãûm ............................................................................... 163
III.2. Laìm viãûc våïi caïc tãûp ................................................................ 164
III.3. ÆÏng duûng chãú âäü laìm viãûc våïi caïc tãûp .................................... 172
PHUÛ LUÛC A MÄÜT SÄÚ CHÆÅNG TRÇNH PROLOG..........................187
PHUÛ LUÛC B HÆÅÏNG DÁÙN SÆÍ DUÛNG SWI-PROLOG .....................194
I. GIÅÏI THIÃUU SWI-PROLOG............................................... 194
II. LAIM VIÃUC VÅÏI SWI-PROLOG......................................... 195
II.1. Âàût cáu hoíi .............................................................................. 195
II.2. Chaûy trçnh demo..................................................................... 196
II.3. Chaûy trçnh demo XPCE ......................................................... 197
II.4. Caïc lãûnh âån (Menu commands)............................................ 198
II.5. Soaûn thaío chæång trçnh.......................................................... 200
III. MÄÜT SÄÚ LÃÛNH SWI-PROLOG THÄNG DUÛNG.................. 201
TAÌI LIÃÛU THAM KHAÍO ............................................................................ 203
iii
CHÆÅNG 1
Måí âáö u vãö ngän ngæî Prolog
« A program is a theory (in some logic)
and computation is deduction from the theory »
J. A. Robinson
« Program = data structure + algorithm »
N. Wirth
« Algorithm = logic + control »
R. Kowalski
I. Giåïi thiãûu ngän ngæî Prolog
I.1. Prolog laì ngän ngæî láûp trçnh lägich
P rolog laì ngän ngæî âæåüc sæí duûng phäø biãún nháút trong doìng caïc ngän
ngæî láûp trçnh lägich (Prolog coï nghéa laì PROgramming in LOGic).
Ngän ngæî Prolog do giaïo sæ ngæåìi Phaïp Alain Colmerauer vaì nhoïm
nghiãn cæïu cuía äng âãö xuáút láön âáöu tiãn taûi træåìng Âaûi hoüc Marseille âáöu
nhæîng nàm 1970. Âãún nàm 1980, Prolog nhanh choïng âæåüc aïp duûng räüng raîi
åí cháu Áu, âæåüc ngæåìi Nháût choün laìm ngän ngæî phaït triãøn doìng maïy tênh
thãú hãû 5. Prolog âaî âæåüc caìi âàût trãn caïc maïy vi tênh Apple II, IBM-PC,
Macintosh.
Prolog coìn âæåüc goüi laì ngän ngæî láûp trçnh kyï hiãûu (symbolic programming)
tæång tæû caïc ngän ngæî láûp trçnh haìm (functional programming), hay láûp trçnh phi
säú (non-numerical programming). Prolog ráút thêch håüp âãø giaíi quyãút caïc baìi toaïn
liãn quan âãún caïc âäúi tæåüng (object) vaì mäúi quan hãû (relation) giæîa chuïng.
Prolog âæåüc sæí duûng phäø biãún trong lénh væûc trê tuãû nhán taûo. Nguyãn lyï
láûp trçnh lägich dæûa trãn caïc mãûnh âãö Horn (Horn logêc). Mäüt mãûnh âãö Horn
biãùu diãùn mäüt sæû kiãûn hay mäüt sæû viãûc naìo âoï laì âuïng hoàûc khäng âuïng, xaíy
ra hoàûc khäng xaíy ra (coï hoàûc khäng coï, v.v...).
1
2 Láûp trçnh logic trong Prolog
Vê duû I.1 : Sau âáy laì mäüt säú mãûnh âãö Horn :
1. Nãúu mäüt ngæåìi giaì maì (vaì) khän ngoan thç ngæåìi âoï haûnh phuïc.
2. Jim laì ngæåìi haûnh phuïc.
3. Nãúu X laì cha meû cuía Y vaì Y laì cha meû cuía Z thç X laì äng cuía Z.
4. Tom laì äng cuía Pat.
5. Táút caí moüi ngæåìi âãöu chãút (hoàûc Nãúu ai laì ngæåìi thç ai âoï phaíi chãút).
6. Socrat laì ngæåìi.
Trong caïc mãûnh âãö Horn åí trãn, caïc mãûnh âãö 1, 3, 5 âæåüc goüi laì caïc luáût
(rule), caïc mãûnh âãö coìn laûi âæåüc goüi laì caïc sæû kiãûn (fact). Mäüt chæång trçnh
lägich coï thãø âæåüc xem nhæ laì mäüt cå såí dæî liãûu gäöm caïc mãûnh âãö Horn, hoàûc
daûng luáût, hoàûc daûng sæû kiãûn, chàóng haûn nhæ táút caí caïc sæû kiãûn vaì luáût tæì 1
âãún 6 åí trãn. Ngæåìi sæí duûng (NSD) goüi chaûy mäüt chæång trçnh lägich bàòng
caïch âàût cáu hoíi (query/ question) truy váún trãn cå såí dæî liãûu naìy, chàóng
haûn cáu hoíi :
Socrat coï chãút khäng ?
(tæång âæång khàóng âënh Socrat chãút âuïng hay sai ?)
Mäüt hãû thäúng lägich seî thæûc hiãûn chæång trçnh theo caïch «suy luáûn»-tçm
kiãúm dæûa trãn väún «hiãøu biãút» âaî coï laì chæång trçnh - cå såí dæî liãûu, âãø minh
chæïng cáu hoíi laì mäüt khàóng âënh, laì âuïng (Yes) hoàûc sai (No). Våïi cáu hoíi
trãn, hãû thäúng tçm kiãúm trong cå såí dæî liãûu khàóng âënh Socrat chãút vaì «tçm
tháúy» luáût 5 thoaí maîn (vãú thç). Váûn duûng luáût 5, hãû thäúng nháûn âæåüc Socrat
laì ngæåìi (vãú nãúu) chênh laì sæû kiãûn 5. Tæì âoï, cáu traí låìi seî laì :
Yes
coï nghéa Socrat chãút laì âuïng.
I.2. Cuï phaïp Prolog
I.2.1. Caïc thuáût ngæî
Mäüt chæång trçnh Prolog laì mäüt cå såí dæî liãûu gäöm caïc mãûnh âãö (clause).
Mäùi mãûnh âãö âæåüc xáy dæûng tæì caïc vë tæì (predicat). Mäüt vë tæì laì mäüt phaït
biãøu naìo âoï vãö caïc âäúi tæåüng coï giaï trë chán âuïng (true) hoàûc sai (fail). Mäüt vë
tæì coï thãø coï caïc âäúi laì caïc nguyãn lägich (logic atom).
Måí âáöu vãö ngän ngæî Prolog 3
Mäùi nguyãn tæí (noïi goün) biãøu diãùn mäüt quan hãû giæîa caïc haûng (term).
Nhæ váûy, haûng vaì quan hãû giæîa caïc haûng taûo thaình mãûnh âãö.
Haûng âæåüc xem laì nhæîng âäúi tæåüng “dæî liãûu” trong mäüt trçnh Prolog.
Haûng coï thãø laì haûng så cáúp (elementary term) gäöm hàòng (constant), biãún
(variable) vaì caïc haûng phæïc håüp (compound term).
Caïc haûng phæïc håüp biãøu diãùn caïc âäúi tæåüng phæïc taûp cuía baìi toaïn cáön giaíi
quyãút thuäüc lénh væûc âang xeït. Haûng phæïc håüp laì mäüt haìm tæí (functor) coï
chæïa caïc âäúi (argument), coï daûng
Tãn_haìm_tæí(Âäúi_1, ..., Âäúi_n)
Tãn haìm tæí laì mäüt chuäùi chæî caïi vaì/hoàûc chuî säú âæåüc bàõt âáöu båíi mäüt chæî
caïi thæåìng. Caïc âäúi coï thãø laì biãún, haûng så cáúp, hoàûc haûng phæïc håüp. Trong
Prolog, haìm tæí âàûc biãût “.” (dáúu cháúm) biãøu diãùn cáúu truïc danh saïch (list).
Kiãøu dæî liãûu haìm tæí tæång tæû kiãøu baín ghi (record) vaì danh saïch (list) tæång
tæû kiãøu maíng (array) trong caïc ngän ngæî láûp trçnh mãûnh lãûnh (C, Pascal...).
Vê duû I.2 :
f(5, a, b).
student(robert, 1975, info, 2, address(6, 'mal juin', 'Caen')).
[a, b, c]
Mãûnh âãö coï thãø laì mäüt sæû kiãûn, mäüt luáût (hay quy tàõc), hay mäüt cáu hoíi.
Prolog quy æåïc viãút sau mäùi mãûnh âãö mäüt dáúu cháúm âãø kãút thuïc nhæ sau :
• Sæû kiãûn : < ... >. (tæång æïng våïi luáût < ... > :- true. )
• Luáût : < ... > :- < ... >.
• Cáu hoíi ?- < ... >. (åí chãú âäü tæång taïc coï dáúu nhàõc lãûnh)
I.2.2. Caïc kiãøu dæî liãûu Prolog
Hçnh 1.1. biãøu diãùn mäüt sæû phán låïp caïc kiãøu dæî liãûu trong Prolog gäöm
kiãøu dæî liãûu så cáúp vaì kiãøu dæî liãûu coï cáúu truïc. Sæû phán låïp naìy nháûn biãút
kiãøu cuía mäüt âäúi tæåüng nhåì bãö ngoaìi cuï phaïp.
Cuï phaïp cuía Prolog quy âënh mäùi kiãøu âäúi tæåüng coï mäüt daûng khaïc nhau.
Prolog khäng cáön cung cáúp mäüt thäng tin naìo khaïc âãø nháûn biãút kiãøu cuía
mäüt âäúi tæåüng. Trong Prolog, NSD khäng cáön khai baïo kiãøu dæî liãûu.
4 Láûp trçnh logic trong Prolog
kiãøu dæî liãûu
kiãøu så cáúp kiãøu phæïc håüp
hàòng biãún
säú chuäùi kyï tæû nguyãn tæí
Hçnh I.1. Caïc kiãøu dæî liãûu trong Prolog
Caïc kiãøu dæî liãûu Prolog âæåüc xáy dæûng tæì caïc kyï tæû ASCII :
• Caïc chæî caïi in hoa A, B, ..., Z vaì chæî caïi in thæåìng a, b, ..., z.
• Caïc chæî säú 0, 1, ..., 9.
• Caïc kyï tæû âàûc biãût, chàóng haûn + − ∗ / < > = : . & _ ∼.
I.2.3. Chuï thêch
Trong mäüt chæång trçnh Prolog, chuï thêch (comment) âæåüc âàût giæîa hai
càûp kyï hiãûu /* vaì */ (tæång tæû ngän ngæî C). Vê duû :
/∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
/∗∗∗ Âáy laì mäüt chuï thêch ∗∗∗/
/∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
Trong træåìng håüp muäún âàût mäüt chuï thêch ngàõn sau mäùi pháön khai baïo
Prolog cho âãún hãút doìng, coï thãø âàût træåïc mäüt kyï hiãûu %.
Vê duû :
%%%%%%%%%%%%%%%
% Âáy cuîng laì mäüt chuï thêch
%%%%%%%%%%%%%%%
Prolog seî boí qua táút caí caïc pháön chuï thêch trong thuí tuûc.
Måí âáöu vãö ngän ngæî Prolog 5
II. Caïc kiãøu dæî liãûu så cáúp cuía Prolog
II.1. Caïc kiãøu hàòng (træûc kiãûn)
II.1.1. Kiãøu hàòng säú
Prolog sæí duûng caí säú nguyãn vaì säú thæûc. Cuï phaïp cuía caïc säú nguyãn vaì säú
thæûc ráút âån giaín, chàóng haûn nhæ caïc vê duû sau :
1 1515 0 -97
3.14 -0.0035 100.2
Tuyì theo phiãn baín caìi âàût, Prolog coï thãø xæí lyï caïc miãön säú nguyãn vaì
miãön säú thæûc khaïc nhau. Vê duû trong phiãn baín Turbo Prolog, miãön säú
nguyãn cho pheïp tæì -32768 âãún 32767, miãön säú thæûc cho pheïp tæì ±1e-307
âãún ±1e+308. Caïc säú thæûc ráút khi âæåüc sæí duûng trong Prolog. Lyï do chuí yãúu åí
chäù Prolog laì ngän ngæî láûp trçnh kyï hiãûu, phi säú.
Caïc säú nguyãn thæåìng chè âæåüc sæí duûng khi cáön âãúm säú læåüng caïc pháön tæí
hiãûn diãûn trong mäüt danh saïch Prolog daûng [a1, a2, ..., an ].
II.1.2. Kiãøu hàòng lägich
Prolog sæí duûng hai hàòng lägich coï giaï trë laì true vaì fail. Thäng thæåìng caïc
hàòng lägich khäng âæåüc duìng nhæ tham säú maì âæåüc duìng nhæ caïc mãûnh âãö.
Hàòng fail thæåìng âæåüc duìng âãø taûo sinh låìi giaíi baìi toaïn.
II.1.3. Kiãøu hàòng chuäùi kyï tæû
Caïc hàòng laì chuäùi (string) caïc kyï tæû âæåüc âàût giæîa hai dáúu nhaïy keïp.
"Toto \#\{@ tata" chuäùi coï tuyì yï kyï tæû
"" chuäùi räùng (empty string)
"\"" chuäùi chè coï mäüt dáúu nhaïy keïp.
II.1.4. Kiãøu hàòng nguyãn tæí
Caïc hàòng nguyãn tæí Prolog laì chuäùi kyï tæû åí mäüt trong ba daûng nhæ sau :
(1) Chuäùi gäöm chæî caïi, chæî säú vaì kyï tæû _ luän luän âæåüc bàõt âáöu bàòng mäüt
chæî caïi in thæåìng.
newyork a_
nil x__y
x25 tom_cruise
6 Láûp trçnh logic trong Prolog
(2) Chuäùi caïc kyï tæû âàûc biãût :
.:.
======> ::==
...
(3) chuäùi âàût giæîa hai dáúu nhaïy âån (quote) âæåüc bàõt âáöu bàòng chæî in
hoa, duìng phán biãût våïi caïc tãn biãún :
’Jerry’ ’Tom SMITH’
II.2. Biãún
Tãn biãún laì mäüt chuäùi kyï tæû gäöm chæî caïi, chæî säú, bàõt âáöu båíi chæî hoa
hoàûc dáúu gaûch dæåïi doìng :
X, Y, A
Result, List_of_members
_x23, _X, _, ...
III. Sæû kiãûn vaì luáût trong Prolog
III.1. Xáy dæûng sæû kiãûn
Vê duû III.1 : Quan hãû gia âçnh
Âãø xáy dæûng caïc sæû kiãûn trong mäüt chæång trçnh Prolog, ta láúy mäüt vê duû
vãöï. Ta xáy dæûng mäüt cáy gia hãû nhæ sau :
pam tom
parent
bob liz
ann pat tom bob
jim
(a) (b)
Hçnh III.1.Cáy gia hãû.
Måí âáöu vãö ngän ngæî Prolog 7
Trong cáy gia hãû (a), caïc nuït chè ngæåìi, coìn caïc muîi tãn chè quan hãû cha
meû cuía (parent of). Sæû kiãûn Tom laì cha meû cuía Bob âæåüc viãút thaình mäüt vë
tæì Prolog nhæ sau (chuï yï mãûnh âãö âæåüc kãút thuïc båíi mäüt dáúu cháúm) :
parent(tom, bob). % Chuï yï khäng coï dáúu caïch træåïc dáúu måí ngoàûc
ÅÍ âáy, vë tæì parent coï hai âäúi laì tom vaì bob. Ngæåìi ta coï thãø biãøu diãùn vë
tæì naìy båíi mäüt cáy nhæ trong Hçnh III.1 (b) : nuït gäúc laì tãn vë tæì, caïc nuït laï laï
caïc âäúi.
Tæì cáy gia hãû trãn âáy, coï thãø tiãúp tuûc viãút caïc vë tæì khaïc âãø nháûn âæåüc
mäüt chæång trçnh Prolog gäöm 6 vë tæì nhæ sau :
parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
Sau khi hãû thäúng Prolog nháûn âæåüc chæång trçnh naìy, thæûc cháút laì mäüt cå
såí dæî liãûu, ngæåìi ta coï thãø âàût ra caïc cáu hoíi liãn quan âãún quan hãû parent.
Vê duû cáu hoíi Bob coï phaíi laì cha meû cuía Pat âæåüc goî vaìo trong hãû thäúng âäúi
thoaûi Prolog (dáúu nhàõc ?-_) nhæ sau :
?- parent(bob, pat).
Sau khi tçm tháúy sæû kiãûn naìy trong chæång trçnh, Prolog traí låìi :
Yes
Ta tiãúp tuûc âàût cáu hoíi khaïc :
?- parent(liz, pat).
No
Båíi vç Prolog khäng tçm tháúy sæû kiãûn Liz laì ngæåìi meû cuía Pat trong
chæång trçnh. Tæång tæû, Prolog traí låìi No cho sæû kiãûn :
?- parent(tom, ben).
Vç tãn ben chæa âæåüc âæa vaìo trong chæång trçnh. Ta coï thãø tiãúp tuûc âàût
ra caïc cáu hoíi thuï vë khaïc. Chàóng haûn, ai laì cha (hay meû) cuía Liz ?
?- parent(X, liz).
Láön naìy, Prolog khäng traí låìi Yes hoàûc No, maì âæa ra mäüt giaï trë cuía X
laìm thoaí maîn cáu hoíi trãn âáy :
8 Láûp trçnh logic trong Prolog
X = tom
Âãø biãút âæåüc ai laì con cuía Bob, ta chè cáön viãút :
?- parent(bob, X).
Våïi cáu hoíi naìy, Prolog seî coï hai cáu traí låìi, âáöu tiãn laì :
X = ann ->;
Âãø biãút âæåüc cáu traí låìi tiãúp theo, trong háöu hãút caïc caìi âàût cuía Prolog,
NSD phaíi goî vaìo mäüt dáúu cháúm pháøy (;) sau -> (Arity Prolog) :
X = pat
Nãúu âaî hãút phæång aïn traí låìi maì váùn tiãúp tuûc yãu cáöu (;), Prolog traí låìi
No.
NSD coï thãø âàût caïc cáu hoíi täøng quaït hån, chàóng haûn : ai laì cha meû cuía
ai ? Noïi caïch khaïc, cáön tçm X vaì Y sao cho X laì cha meû cuía Y. Ta viãút nhæ
sau :
?- parent(X, Y).
Sau khi hiãøn thë cáu traí låìi âáöu tiãn, Prolog seî láön læåüt tçm kiãúm nhæîng
càûp cha meû − con thoaí maîn vaì láön læåüt hiãøn thë kãút quaí nãúu chæìng naìo NSD
coìn yãu cáöu cho âãún khi khäng coìn kãút quaí låìi giaíi naìo næîa (kãút thuïc båíi
Yes) :
X = pam
Y = bob ->;
X = tom
Y = bob ->;
X = tom
Y = liz ->;
X = bob
Y = ann ->;
X = bob
Y = pat ->;
X = pat
Y = jim
Yes
Tuyì theo caìi âàût Prolog, NSD coï thãø goî vaìo mäüt dáúu cháúm (.) hoàûc Enter
âãø cháúm dæït giæîa chæìng luäöng traí låìi.
Måí âáöu vãö ngän ngæî Prolog 9
Ta coï thãø tiãúp tuûc âæa ra nhæîng cáu hoíi phæïc taûp hån khaïc, chàóng haûn ai
laì äng (baì) cuía Jim ? Thæûc tãú, quan hãû äng − baì (grandparent) chæa âæåüc
âënh nghéa, cáön phaíi phán taïch cáu hoíi naìy thaình hai pháön så cáúp hån :
1. Ai laì cha (meû) cuía Jim ? Giaí sæí coï tãn laì Y.
2. Ai laì cha (meû) cuía Y ? Giaí sæí coï tãn laì X.
X
parent
Y grandparent
parent
jim
Hçnh III.2. Quan hãû äng baì âæåüc håüp thaình tæì hai quan hãû cha meû.
Luïc naìy, coï thãø viãút trong Prolog nhæ sau :
?- parent(Y, jim), parent(X, Y).
Prolog traí låìi :
Y = pat
X = bob
Yes
Cáu hoíi trãn âáy tæång æïng våïi cáu hoíi : tçm X vaì Y thoaí maîn :
parent(Y, jim)
vaì
parent(X, Y).
Nãúu thay âäøi thæï tæû hai thaình pháön cáu hoíi, thç nghéa lägich váùn khäng
thay âäøi vaì Prolog traí låìi cuìng kãút quaí (coï thãø thay âäøi vãö thæï tæû), nghéa laì
ta coï thãø âàût cáu hoíi nhæ sau :
?- parent(X, Y), parent(Y, jim).
X = bob
Y = âæåìng dáùn
Yes
Báy giåì ta âàût cáu hoíi ai laì chaïu cuía Tom ?
?- parent(tom, X), parent(X, Y).
X = bob
Y = ann->;
10 Láûp trçnh logic trong Prolog
X = bob
Y = pat ->;
No
Mäüt cáu hoíi khaïc coï thãø nhæ sau : Ann vaì Pat coï cuìng ngæåìi äng khäng ?
nghéa laì ta diãùn âaût thaình hai giai âoaûn :
1. Tçm X laì cha meû cuía Ann.
2. X tçm tháúy coï cuìng laì cha meû cuía Pat khäng ?
Cáu hoíi vaì traí låìi trong Prolog nhæ sau :
?- parent(X, ann), parent(X, pat).
X = bob
Trong Prolog, cáu hoíi coìn âæåüc goüi laì âêch (goal) cáön phải âæåüc thoaí maîn
(satisfy). Mäùi cáu hoíi âàût ra âäúi våïi cå såí dæî liãûu coï thãø tæång æïng våïi mäüt
hoàûc nhiãöu âêch. Chàóng haûn daîy caïc âêch :
parent(X, ann), parent(X, pat).
tæång æïng våïi cáu hoíi laì pheïp häüi (conjunction) cuía 2 mãûnh âãö :
X laì mäüt cha meû cuía Ann, vaì
X laì mäüt cha meû cuía Pat.
Nãúu cáu traí låìi laì Yes, thç coï nghéa âêch âaî âæåüc thoaí maîn, hay âaî thaình
cäng. Trong træåìng håüp ngæåüc laûi, cáu traí låìi laì No, coï nghéa âêch khäng âæåüc
thoaí maîn, hay âaî tháút baûi.
Nãúu coï nhiãöu cáu traí låìi cho mäüt cáu hoíi, Prolog seî âæa ra cáu traí låìi âáöu
tiãn vaì chåì yãu cáöu cuía NSD tiãúp tuûc.
III.2. Xáy dæûng luáût
III.2.1. Âënh nghéa luáût
Tæì chæång trçnh gia hãû trãn âáy, ta coï thãø dãù daìng bäø sung caïc thäng tin
khaïc, chàóng haûn bäø sung caïc sæû kiãûn vãö giåïi tênh (nam, næî) cuía nhæîng ngæåìi
âaî nãu tãn trong quan hãû parent nhæ sau :
woman(pam).
man(tom).
man(bob).
woman(liz).
woman(pat).
Måí âáöu vãö ngän ngæî Prolog 11
woman(ann).
man(jim).
Ta âaî âënh nghéa caïc quan hãû âån (unary) woman vaì man vç chuïng chè
liãn quan âãún mäüt âäúi tæåüng duy nháút. Coìn quan hãû parent laì nhë phán, vç
liãn quan âãún mäüt càûp âäúi tæåüng. Nhæ váûy, caïc quan hãû âån duìng âãø thiãút
láûp mäüt thuäüc tênh cuía mäüt âäúi tæåüng. Mãûnh âãö :
woman(pam).
âæåüc giaíi thêch : Pam laì næî. Tuy nhiãn, ta cuîng coï thãø sæí duûng quan hãû nhë
phán âãø âënh nghéa giåïi tênh :
sex(pam, female).
sex(tom, male).
sex(bob, male).
...
Báy giåì ta âæa vaìo mäüt quan hãû måïi child, âäúi ngæåüc våïi parent nhæ sau :
child(liz, tom).
Tæì âoï, ta âënh nghéa luáût måïi nhæ sau :
child(Y, X) :- parent(X, Y).
Luáût trãn âæåüc hiãøu laì :
Våïi moüi X vaì Y, hay Våïi moüi X vaì Y,
Y laì con cuía X nãúu nãúu X laì cha (hay meû) cuía Y thç
X laì cha (hay meû) cuía Y. Y laì con cuía X.
Coï sæû khaïc nhau cå baín giæîa sæû kiãûn vaì luáût. Mäüt sæû kiãûn, chàóng haûn :
parent(tom, liz).
laì mäüt âiãöu gç âoï luän âuïng, khäng coï âiãöu kiãûn gç raìng buäüc. Trong khi âoï,
caïc luáût liãn quan âãún caïc thuäüc tênh chè âæåüc thoaí maîn nãúu mäüt säú âiãöu
kiãûn naìo âoï âæåüc thoaí maîn. Mäùi luáût bao gäöm hai pháön:
• pháön bãn phaíi (RHS: Right Hand Side) chè âiãöu kiãûn, coìn âæåüc goüi laì
thán (body) cuía luáût, vaì
• pháön bãn traïi (LH: Left Hand Side S) chè kãút luáûn, coìn âæåüc goüi laì âáöu
(head) cuía luáût.
12 Láûp trçnh logic trong Prolog
Nãúu âiãöu kiãûn parent(X, Y) laì âuïng, thç child(Y, X) cuîng âuïng vaì laì háûu
quaí lägich cuía pheïp suy luáûn (inference).
child(Y, X) :- parent(X, Y).
âáöu thán
Cáu hoíi sau âáy giaíi thêch caïch Prolog sæí duûng caïc luáût : Liz coï phaíi laì
con cuía Tom khäng ?
?- child(liz, tom)
Thæûc tãú, trong chæång trçnh khäng coï sæû kiãûn naìo liãn quan âãún con, maì
ta phaíi tçm caïch aïp duûng caïc luáût. Luáût trãn âáy åí daûng täøng quaït våïi caïc âäúi
tæåüng X vaì Y báút kyì, maì ta laûi cáön caïc âäúi tæåüng cuû thãø liz vaì tom.
Ta cáön sæí duûng pheïp thãú (substitution) bàòng caïch gaïn giaï trë liz cho biãún
Y vaì tom cho X. Ngæåìi ta noïi ràòng caïc biãún X vaì Y âaî âæåüc raìng buäüc
(bound) :
X = tom
vaì
Y = liz
Luïc naìy, pháön âiãöu kiãûn coï giaï trë parent(tom, liz) vaì tråí thaình âêch con
(sub-goal) âãø Prolog thay thãú cho âêch child(liz, tom). Tuy nhiãn, âêch naìy
thoaí maîn vaì coï giaï trë Yes vç chênh laì sæû kiãûn âaî thiãút láûp trong chæång
trçnh.
Sau âáy, ta tiãúp tuûc bäø sung caïc quan hãû måïi. Quan hãû meû mother âæåüc
âënh nghéa nhæ sau (chuï yï dáúu pháøy chè pheïp häüi hay pheïp vaì lägich) :
mother(X, Y) :- parent(X, Y), woman(X).
âæåüc hiãøu laì :
Våïi moüi X vaì Y, X laì meû cuía Y nãúu
X laì cha (hay meû) cuía Y vaì X laì næî.
Âäö thë sau âáy minh hoaû viãûc âënh nghéa caïc quan hãû child, mother vaì
grandparent sæí duûng mäüt quan hãû khaïc :
Trong âäö thë, ngæåìi ta quy æåïc ràòng : caïc nuït tæång æïng våïi caïc âäúi tæåüng
(laì caïc âäúi cuía mäüt quan hãû). Caïc cung näúi caïc nuït tæång æïng våïi caïc quan hãû
Måí âáöu vãö ngän ngæî Prolog 13
nhë phán, âæåüc âënh hæåïng tæì âäúi thæï nháút âãún âäúi thæï hai cuía quan hãû.
Mäüt quan hãû âån âæåüc biãøu diãùn båíi tãn quan hãû tæång æïng våïi nhaîn cuía
âäúi tæåüng âoï. Caïc quan hãû cáön âënh nghéa âæåüc biãøu diãùn båíi caïc cung coï neït
âæït. Mäùi âäö thë âæåüc giaíi thêch nhæ sau : nãúu caïc quan hãû âæåüc chè båíi caïc
cung coï neït liãön âæåüc thoaí maîn, thç quan hãû biãøu diãùn båíi cung coï neït âæït
cuîng âæåüc thoaí maîn.
woman
X X X
parent child parent mother parent
Y Y Y grandparent
parent
Z
Hçnh III.3. Âënh nghéa quan hãû con, meû vaì äng baì sæí duûng mäüt quan hãû khaïc.
Nhæ váûy, quan hãû äng−baì grandparent âæåüc viãút nhæ sau :
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
Âãø thuáûn tiãûn cho viãûc âoüc chæång trçnh Prolog, ta coï thãø viãút mäüt luáût
trãn nhiãöu doìng, doìng âáöu tiãn laì pháön âáöu cuía luáût, caïc doìng tiãúp theo laì
pháön thán cuía luáût, mäùi âêch trãn mäüt doìng phán biãût. Báy giåì quan hãû
grandparent âæåüc viãút laûi nhæ sau :
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
Ta tiãúp tuûc âënh nghéa quan hãû chë em gaïi sister nhæ sau :
sister(X, Y) :- Våïi moüi X vaì Y, X laì mäüt chë (em) gaïi cuía Y nãúu
parent(Z, X), (1) X vaì Y coï cuìng cha (cuìng meû), vaì
parent(Z, Y),
woman(X). (2) X laì næî .
Z
parent parent
woman X Y
sister
Hçnh III.4. Âënh nghéa quan hãû chë (em) gaïi.
14 Láûp trçnh logic trong Prolog
Chuï yï caïch giaíi thêch âiãöu kiãûn X vaì Y coï cuìng cha meû : mäüt Z naìo âoï
phaíi laì mäüt cha meû cuía X, vaì cuîng Z âoï phaíi laì mäüt cha meû cuía Y.
Hay noïi mäüt caïch khaïc laì : Z1 laì mäüt cha meû cuía X, Z2 laì mäüt cha meû cuía
Y, vaì Z1 âäöng nháút våïi Z2.
An laì næî, Ann vaì Pat cuìng cha meû nãn Ann laì chë em gaïi cuía Pat, ta coï :
?- sister(ann, pat).
Yes
Ta cuîng coï thãø hoíi ai laì chë em gaïi cuía Pat nhæ sau :
?- sister(X, pat).
Prolog seî láön læåüt âæa ra hai cáu traí låìi :
X = ann ->;
X = pat ->.
Yes
Váûy thç Pat laûi laì em gaïi cuía chênh mçnh ?! Âiãöu naìy sai vç ta chæa giaíi
thêch roî trong âënh nghéa chë em gaïi. Nãúu chè dæûa vaìo âënh nghéa trãn âáy
thç cáu traí låìi cuía Prolog laì hoaìn toaìn håüp lyï. Prolog suy luáûn ràòng X vaì Y coï
thãø âäöng nháút våïi nhau, mäùi ngæåìi âaìn baì coï cuìng cha meû seî laì em gaïi cuía
chênh mçnh. Ta cáön sæía laûi âënh nghéa bàòng caïch thãm vaìo âiãöu kiãûn X vaì Y
khaïc nhau. Nhæ seî tháúy sau naìy, Prolog coï nhiãöu caïch âãø giaíi quyãút, tuy
nhiãn luïc naìy ta giaí sæí ràòng quan hãû :
different(X, Y)
âaî âæåüc Prolog nháûn biãút vaì âæåüc thoaí maîn nãúu vaì chè nãúu X vaì Y khäng
bàòng nhau. Âënh nghéa chë (em) gaïi måïi nhæ sau :
sister(X, Y) :-
parent(Z, X),
parent(Z, Y),
woman(X).
different(X, Y).
Vê duû III.2 : Ta láúy laûi vê duû cäø âiãøn sæí duûng hai tiãn âãö sau âáy :
Táút caí moüi ngæåìi âãöu chãút.
Socrate laì mäüt ngæåìi.
Ta viãút trong Prolog nhæ sau :
mortal(X) :- man(X).
man(socrate).
