Lập trình Lôgích trong prolog

Chia sẻ: Hoang Kien | Ngày: | Loại File: PDF | Số trang:99

Thêm vào BST

Báo xấu

128
lượt xem 35
download

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

Prolog là một ngôn ngữ lập trình. Tên gọi Prolog được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là "lập trình theo lô gích". Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của Prolog là giúp người dùng mô tả lại bài toán trên ngôn ngữ của logic, dựa trên đó, máy tính sẽ tiến hành suy diễn tự động dựa vào những cơ chế suy diễn có sẵn (hợp nhất, quay lui và tìm kiếm theo chiều sâu) để tìm câu trả lời cho người dùng....

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ôgích trong prolog

PGS.TS. PHAN HUY KHÁNH L p t rình Lô g ích trong Prolog NHÀ XU T B N I H C QU C GIA HÀ N I 2004
PGS.TS. PHAN HUY KHÁNH L p tr ìn h L ôg í ch t r ong Pr ol og Prolog là ngôn ng l p trình lôgich (Prolog = PROgramming in LOGic) do GS. A. Colmerauer ưa ra l n u tiên năm 1972 t i trư ng i h c Marseille, nư c Pháp. n năm 1980, Prolog nhanh chóng ư c áp d ng r ng rãi, ư c ngư i Nh t ch n làm ngôn ng phát tri n máy tính th h 5. Prolog ã ư c cài t trên h u h t các dòng máy tính Unix/Linux, Macintosh, Windows. Prolog còn ư c g i là ngôn ng l p trình ký hi u (symbolic programming) tương t l p trình hàm (functional programming), hay l p trình phi s (non-numerical programming). Nguyên lý l p trình lôgich d a trên phép suy di n lôgích, liên quan n nh ng khái ni m toán h c như phép h p nh t Herbrand, h p gi i Robinson, lôgich Horn, lôgich v t b c m t (first order predicate logic), v.v... Prolog r t thích h p gi i quy t nh ng bài toán liên quan n các i tư ng và m i quan h gi a chúng. Prolog ư c ng d ng 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, h chuyên gia, máy h c, x lý ngôn ng , trò chơi, v.v... N i dung cu n sách t p trung trình bày cơ s lý thuy t và nh ng k thu t l p trình cơ b n trong Prolog, r t thích h p cho sinh viên các ngành tin h c và nh ng b n c mu n tìm hi u v k thu t l p trình ng d ng trong lĩnh v c trí tu nhân t o. V TÁC GI : T t nghi p ngành Toán Máy tính năm 1979 t i trư ng i h c Bách khoa Hà N i. T 1979 n nay gi ng d y t i khoa Công ngh Thông tin, trư ng i h c Bách khoa, i h c à N ng. B o v ti n sĩ năm 1991 t i Pháp. Gi ch c ch nhi m khoa Công ngh Thông tin 1995-2000. Hư ng nghiên c u chính : x lý ngôn ng , x lý a ng , lý thuy t tính toán. E-mail: khanhph@vnn.vn 3
L I NÓI U Cu n sách này nh m cung c p cơ s lý thuy t và nh ng 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... Cu n sách g m năm chương, trong m i chương, tác gi u c g ng ưa vào nhi u ví d minh h a. N i dung các chương như sau : − Chương 1 gi i thi u ngôn ng l p trình Prolog d a trên lôgich Horn (Horn logic). Ngư i c ư c làm quen v i các ki u d li u c a Prolog, khái ni m lu t, s ki n và vi t ư c các chương trình Prolog ơn gi n. − Chương 2 trình bày các m c nghĩa khác nhau c a m t chương trình Prolog : nghĩa lôgich, nghĩa khai báo và nghĩa th t c, cách Prolog tr l i các câu h i, cách Prolog làm tho mãn các ích. − Chương 3 trình bày các phép toán s h c, phép so sánh các i tư ng và nh nghĩa các hàm s d ng phép quy trong Prolog. − Chương 4 trình bày c u trúc danh sách và các phép x lý cơ b n trên danh sách c a Prolog. − Chương 5 trình bày k thu t l p trình nâng cao v i Prolog. − Ph n ph l c gi i thi u ngôn ng l p trình SWI-Prolog, hư ng d n cách cài t s d ng ph n m m này và m t s chương trình ví d tiêu bi u vi t trong SWI Prolog ã ch y có k t qu . Cu n sách này dùng làm giáo trình cho sinh viên ngành Tin h c và nh ng b n c mu n tìm hi u thêm v k thu t l p trình cho lĩnh v c trí tu nhân t o. Trong quá trình biên so n, tác gi ã nh n ư c t các b n ng nghi p nhi u óng gó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 giúp v biên t p cu n sách ư c ra i. Tác gi xin ư c bày t lòng bi t ơn sâu s c. Tác gi cũng chân thành c m ơn m i ý ki n phê bình óng góp c a b n c g n xa v n i dung c a cu n sách này. à N ng, ngày 27/05/2004 Tác gi .
M CL 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 là ngôn ng l p trình lôgich .............................................. 1 I.2. Cú pháp Prolog ............................................................................ 2 I.2.1. Các thu t ng .............................................................................. 2 I.2.2. Các ki u d li u Prolog ............................................................... 3 I.2.3. Chú thích ..................................................................................... 4 II. CÁC KI U D LI U SƠ C P C A PROLOG.......................... 5 II.1. Cá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 ký t .................................................................. 5 II.1.4. Ki u h ng nguyên t .................................................................... 5 II.2. Bi n ............................................................................................. 6 III. S KI N VÀ 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............................................................... 16 III.2.3. S d ng bi n trong Prolog ......................................................... 18 IV. KI U D LI U C U TRÚC C A PROLOG........................... 20 IV.1. nh nghĩa ki u c u trúc c a Prolog........................................... 20 IV.2. So sánh và h p nh t các h ng..................................................... 23 CHƯƠNG 3 NG NGHĨA C A CHƯƠNG TRÌNH PROLOG ................ 31 I. QUAN H GI A PROLOG VÀ LÔGICH TOÁN H C ........... 31 II. CÁC M C NGHĨA C A CHƯƠNG TRÌNH PROLOG ........... 32 II.1. Nghĩa khai báo c a chương trình Prolog .................................... 33 II.2. Khái ni m v gói m nh .......................................................... 34 II.3. Nghĩa lôgich c a các m nh .................................................... 35 II.4. Nghĩa th t c c a Prolog............................................................ 37 II.5. T h p các y u t khai báo và th t c ........................................ 47 i
III. VÍ D : CON KH VÀ QU CHU I........................................ 48 III.1. Phát bi u bài toán....................................................................... 48 III.2. Gi i bài toán v i Prolog ............................................................. 49 III.3. S p t th t các m nh và các ích ...................................... 54 III.3.1. Nguy cơ g p các vòng l p vô h n............................................... 54 III.3.2. Thay i th t m nh và ích trong chương trình.................. 56 CHƯƠNG 3 CÁC PHÉP TOÁN VÀ S H C............................................. 65 I. S H C .................................................................................... 65 I.1. Các phép toán s h c ................................................................. 65 I.2. Bi u th c s h c ........................................................................ 65 I.3. nh nghĩa các phép toán trong Prolog....................................... 68 II. CÁC PHÉP SO SÁNH C A PROLOG ..................................... 73 II.1. Các phép so sánh s h c............................................................. 73 II.2. Các phép so sánh h ng ............................................................... 75 II.3. V t xác nh ki u..................................................................... 77 II.4. M t s v t x lý h ng .............................................................. 77 III. NH NGHĨA HÀM ................................................................. 79 III.1. nh nghĩa hàm s d ng quy................................................. 79 III.2. T i ưu phép quy .................................................................... 87 III.3. M t s ví d khác v quy....................................................... 88 III.3.1. Tìm ư ng i trong m t th có nh hư ng ............................ 88 III.3.2. Tính dài ư ng i trong m t th ........................................ 89 III.3.3. Tính g n úng các chu i ............................................................ 90 CHƯƠNG 4 C U TRÚC DANH SÁCH ...................................................... 95 I. BI U DI N C U TRÚC DANH SÁCH ................................... 95 II. M T S V T X LÝ DANH SÁCH C A PROLOG........... 98 III. CÁC THAO TÁC CƠ B N TRÊN DANH SÁCH .................... 99 III.1. Xây d ng l i m t s v t có s n ............................................... 99 III.1.1. Ki m tra m t ph n t có m t trong danh sách............................ 99 III.1.2. Ghép hai danh sách ................................................................. 100 III.1.3. B sung m t ph n t vào danh sách......................................... 104 III.1.4. Lo i b m t ph n t kh i danh sách......................................... 104 III.1.5. Ngh ch o danh sách.............................................................. 105 III.1.6. Danh sách con ......................................................................... 106 III.2. Hoán v .................................................................................... 107
III.3. M t s ví d v danh sách........................................................ 109 III.3.1. S p x p các ph n t c a danh sách.......................................... 109 III.3.2. Tính dài c a m t danh sách................................................. 109 III.3.3. T o sinh các s t nhiên........................................................... 111 CHƯƠNG 5 K THU T L P TRÌNH PROLOG .................................... 117 I. NHÁT C T ............................................................................. 117 I.1. Khái ni m nhát c t ................................................................... 117 I.2. K thu t s d ng nhát c t......................................................... 118 I.2.1. T o ích gi b ng nhát c t....................................................... 118 I.2.2. Dùng nhát c t lo i b hoàn toàn quay lui ................................ 119 I.2.3. Ví d s d ng k thu t nhát c t ................................................ 122 I.3. Phép ph nh .......................................................................... 126 I.3.1. Ph nh b i th t b i ............................................................... 126 I.3.2. S d ng k thu t nhát c t và ph nh...................................... 128 II. S D NG CÁC C U TRÚC.................................................. 131 II.1. Truy c p thông tin c u trúc t m t cơ s d li u ...................... 132 II.2. Tr u tư ng hoá d li u ............................................................ 136 II.3. Mô ph ng ôtômat h u h n ....................................................... 138 II.3.1. Mô ph ng ôtômat h u h n không ơn nh .............................. 138 II.3.2. Mô ph ng ôtômat h u h n ơn nh ........................................ 143 II.4. Ví d : l p k ho ch i du l ch b ng máy bay ........................... 144 II.5. Bài toán tám quân h u.............................................................. 150 II.5.1. S d ng danh sách to theo hàng và c t.............................. 151 II.5.2. S d ng danh sách to theo c t........................................... 155 II.5.3. S d ng to theo hàng, c t và các ư ng CHÉO................. 158 II.5.4. K t lu n ................................................................................... 161 II.5.5. B di n d ch Prolog ................................................................. 162 III. QUÁ TRÌNH VÀO-RA VÀ LÀM VI C V I T P.................. 163 III.1. Khái ni m ................................................................................ 163 III.2. Làm vi c v i các t p ................................................................ 164 III.2.1. c và ghi lên t p .................................................................... 164 III.2.2. M t s ví d c và ghi lên t p................................................. 167 III.2.3. N p chương trình Prolog vào b nh ....................................... 171 III.3. ng d ng ch làm vi c v i các t p...................................... 172 III.3.1. nh d ng các h ng ................................................................. 172 III.3.2. S d ng t p x lý các h ng ...................................................... 173 III.3.3. Thao tác trên các ký t ............................................................. 175 III.3.4. Thao tác trên các nguyên t ..................................................... 177 III.3.5. M t s v t x lý cơ s d li u ................................................ 180 iii
PH L C A M T S CHƯƠNG TRÌNH PROLOG ............................... 187 PH L C B HƯ NG D N S D NG SWI-PROLOG............................ 200 I. GI I THIÊUU SWI-PROLOG ................................................ 194 II. LAIM VIÊUC V I SWI-PROLOG ......................................... 195 II.1. t câu h i............................................................................... 195 II.2. Ch y trình demo ...................................................................... 196 II.3. Ch y trình demo XPCE............................................................ 197 II.4. Các l nh ơn (Menu commands).............................................. 198 II.5. So n th o chương trình ............................................................ 200 III. M T S L NH SWI-PROLOG THÔNG D NG ................... 201 TÀI LI U THAM KH O ............................................................................... 203
CHƯƠNG 1 M uv 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 là ngôn ng l p trình lôgich rolog là ngôn ng ư c s d ng ph bi n nh t trong dòng các ngôn ng P l p trình lôgich (Prolog có nghĩa là PROgramming in LOGic). Ngôn ng Prolog do giáo sư ngư i Pháp Alain Colmerauer và nhóm nghiên c u c a ông xu t l n u tiên t i trư ng i h c Marseille u nh ng năm 1970. n năm 1980, Prolog nhanh chóng ư c áp d ng r ng rãi châu Âu, ư c ngư i Nh t ch n làm ngôn ng phát tri n dòng máy tính th h 5. Prolog ã ư c cài t trên các máy vi tính Apple II, IBM-PC, Macintosh. Prolog còn ư c g i là ngôn ng l p trình ký hi u (symbolic programming) tương t các ngôn ng l p trình hàm (functional programming), hay l p trình phi s (non- numerical programming). Prolog r t thích h p gi i quy t các bài toán liên quan n các i tư ng (object) và m i quan h (relation) gi a chúng. Prolog ư c s d ng ph bi n trong lĩnh v c trí tu nhân t o. Nguyên lý l p trình lôgich d a trên cá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 nào ó là úng ho c không úng, x y ra ho c không x y ra (có ho c không có, v.v...). Ví d I.1 : Sau ây là m t s m nh Horn : 1. N u m t ngư i già mà (và) khôn ngoan thì ngư i ó h nh phúc. 2. Jim là ngư i h nh phúc. 3. N u X là cha m c a Y và Y là cha m c a Z thì X là ông c a Z. 4. Tom là ông c a Sue. 1
2 L p trình lôgic trong Prolog 5. T t c m i ngư i u ch t (ho c N u ai là ngư i thì ai ó ph i ch t). 6. Socrat là ngư i. Trong các m nh Horn trên, các m nh 1, 3, 5 ư c g i là các lu t (rule), các m nh còn l i ư c g i là các s ki n (fact). M t chương trình lôgich có th ư c xem như là m t cơ s d li u g m các m nh Horn, ho c d ng lu t, ho c d ng s ki n, ch ng h n như t t c các s ki n và lu t t 1 n 6 trên. Ngư i s d ng (NSD) g i ch y m t chương trình lôgich b ng cách t câu h i (query/ question) truy v n trên cơ s d li u này, ch ng h n câu h i : Socrat có ch t không ? (tương ương kh ng nh Socrat ch t úng hay sai ?) M t h th ng lôgich s th c hi n chương trình theo cách «suy lu n»-tìm ki m d a trên v n «hi u bi t» ã có là chương trình - cơ s d li u, minh ch ng câu h i là m t kh ng nh, là úng (Yes) ho c sai (No). V i câu h i trên, h th ng tìm ki m trong cơ s d li u kh ng nh Socrat ch t và «tìm th y» lu t 5 tho mãn (v thì). V n d ng lu t 5, h th ng nh n ư c Socrat là ngư i (v n u) chính là s ki n 5. T ó, câu tr l i s là : Yes có nghĩa s ki n Socrat ch t là úng. I.2. Cú pháp Prolog I.2.1. Các thu t ng M t chương trình Prolog là m t cơ s d li u g m các m nh (clause). M i m nh ư c xây d ng t các v t (predicat). M t v t là m t phát bi u nào ó v các i tư ng có giá tr chân úng (true) ho c sai (fail). M t v t có th có các i là các nguyên lôgich (logic atom). M i nguyên t (nói g n) bi u di n m t quan h gi a các h ng (term). Như v y, h ng và quan h gi a các h ng t o thành m nh . H ng ư c xem là nh ng i tư ng “d li u” trong m t trình Prolog. H ng có th là h ng sơ c p (elementary term) g m h ng (constant), bi n (variable) và các h ng ph c h p (compound term). Các h ng ph c h p bi u di n các i tư ng ph c t p c a bài toán c n gi i quy t thu c lĩnh v c ang xét. H ng ph c h p là m t hàm t (functor) có ch a các i (argument), có d ng Tên_hàm_t ( i_1, ..., i_n) Tên hàm t là m t chu i ch cái và/ho c chũ s ư c b t u b i m t ch cái thư ng. Các i có th là bi n, h ng sơ c p, ho c h ng ph c h p. Trong Prolog,
M u v ngôn ng Prolog 3 hàm t c bi t “.” (d u ch m) bi u di n c u trúc danh sách (list). Ki u d li u hàm t tương t ki u b n ghi (record) và danh sách (list) tương t ki u m ng (array) trong các ngôn ng l p trình m nh l nh (C, Pascal...). Ví d I.2 : f(5, a, b). student(robert, 1975, info, 2, address(6, 'mal juin', 'Caen')). [a, b, c] M nh có th là m t s ki n, m t lu t (hay quy t c), hay m t câu h i. Prolog quy ư c vi t sau m i m nh m t d u ch m k t thúc như sau : • S ki n : < ... >. (tương ng v i lu t < ... > :- true. ) • Lu t : < ... > :- < ... >. • Câu h i ?- < ... >. ( ch tương tác có d u nh c l nh) I.2.2. Các ki u d li u Prolog Hình 1.1. bi u di n m t s phân l p các ki u d li u trong Prolog g m ki u d li u sơ c p và ki u d li u có c u trúc. S phân l p này nh n bi t ki u c a m t i tư ng nh b ngoài cú pháp. Cú pháp c a Prolog quy nh m i ki u i tư ng có m t d ng khác nhau. Prolog không c n cung c p m t thông tin nào khác nh n bi t ki u c a m t i tư ng. Trong Prolog, NSD không c n khai báo ki u d li u. ki u d li u ki u sơ c p ki u ph c h p h ng bi n s chu i ký t nguyên t Hình I.1. Các ki u d li u trong Prolog Các ki u d li u Prolog ư c xây d ng t các ký t ASCII : • Các ch cái in hoa A, B, ..., Z và ch cái in thư ng a, b, ..., z. • Các ch s 0, 1, ..., 9.
4 L p trình lôgic trong Prolog • Các ký t c bi t, ch ng h n + - * / < > = : . & _ ~. I.2.3. Chú thích Trong m t chương trình Prolog, chú thích (comment) ư c t gi a hai c p ký hi u /* và */ (tương t ngôn ng C). Ví d : /*************************/ /*** ây là m t chú thích ***/ /*************************/ Trong trư ng h p mu n t m t chú thích ng n sau m i ph n khai báo Prolog cho n h t dòng, có th t trư c m t ký hi u %. Ví d : %%%%%%%%%%%%%%%%%%%%% % ây cũng là m t chú thích %%%%%%%%%%%%%%%%%%%%% Prolog s b qua t t c các ph n chú thích trong th t c. II. Các ki u d li u sơ c p c a Prolog II.1. Các ki u h ng (tr c ki n) II.1.1. Ki u h ng s Prolog s d ng c s nguyên và s th c. Cú pháp c a các s nguyên và s th c r t ơn gi n, ch ng h n như các ví d sau : 1 1515 0 -97 3.14 -0.0035 100.2 Tuỳ theo phiên b n cài t, Prolog có th x lý các mi n s nguyên và mi n s th c khác nhau. Ví d trong phiên b n Turbo Prolog, mi n s nguyên cho phép t -32768 n 32767, mi n s th c cho phép t ±1e-307 n ±1e+308. Các s th c r t khi ư c s d ng trong Prolog. Lý do ch y u ch Prolog là ngôn ng l p trình ký hi u, phi s . Các s nguyên thư ng ch ư c s d ng khi c n m s lư ng các ph n t hi n di n trong m t danh sách Prolog d ng [a1, a2, ..., an ].
M u v ngôn ng Prolog 5 II.1.2. Ki u h ng lôgich Prolog s d ng hai h ng lôgich có giá tr là true và fail. Thông thư ng các h ng lôgich không ư c dùng như tham s mà ư c dùng như các m nh . H ng fail thư ng ư c dùng t o sinh l i gi i bài toán. II.1.3. Ki u h ng chu i ký t Các h ng là chu i (string) các ký t ư c t gi a hai d u nháy kép. "Toto \#\{@ tata" chu i có tuỳ ý ký t "" chu i r ng (empty string) "\"" chu i ch có m t d u nháy kép. II.1.4. Ki u h ng nguyên t Các h ng nguyên t Prolog là chu i ký t m t trong ba d ng như sau : (1) Chu i g m ch cái, ch s và ký t _ luôn luôn ư c b t u b ng m t ch cái in thư ng. newyork a_ nil x__y x25 tom_cruise (2) Chu i các ký t c bi t : .:. ======> ::== ... (3) chu i t gi a hai d u nháy ơn (quote) ư c b t u b ng ch in hoa, dùng phân bi t v i các tên bi n : ’Jerry’ ’Tom SMITH’ II.2. Bi n Tên bi n là m t chu i ký t g m ch cái, ch s , b t u b i ch hoa ho c d u g ch dư i dòng : X, Y, A Result, List_of_members _x23, _X, _, ...
6 L p trình lôgic trong Prolog III. S ki n và lu t trong Prolog III.1. Xây d ng s ki n Ví d III.1 : Quan h gia ình xây d ng các s ki n trong m t chương trình Prolog, ta l y m t ví d v . Ta xây d ng m t cây gia h như Hình III.1. Trong cây gia h (a), các nút ch ngư i, còn các mũi tên ch quan h cha m c a (parent of). S ki n Tom là cha m c a Bill ư c vi t thành m t v t Prolog như sau (chú ý m nh ư c k t thúc b i m t d u ch m) : parent(tom, bill). % Chú ý không có d u cách trư c d u m ngo c ây, v t parent có hai i là tom và bill. Ngư i ta có th bi u di n v t này b i m t cây như trong Hình III.1 (b) : nút g c là tên c a v t , còn các nút lá là các i. mar tom parent y bil liz l tom bill ann sue jim (a) (b) Hình III.1.Cây gia h . T cây gia h trên ây, có th ti p t c vi t các v t khác nh n ư c m t chương trình Prolog g m 6 v t như sau : parent(mary, bill). parent(tom, bill). parent(tom, liz). parent(bill, ann). parent(bill, sue). parent(sue, jim). Sau khi h th ng Prolog nh n ư c chương trình này, th c ch t là m t cơ s d li u, ngư i ta có th t ra các câu h i liên quan n quan h parent. Ví d
M u v ngôn ng Prolog 7 câu h i Bill có ph i là cha m c a Sue ư c gõ vào trong h th ng i tho i Prolog (d u nh c ?-_) như sau : ?- parent(bill, sue). Sau khi tìm th y s ki n này trong chương trình, Prolog tr l i : Yes Ta ti p t c t câu h i khác : ?- parent(liz, sue). No B i vì Prolog không tìm th y s ki n Liz là ngư i m c a Sue trong chương trình. Tương t , Prolog tr l i No cho s ki n : ?- parent(tom, ben). Vì tên ben chưa ư c ưa vào trong chương trình. Ta có th ti p t c t ra các câu h i thú v khác. Ch ng h n, ai là cha (hay m ) c a Liz ? ?- parent(X, liz). L n này, Prolog không tr l i Yes ho c No, mà ưa ra m t giá tr c a X làm tho mãn câu h i trên ây : X = tom bi t ư c ai là con c a Bill, ta ch c n vi t : ?- parent(bill, X). V i câu h i này, Prolog s có hai câu tr l i, u tiên là : X = ann ->; bi t ư c câu tr l i ti p theo, trong h u h t các cài t c a Prolog, NSD ph i gõ vào m t d u ch m ph y (;) sau -> (Arity Prolog) : X = sue N u ã h t phương án tr l i mà v n ti p t c yêu c u (;), Prolog tr l i No. NSD có th t các câu h i t ng quát hơn, ch ng h n : ai là cha m c a ai ? Nói cách khác, c n tìm X và Y sao cho X là cha m c a Y. Ta vi t như sau : ?- parent(X, Y). Sau khi hi n th câu tr l i u tiên, Prolog s l n lư t tìm ki m nh ng c p cha m − con tho mãn và l n lư t hi n th k t qu n u ch ng nào NSD còn yêu c u cho n khi không còn k t qu l i gi i nào n a (k t thúc b i Yes) : X = mary Y = bill ->; X = tom Y = bill ->;
8 L p trình lôgic trong Prolog X = tom Y = liz ->; X = bill Y = ann ->; X = bill Y = sue ->; X = sue Y = jim Yes Tuỳ theo cài t Prolog, NSD có th gõ vào m t d u ch m (.) ho c Enter ch m d t gi a ch ng lu ng tr l i. Ta có th ti p t c ưa ra nh ng câu h i ph c t p hơn khác, ch ng h n ai là ông (bà) c a Jim ? Th c t , quan h ông − bà (grandparent) chưa ư c nh nghĩa, c n ph i phân tách câu h i này thành hai ph n sơ c p hơn : 1. Ai là cha (m ) c a Jim ? Gi s có tên là Y. 2. Ai là cha (m ) c a Y ? Gi s có tên là X. X parent grandparent Y parent jim Hình III.2. Quan h ông bà ư c h p thành t hai quan h cha m . Lúc này, có th vi t trong Prolog như sau : ?- parent(Y, jim), parent(X, Y). Prolog tr l i : Y = sue X = bill Yes Câu h i trên ây tương ng v i câu h i : tìm X và Y tho mãn : parent(Y, jim) và parent(X, Y).
M u v ngôn ng Prolog 9 N u thay i th t hai thành ph n câu h i, thì nghĩa lôgich v n không thay i và Prolog tr l i cùng k t qu (có th thay i v th t ), nghĩa là ta có th t câu h i như sau : ?- parent(X, Y), parent(Y, jim). X = bill Y = ư ng d n Yes Bây gi ta t câu h i ai là cháu c a Tom ? ?- parent(tom, X), parent(X, Y). X = bill Y = ann->; X = bill Y = sue ->; No M t câu h i khác có th như sau : Ann và Sue có cùng ngư i ông không ? nghĩa là ta di n t thành hai giai o n : 1. Tìm X là cha m c a Ann. 2. X tìm th y có cùng là cha m c a Sue không ? Câu h i và tr l i trong Prolog như sau : ?- parent(X, ann), parent(X, sue). X = bill Trong Prolog, câu h i còn ư c g i là ích (goal) c n ph i ư c tho mãn (satisfy). M i câu h i t ra i v i cơ s d li u có th tương ng v i m t ho c nhi u ích. Ch ng h n dãy các ích : parent(X, ann), parent(X, sue). tương ng v i câu h i là phép h i (conjunction) c a 2 m nh : X là m t cha m c a Ann, và X là m t cha m c a Sue. N u câu tr l i là Yes, thì có nghĩa ích ã ư c tho mãn, hay ã thành công. Trong trư ng h p ngư c l i, câu tr l i là No, có nghĩa ích không ư c tho mãn, hay ã th t b i. N u có nhi u câu tr l i cho m t câu h i, Prolog s ưa ra câu tr l i u tiên và ch yêu c u c a NSD ti p t c.
10 L p trình lôgic trong Prolog 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 có th d dàng b sung các thông tin khác, ch ng h n b sung các s ki n v gi i tính (nam, n ) c a nh ng ngư i ã nêu tên trong quan h parent như sau : woman(mary). man(tom). man(bill). woman(liz). woman(sue). woman(ann). man(jim). Ta ã nh nghĩa các quan h ơn (unary) woman và man vì chúng ch liên quan n m t i tư ng duy nh t. Còn quan h parent là nh phân, vì liên quan nm tc p i tư ng. Như v y, các quan h ơn dùng thi t l p m t thu c tính c a m t i tư ng. M nh : woman(mary). ư c gi i thích : Mary là n . Tuy nhiên, ta cũng có th s d ng quan h nh phân nh nghĩa gi i tính : sex(mary, female). sex(tom, male). sex(bill, male). ... Bây gi ta ưa vào m t quan h m i child, i ngư c v i parent như sau : child(liz, tom). T ó, ta nh nghĩa lu t m i như sau : child(Y, X) :- parent(X, Y). Lu t trên ư c hi u là : V i m i X và Y, Y là con c a X n u X là cha (hay m ) c a Y. hay
M u v ngôn ng Prolog 11 V i m i X và Y, n u X là cha (hay m ) c a Y thì Y là con c a X. Có s khác nhau cơ b n gi a s ki n và lu t. M t s ki n, ch ng h n : parent(tom, liz). là m t i u gì ó luôn úng, không có i u ki n gì ràng bu c. Trong khi ó, các lu t liên quan n các thu c tính ch ư c tho mãn n u m t s i u ki n nào ó ư c tho mãn. M i lu t bao g m hai ph n: • ph n bên ph i (RHS: Right Hand Side) ch i u ki n, còn ư c g i là thân (body) c a lu t, và • ph n bên trái (LH: Left Hand Side S) ch k t lu n, còn ư c g i là u (head) c a lu t. N u i u ki n parent(X, Y) là úng, thì child(Y, X) cũng úng và là h u qu lôgich c a phép suy lu n (inference). child(Y, X) :- parent(X, Y). u thân Câu h i sau ây gi i thích cách Prolog s d ng các lu t : Liz có ph i là con c a Tom không ? ?- child(liz, tom) Th c t , trong chương trình không có s ki n nào liên quan n con, mà ta ph i tìm cách áp d ng các lu t. Lu t trên ây d ng t ng quát v i các i tư ng X và Y b t kỳ, mà ta l i c n các i tư ng c th liz và tom. Ta c n s d ng phép th (substitution) b ng cách gán giá tr liz cho bi n Y và tom cho X. Ngư i ta nói r ng các bi n X và Y ã ư c ràng bu c (bound) : X = tom và Y = liz Lúc này, ph n i u ki n có giá tr parent(tom, liz) và tr thành ích con (sub-goal) Prolog thay th cho ích child(liz, tom). Tuy nhiên, ích này tho mãn và có giá tr Yes vì chính là s ki n ã thi t l p trong chương trình. Sau ây, ta ti p t c b sung các quan h m i. Quan h m mother ư c nh nghĩa như sau (chú ý d u ph y ch phép h i hay phép và lôgich) : mother(X, Y) :- parent(X, Y), woman(X).
12 L p trình lôgic trong Prolog ư c hi u là : V i m i X và Y, X là m c a Y n u X là cha (hay m ) c a Y và X là n . th sau ây minh ho vi c nh nghĩa các quan h child, mother và grandparent s d ng m t quan h khác : Trong th , ngư i ta quy ư c r ng : các nút tương ng v i các i tư ng (là các i c a m t quan h ). Các cung n i các nút tương ng v i các quan h nh phân, ư c nh hư ng t i th nh t n i th hai c a quan h . M t quan h ơn ư c bi u di n b i tên quan h tương ng v i nhãn c a i tư ng ó. Các quan h c n nh nghĩa s ư c bi u di n b i các cung có nét t. M i th ư c gi i thích như sau : n u các quan h ư c ch b i các cung có nét li n ư c tho mãn, thì quan h bi u di n b i cung có nét t cũng ư c tho mãn. woman X X X parent child parent mother parent grandparent Y Y Y parent Z Hình III.3. nh nghĩa quan h con, m và ông bà s d ng m t quan h khác. Như v y, quan h ông−bà grandparent ư c vi t như sau : grandparent(X, Z) :- parent(X, Y), parent(Y, Z). thu n ti n cho vi c c chương trình Prolog, ta có th vi t m t lu t trên nhi u dòng, dòng u tiên là ph n u c a lu t, các dòng ti p theo là ph n thân c a lu t, m i ích trên m t dòng phân bi t. Bây gi quan h grandparent ư c vi t l i như sau : grandparent(X, Z) :- parent(X, Y), parent(Y, Z). Ta ti p t c nh nghĩa quan h ch em gái sister như sau : V i m i X và Y, X là m t ch (em) gái c a Y n u (1) X và Y có cùng cha (cùng m ), và (2) X là n . sister(X, Y) :-