Lập trình lôgich

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:193

Thêm vào BST

Báo xấu

204
lượt xem 84
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cuốn sách này nhằm cung cấp cơ sở lý thuyết và các phương pháp lập trình cơ bản nhất của môn học «Lập trình lôgich» (Programming in Logic). Người đọc sẽ được làm quen với một số kỹ thuật lập trình lôgich được ứng dụng tương đối phổ biến và chủ yếu trong lĩnh vực trí tuệ nhân tạo (Artificial Intelligence) như công nghệ xử lý tri thức, máy học, hệ chuyên gia, xử lý ngôn ngữ tự nhiên, trò chơi, v.v... ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lập trình lôgich

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í long 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ã ö n gän ngæ î P rolog « 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 : tom pam parent bob liz tom bob pat ann 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 grandparent Y 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 parent parent mother child grandparent Y Y Y 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), (2) X laì næî . woman(X). 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).