Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 2

Chia sẻ: Dwefershrdth Vrthrtj | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

229
lượt xem 72
download

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

Đến năm 1980, prolog nhanh chóng được áp dụng rộng rãi, đựoc người Nhật chọn làm ngôn ngữ phát triển máy tính thế hệ 5. Prolog đã dược cài đặt trên hầu hết các dòng máy tính unix/lunix, Macintosh, Windows.

Chủ đề:

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

Lưu

Nội dung Text: Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 2

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. Mi 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 parent mother parent child grandparent Y Y Y parent Z nh nghĩa quan h con, m và ông bà s d ng m t quan h khác. Hình III.3. 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) :-
13 M u v ngôn ng Prolog parent(Z, X), parent(Z, Y), woman(X). Z parent parent woman X Y sister nh nghĩa quan h ch (em) gái. Hình III.4. Chú ý cách gi i thích i u ki n X và Y có cùng cha m : m t Z nào ó ph i là m t cha m c a X, và cũng Z ó ph i là m t cha m c a Y. Hay nói m t cách khác là : Z1 là m t cha m c a X, Z2 là m t cha m c a Y, và Z1 ng nh t v i Z2. An là n , Ann và Sue cùng cha m nên Ann là ch em gái c a Sue, ta có : ?- sister(ann, sue). Yes Ta cũng có th h i ai là ch em gái c a Sue như sau : ?- sister(X, sue). Prolog s l n lư t ưa ra hai câu tr l i : X = ann ->; X = sue ->. Yes V y thì Sue l i là em gái c a chính mình ?! i u này sai vì ta chưa gi i thích rõ trong nh nghĩa ch em gái. N u ch d a vào nh nghĩa trên ây thì câu tr l i c a Prolog là hoàn toàn h p lý. Prolog suy lu n r ng X và Y có th ng nh t v i nhau, m i ngư i àn bà có cùng cha m s là em gái c a chính mình. Ta c n s a l i nh nghĩa b ng cách thêm vào i u ki n X và Y khác nhau. Như s th y sau này, Prolog có nhi u cách gi i quy t, tuy nhiên lúc này ta gi s r ng quan h: different(X, Y) ã ư c Prolog nh n bi t và ư c tho mãn n u và ch n u X và Y không b ng nhau. nh nghĩa ch (em) gái m i như sau : sister(X, Y) :- parent(Z, X), parent(Z, Y), woman(X). different(X, Y). Ví d III.2 : Ta l y l i ví d c i n s d ng hai tiên sau ây :
14 L p trình lôgic trong Prolog T t c m i ngư i u ch t. Socrate là m t ngư i. Ta vi t trong Prolog như sau : mortal(X) :- man(X). man(socrate). M t nh lý ư c suy lu n m t cách lôgich t hai tiên này là Socrate ph i ch t. Ta t các câu h i như sau : ?- mortal(socrate). Yes Ví d III.3 : ch Paul cũng là ngư i, còn Bonzo là con v t, ta vi t các s ki n : man(paul). animal(bonzo). Con ngư i có th nói và không ph i là lo i v t, ta vi t lu t : speak(X) :- man(X), not(animal(bonzo)). Ta t các câu h i như sau : ?- speak(bonzo). No ?- speak(paul). Yes Ví d III.4 : Ta ã xây d ng các s ki n và các lu t có d ng v t ch a tham i, sau ây, ta l y m t ví d khác v s ki n và lu t không ch a tham i : 'It is sunny'. 'It is summer'. 'It is hot' :- 'It is summer', 'It is sunny'. 'It is cold' :- 'It is winter', 'It is snowing'. T chương trình trên, ta có th t câu h i : ?- 'It is hot'. Yes Câu tr l i 'It is hot' là úng vì ã có các s ki n 'It is sunny' và 'It is summer' trong chương trình. Còn câu h i « ?- 'It is cold.' » có câu tr l i sai.
15 M u v ngôn ng Prolog III.2.2. nh nghĩa lu t quy Bây gi ta ti p t c thêm m t quan h m i vào chương trình. Quan h này ch s d ng quan h parent, và ch có hai lu t. Lu t th nh t nh nghĩa các t tiên tr c ti p, lu t th hai nh nghĩa các t tiên gián ti p. Ta nói r ng X là m t t tiên gián ti p c a Z n u t n t i m t liên h cha m (ông bà) gi a X và Z : Trong cây gia h Hình III.1, Tom là t tiên tr c ti p c a Liz, và t tiên gián ti p c a Sue. Ta nh nghĩa lu t 1 (t tiên tr c ti p) như sau : V i m i X và Z, X là m t t tiên c a Z n u X là cha m c a Z . ancestor(X, Z) :- parent(X, Z). X X parent ancestor parent Z (a) parent ancesto r parent Y (b) Hình III.5. Quan h t tiên : (a) X là t tiên tr c ti p c a Z, (b) X là t tiên gián ti p c a Z. nh nghĩa lu t 2 (t tiên gián ti p) ph c t p hơn, trình Prolog tr nên dài dòng hơn, m i khi càng m r ng m c t tiên h u du như ch ra trong Hình III.6. K c lu t 1, ta có quan h t tiên ư c nh nghĩa như sau : % lu t 1 nh nghĩa t tiên tr c ti p ancestor(X, Z) :- parent(X, Z). % lu t 2 : t tiên gián ti p là ông bà (tam i) ancestor(X, Z) :- parent(X, Y), parent(Y, Z). % t tiên gián ti p là c ông c bà (t i) ancestor(X, Z) :- parent(X, Y1), parent(Y1, Y2), parent(Y2, Z).
16 L p trình lôgic trong Prolog % ngũ i ng ư ng ancestor(X, Z) :- parent(X, Y1), parent(Y1, Y2), parent(Y2, Y3), parent(Y3, Z). ... Tuy nhiên, t n t i m t cách nh nghĩa t tiên gián ti p m c b t kỳ nh phép quy (recursive) như sau : V i m i X và Z, X là m t t tiên c a Z n u t n t i Y sao cho (1) X là cha m c a Y và (2) Y là m t t tiên c a Z. X X X parent parent ancestor Y1 Y Y1 parent ancestor parent ancestor Y2 Z Y2 parent Y3 Z Z Hình III.6. Các c p t tiên h u du gián ti p các m c khác nhau. ancestor(X, Z) :- parent(X, Z). ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). ?- ancestor(mary, X). X = jim ->; X = ann ->; X = sue ->; X = bill Yes
17 M u v ngôn ng Prolog Trong Prolog, h u h t các chương trình ph c t p u s d ng quy, quy là m t kh năng m nh c a Prolog. ancestor parent Y ... X Z ancestor quy c a quan h t tiên ( ư c quay ngang cho thu n ti n). Hình III.7.D ng Cho n lúc này, ta ã nh nghĩa nhi u quan h (parent, woman, man, grandparent, child, sister, mother và ancestor). Ta th y m i quan h ch tương ng v i m t m nh , tuy nhiên, quan h ancestor l i có hai m nh . Ngư i ta nói r ng nh ng m nh này liên quan (concern) n quan h ancestor. Trong trư ng h p t t c các m nh u liên quan n m t quan h , ngư i ta nh n ư c m t th t c (procedure). III.2.3. S d ng bi n trong Prolog Khi tính toán, NSD có th thay th m t bi n trong m t m nh b im t i tư ng khác. Lúc này ta nói bi n ã b ràng bu c. Các bi n xu t hi n trong m t m nh ư c g i là bi n t do. Ngư i ta gi thi t r ng các bi n là ư c lư ng t toàn th và ư c c là «v i m i». Tuy hiên có nhi u cách gi i thích khác nhau trong trư ng h p các bi n ch xu t hi n trong ph n bên ph i c a lu t. Ví d : haveachil(X) :- parent(X, Y). có th ư c c như sau : (a) V i m i X và Y, n u X là cha (hay m ) c a Y thì X có m t ngư i con. (b) V i m i X, X có m t ngư i con n u t n t i m t Y sao cho X là cha (hay m ) c a Y. Khi m t bi n ch xu t hi n m t l n trong m t m nh thì không c n t tên cho nó. Prolog cho phép s d ng các bi n n c danh (anonymous variable) là các bi n có tên ch là m t d u g ch dư i dòng _. Ta xét ví d sau : have_a_child(X) :- parent(X, Y).
18 L p trình lôgic trong Prolog Lu t trên nêu lên r ng v i m i X, X có m t con n u X là cha c a m t Y nào ó. Ta th y ích have_a_child không ph thu c gì vào tên c a con, vì v y có th s d ng bi n n c danh như sau : have_a_child(X) :- parent(X, _). M i v trí xu t hi n d u g ch dư i dòng _ trong m t m nh tương ng v i m t bi n n c danh m i. Ví d n u ta mu n th hi n t n t i m t ngư i nào ó có con n u t n t i hai i tư ng sao cho m t i tư ng này là cha c a i tư ng kia, thì ta có th vi t : someone_has_a_child :- parent(_, _). M nh này tương ương v i : someone_has_a_child :- parent(X, Y). nhưng hoàn toàn khác v i : someone_has_a_child :- parent(X, X). N u bi n n c danh xu t hi n trong m t câu h i, thì Prolog s không hi n th giá tr c a bi n này trong k t qu tr v . N u ta mu n tìm ki m nh ng ngư i có con, mà không quan tâm n tên con là gì, thì ch c n vi t : ?- parent(X, _). ho c tìm ki m nh ng ngư i con, mà không quan tâm n cha m là gì : ?- parent(_ , X). T m v c t v ng (lexical scope) c a các bi n trong m t m nh không vư t ra kh i m nh ó. Có nghĩa là n u, ví d , bi n X15 xu t hi n trong hai m nh khác nhau, thì s tương ng v i hai bi n phân bi t nhau. Trong cùng m t m nh , X15 luôn luôn ch bi u di n m t bi n. Tuy nhiên i v i các h ng thì tình hu ng l i khác : m t nguyên t th hi n m t i tư ng trong t t c các m nh , có nghĩa là trong t t c chương trình. IV. Ki u d li u c u trúc c a Prolog IV.1. nh nghĩa ki u c u trúc c a Prolog Ki u d li u có c u trúc, tương t c u trúc b n ghi, là i tư ng có nhi u thành ph n, m i thành ph n l i có th là m t c u trúc. Prolog xem m i thành ph n như là m t i tư ng khi x lý các c u trúc. t h p các thành ph n thành m t i tư ng duy nh t, Prolog s d ng các hàm t . Ví d IV.1 : C u trúc g m các thành ph n ngày tháng năm t o ra hàm t date. Ngày 2/9/1952 s ư c vi t như sau : date(2, september, 1952)
19 M u v ngôn ng Prolog M i thành ph n trong hàm t date u là h ng (hai s nguyên và m t nguyên t ). Tuy nhiên ta có th thay th m i thành ph n b ng m t bi n hay m t c u trúc khác. Ch ng h n ta có th thay th thành ph n th nh t b ng bi n Day (chú ý tên bi n b t u b i ch hoa) th hi n b t kỳ ngày nào c a tháng 9 : date(Day, may, 1890) Chú ý r ng Day là m t bi n, có th ư c ràng bu c khi x lý sau ó. Trong Prolog, v m t cú pháp, các i tư ng là nh ng h ng. Trong ví d trên, may và date(Day, september, 2003) u là nh ng h ng. các tham i date date( Day, september, 2003 ) hàm t bi n ký hi u s 02 september (b) 2003 (a) Hình IV.1. Ngày tháng là m t i tư ng có c u trúc : (a) bi u di n d ng cây c a c u trúc ; (b) gi i thích cách vi t trong Prolog M i i tư ng có c u trúc u có th ư c bi u di n hình h c dư i d ng cây (tree), v i hàm t là g c, còn các thành ph n tham i là các nhánh c a cây. N u m t trong các thành ph n là m t c u trúc, thì thành ph n ó t o thành m t cây con c a cây ban u. Hai h ng là có cùng c u trúc n u có cùng cây bi u di n và có cùng thành ph n (pattern of variables). Hàm t c a g c ư c g i là hàm t chính c a h ng. Ví d IV.2 : C u trúc ( ơn gi n) c a m t cu n sách g m ba thành ph n tiêu và tác gi cũng là các c u trúc (con), năm xu t b n là m t bi n : book(title(Name), author(Author), Year) Ví d IV.3 : Xây d ng các i tư ng hình h c ơn gi n trong không gian hai chi u. M i i m ư c xác nh b i hai to , hai i m t o thành m t ư ng th ng, ba i m t o thành m t tam giác. Ta xây d ng các hàm t sau ây : bi u di n i m, point bi u di n m t o n th ng (segment), seg bi u di n m t tam giác. triangle
20 L p trình lôgic trong Prolog i tư ng hình h c ơn gi n. 5 ình IV.2. M t s H i 4ư  trên Hình IV.2 ư c bi u d6, 4) b i các h ng như sau : ( T ó, các t ng in P1 = point(1, 1) P2 = (2, 3) 3 P2 = point(2, 3) S = seg(P1,2 P2) = seg(point(1, 1), point(2, 3))  T = triangle(point(4, 2), 2) (4, point(6, 4), point(7, 1)) 1 N u trong cùng m t chương trình, ta có các i m trong1) t không gian ba (7, m P1 = (1, 1) chi u, ta có th nh nghĩa m t hàm t m i là point3 như sau : | | | | | | | | point3(X, Y, Z) 1 2 3 4 5 6 7 8 Prolog cho phép s d ng cùng tên hai c u trúc khác nhau. Ví d : và point(X1, Y1) point(X, Y, Z) là hai c u trúc khác nhau. Trong cùng m t chương trình, n u m t tên óng hai vai trò khác nhau, như trư ng h p point trên, thì Prolog s căn c vào s lư ng i s phân bi t. Cùng m t tên này s tương ng v i hai hàm t , m t hàm t có hai i s và m t hàm t có ba i s . Như v y, m t hàm t ư c nh nghĩa b i hai y u t : P1 = P1 = seg T = triangle point point point point point point 1 1 1 1 2 3 4 2 6 4 7 1 i tư ng. Hình IV.3. Bi u di n d ng cây c a các (1) Tên hàm t có cú pháp là cú pháp c a các nguyên t . (2) Kích thư c c a hàm t là s các i s c a nó. Bi u di n d ng cây c a các i tư ng i m, o n th ng và tam giác trên ây ư c cho trong Hình IV.3. Như ã trình bày, m i i tư ng c u trúc c a Prolog u ư c bi u di n dư i d ng cây, xu t hi n trong m t chương trình dư i d ng các h ng. * + - a b c 5 Hình IV.4. C u trúc cây c a bi u th c (a + b) * (c − 5)
21 M u v ngôn ng Prolog Ví d bi u th c s h c : (a + b) * (c − 5) có d ng cây, có th vi t dư i d ng bi u th c ti n t g m các hàm t *, + và − : *(+(a, b), −(c, 5)) IV.2. So sánh và h p nh t các h ng Ta v a xét cách bi u di n các c u trúc d li u s d ng h ng. Bây gi ta s xét phép toán quan tr ng nh t liên quan n các h ng là phép so kh p (matching), th c ch t là phép so sánh (comparison operators) trên các h ng và các v t . Trong Prolog, vi c so kh p tương ng v i vi c h p nh t (unification) ư c nghiên c u trong lý thuy t lôgich. Cho hai h ng, ngư i ta nói r ng chúng là h p nh t ư c v i nhau, n u : (1) chúng là gi ng h t nhau, ho c (2) các bi n xu t hi n trong hai h ng có th ư c ràng bu c sao cho các h ng c a m i i tư ng tr nên gi ng h t nhau. Th t chu n (standard order) trên các h ng ư c nh nghĩa như sau : 1. Bi n < Nguyên t < Chu i < S < H ng 2. Bi n cũ < Bi n m i 3. Nguyên t ư c so sánh theo th t ABC (alphabetically). 4. Chu i ư c so sánh theo th t ABC. 5. S ư c so sánh theo giá tr (by value). S nguyên và s th c ư c x lý như nhau (treated identically). 6. Các h ng ph c h p (compound terms) ư c so sánh b c hay s lư ng tham i (arity) trư c, sau ó so sánh tên hàm t (functor-name) theo th t ABC và cu i cùng so sánh m t cách quy (recursively) l n lư t các tham i t trái qua ph i (leftmost argument first). Ví d hai h ng date(D, M, 1890) và date(D1, May, Y1) là có th v i nhau nh ràng bu c sau : • D ư c ràng bu c v i D1 • M ư c ràng bu c v i May • Y1 ư c ràng bu c v i 1890 Trong Prolog, ta có th vi t : D = D1 M = May Y1 = 1890
22 L p trình lôgic trong Prolog Tuy nhiên, ta không th ràng bu c hai h ng date(D, M, 1890) và date(D1, May, 2000), hay date(X, Y, Z) và point(X, Y, Z). C u trúc book(title(Name), author(Author)) ư c so kh p v i : book(title(lord_of_the_rings), author(tolkien)) nh phép th : Name = lord_of_the_rings Author = tolkien Thu t toán h p nh t Herbrand so kh p hai h ng S và T : (1) N u S và T là các h ng, thì S và T ch có th kh p nhau n u và ch n u chúng có cùng giá tr (ch là m t i tư ng). (2) N u S là m t bi n, T là m t i tư ng nào ó b t kỳ, thì S và T kh p nhau, v i S ư c ràng bu c v i T. Tương t , n u T là m t bi n, thì T ư c ràng bu c v i S. (3) N u S và T là các c u trúc, thì S và T kh p nhau n u và ch n u : (a) S và T có cùng m t hàm t chính, và (b) t t c các thành ph n là kh p nhau t ng ôi m t. Như v y, s ràng bu c ư c xác nh b i s ràng bu c c a các thành ph n. Ta có th quan sát lu t th ba cách bi u di n các h ng dư i d ng cây trong Hình IV.5 dư i ây. Quá trình so kh p ư c b t u t g c (hàm t chính). N u hai hàm t là gi ng nhau, thì quá trình s ư c ti p t c v i t ng c p tham i c a chúng. M i quá trình so kh p ư c xem như m t dãy các phép tính ơn gi n hơn như sau : triangle = triangle point(1, 1) = X A = point(4, Y) point(2, 3) = point(2, Z) M i quá trình so kh p là tích c c (positive), n u t t c các quá trình so kh p b tr là tích c c.
23 M u v ngôn ng Prolog triangle point A point 1 1 2 3 triangle X point point 4 Y 2 Z Hình IV.5. K t qu so kh p : triangle(point(1, 1), A, point(2, 3)))= triangle(X, point(4, Y), point(2, Z))). S ràng bu c nh n ư c như sau : X = point(1, 1) A = point(4, Y) Z=3 Sau ây là m t ví d minh ho s d ng k thu t so kh p nh n bi t m t o n th ng ã cho là n m ngang hay th ng ng. M t o n th ng là th ng ng n u hoành (abscissa) c a hai mút là b n g nhau, tương t , là n m ngang n u tung (ordinate) c a hai mút là b ng nhau. Ta s d ng quan h ơn phân bi u di n các tính ch t này như sau : vertical(seg(point(X, Y), point(X, Y1))). horizontal(seg(point(X, Y), point(X1, Y))). Ta có : ?- vertical(seg(point(1, 1), point(1, 2))). Yes ?- vertical(seg(point(1, 1), point(2, Y))). No ?- horizontal(seg(point(1, 1), point(2, Y))). Y=1 Yes
24 L p trình lôgic trong Prolog point(X, Y1) point(X, Y) point(X1, Y) point(X, Y) Hình IV.6. Minh ho các o n th ng n m ngang và th ng ng. V i câu h i th nh t, Prolog tr l i Yes vì các s ki n ư c so kh p úng. V i câu h i th hai, vì không có s ki n nào ư c so kh p nên Prolog tr l i No. V i câu h i th ba, Prolog cho Y giá tr 1 ư c so kh p úng. Ta có th t m t câu h i t ng quát hơn như sau : Cho bi t nh ng o n th ng th ng ng có m t mút cho trư c là (2, 3) ? ?- vertical(seg(point(2, 3), P)). P = point(2, _0104) Yes Câu tr l i có nghĩa là m i ư ng th ng có phương trình X = 2 là th ng ng. Chú ý r ng ây, ta không nh n ư c tên bi n như mong mu n (là Y), mà tuỳ theo phiên b n cài t c th , Prolog s t o ra m t tên bi n khi th c hi n chương trình, _0104 trong ví d trên, nh m tránh t l i tên bi n c a NSD v i hai lý do như sau. Th nh t, cùng m t tên bi n nhưng xu t hi n trong các m nh khác nhau thì s bi u di n nh ng bi n khác nhau. Th hai, do khi áp d ng liên ti p cùng m t m nh , chính b n «copy» ư c s d ng v i m t b bi n khác. Bây gi ta t ti p m t câu h i thú v như sau : Có t n t i m t o n th ng v a th ng ng v a n m ngang hay không ? ?- vertical(S), horizontal(S). S = seg(point(_00E8, _00EC), point(_00E8, _00EC)) Yes Câu tr l i có nghĩa là m i o n th ng khi suy bi n thành m t i m thì v a th ng ng, l i v a n m ngang. Ta th y r ng k t qu nh n ư c là nh so kh p. ây, các tên bi n _00E8 và _00EC, tương ng v i X và Y, ã ư c t o ra b i Prolog.
25 M u v ngôn ng Prolog Sau ây là m t ví d khác minh ho hai c u trúc ư c s kh p v i nhau. student jean X address maljuin caen student jean info Y Hình IV.7. K t qu so kh p : student( jean, X, address(maljuin, caen) ) = student( jean,info, Y ). Tóm t t chương 1 Chương 1 ã trình bày nh ng y u t sơ c p c a Prolog, r t g n gũi v i lôgich hình th c. Nh ng i m quan tr ng mà ta có ư c là : Nh ng i tư ng sơ c p c a Prolog là nguyên t , bi n và s . Các i tư ng • có c u trúc, hay c u trúc, dùng bi u di n các i tư ng có nhi u thành ph n. Các hàm t dùng xây d ng các c u trúc. M i hàm t ư c nh nghĩa b i • tên và th nguyên (dimension). Ki u c a m t i tư ng ư c nh nghĩa hoàn toàn nh vào s xu t hi n v • m t cú pháp c a nó. T m v c t v ng (lexical scope) c a m t bi n là duy nh t m nh mà bi n • xu t hi n. Cùng m t tên bi n xu t hi n trong hai m nh s tương ng v i hai bi n khác nhau. Các c u trúc ư c bi u di n r t ơn gi n b i các cây. Prolog ư c xem như là • m t ngôn ng x lý cây. Phép toán so kh p so sánh hai ph n t (term) và tìm cách ng nh t chúng • b i các ràng bu c c a chúng. N u so kh p thành công, Prolog ưa ra ràng bu c các bi n t ng quát nh t. • Nh ng khái ni m ã trình bày là : • m nh , s ki n, lu t, câu h i, nguyên t , bi n, bi n ràng bu c, ph n u và ph n thân c a c a m t m nh ,
26 L p trình lôgic trong Prolog lu t quy, nh nghĩa quy, ích, i tư ng : nguyên t , s , bi n, h ng c u trúc hàm t , th nguyên c a m t hàm t hàm t chính c a m t h ng so kh p các h ng ràng bu c t ng quát nh t Bài t p chương 1 1. Tìm các i tư ng Prolog úng n v m t cú pháp trong s i tư ng ư c cho dư i ây. Cho bi t ki u c a chúng (là nguyên t , s , bi n hay c u trúc) ? a) Diane b) diane c) ‘Diane’ d) _diane e) ‘Diane va en vacances’ f) va( diane, vacances ) g) 45 h) 5(X , Y) i) +( nord , owest ) j) three( small( cats ) ) 2. Hãy tìm m t bi u di n d ng i tư ng c u trúc cho các hình ch nh t, hình vuông và hình tròn. Xem hình 2.4 có cách gi i quy t. S d ng các bi u di n cho các hình c th minh h a. 3. Chương trình sau nói r ng hai ngư i là có quan h dòng h v i nhau n u : a) m t là t tiên c a ngư i kia, ho c, b) hai ngư i có chung t tiên, ho c, c) hai ngư i có cùng con cháu. kindred( X, Y) :- ancestor(X , Y). kindred(X , Y) :- ancestor(X , Y). % X và Y có cùng t tiên kindred(X , Y) :- ancestor( Z, X), ancestor(Z , Y).
27 M u v ngôn ng Prolog % X và Y có cùng con cháu kindred(X , Y) :- ancestor (X , Z), ancestor(Y , Z). Hãy cho bi t có th làm ng n chương trình trên b ng cách s d ng d u ch m ph y ; ư c không ? 4. Hãy tìm hi u m t nh nghĩa m i v quan h ancestor : ancestor(X Z) :- parent(X Z) . ancestor(X Z) :- parent(Y , Z), ancestor( X, Y). nh nghĩa này có úng hay không ? Có th thay i l i sơ ã cho trong hình 1.7 tương ng v i nh nghĩa m i này ? 5. Ngoài các nh nghĩa quan h gia ình ã có trong ph n lý thuy t và bài t p, hãy nh nghĩa các quan h khác theo t p quán Vi t Nam (cô, dì, chú, bác...) ? 6. Hãy nh nghĩa các quan h trong th gi i sinh v t ( ng v t, th c v t) ? 7. Cho bi t các h ng Prolog h p th c sau ây (valid Prolog terms) : 23 +(fred, jim) foo(X, bar(+(3, 4))) 1+2. Foo(x) Alison Cawsey 8. Cho quan h parent ư c nh nghĩa trong ph n lý thuy t cho bi t k t qu c a các câu h i sau : a) ?- parent(jim , X). b) ?- parent( X , jim). c) ?- parent(mary , X) , parent( X , part). d) ?- parent(mary , X) , parent( X , y ) , parent(y , jim). 9. Vi t các m nh Prolog di n t các câu h i liên quan n quan h parent : a)Ai là cha m c a Sue ? b)Liz có con không ? c)Ai là ông bà (grandparent) c a Sue ? 10. Vit trong Prolog các m nh sau : a)Ai có m t a tr ngư i ó là h nh phúc. Hư ng d n : Xây d ng quan h m t ngôi happy. b) V i m i X, n u X có m t con mà ngư i con này có m t ch em gái, thì X có hai con (xây d ng quan h have_two_children). 11. nh nghĩa quan h grandchild b ng cách s d ng quan h parent. Hư ng d n : tìm hi u quan h grandparent.
28 L p trình lôgic trong Prolog 12. nh nghĩa quan h aunt( X, Y ) b ng cách s d ng quan h parent. thu n ti n, có th v sơ minh h a. 13. Các phép so kh p dư i ây có úng không ? N u úng, cho bi t các ràng bu c bi n tương ng ? a) point( A , B ) = point( 1 ,2) b) point( A , B ) = point( X , Y, Z ) c) addition( 2 , 2 ) = 4 d) +( 2 , D ) = +( E , 2 ) e) triangle( point( -1 , 0 ) , P2, P3 ) = triangle( P1, point( 1, 0 ), point( 0, Y ) ) Các ràng bu c ây ã nh nghĩa m t l p các tam giác. Làm cách nào mô t l p này ? 14. S d ng mô t các ư ng th ng ã cho trong bài h c, tìm m t h ng bi u di n m i ư ng th ng ng X = 5. 15. Cho hình ch nh t ư c bi u di n b i h ng: rectangle(P1, P2, P3, P4). V i Pi là các nh c a hình ch nh t theo chi u dương, hãy nh nghĩa quan h: regular( R ) là úng n u R là m t hình ch nh t có các c nh th ng ng và n m ngang (song song v i các tr c t a ).
CHƯƠNG 2 Ng nghĩa c a chương trình Prolog I. Quan h gi a Prolog và lôgich toán h c Prolog có quan h ch t ch v i lôgich toán h c. D a vào lôgich toán h c, ngư i ta có th di n t cú pháp và nghĩa c a Prolog m t cách ng n g n và súc tích. Tuy nhiên không vì v y mà nh ng ngư i h c l p trình Prolog c n ph i bi t m t s khái ni m v lôgich toán h c. Th t may m n là nh ng khái ni m v lôgich toán h c không th c s c n thi t có th hi u và s d ng Prolog như là m t công c l p trình. Sau ây là m t s quan h gi a Prolog và lôgich toán h c. Prolog có cú pháp là nh ng công th c lôgich v t b c m t (first order predicate logic), ư c vi t dư i d ng các m nh (các lư ng t ∀ và ∃ không xu t hi n m t cách tư ng minh), nhưng h n ch ch ơn thu n d ng m nh Horn, là nh ng m nh ch có ít nh t m t tr c ki n dương (positive literals). Năm 1981, Clocksin và Mellish ã ưa ra m t chương trình Prolog chuy n các công th c tính v t b c m t thành d ng các m nh . Cách Prolog di n gi i chương trình là theo ki u Toán h c : Prolog xem các s ki n và các lu t như là các tiên , xem câu h i c a NSD như là m t nh lý c n ph ng oán. Prolog s tìm cách ch ng minh nh lý này, nghĩa là ch ra r ng nh lý có th ư c suy lu n m t cách lôgich t các tiên . V m t th t c, Prolog s d ng phương pháp suy di n quay lui (back chaining) h p gi i (resolution) bài toán, ư c g i là chi n lư c h p gi i SLD (Selected, Linear, Definite : Linear resolution with a Selection function for Definite sentences) do J. Herbrand và A. Robinson xu t năm 1995. Có th tóm t t như sau : ch ng minh P(a), ngư i ta tìm s ki n P(t) ho c m t lu t : P(t) :- L1, L2, …, Ln 29
30 L p trình lôgic trong Prolog sao cho a có th h p nh t (unifiable) ư c v i t nh so kh p. N u tìm ư c P(t) là s ki n như v y, vi c ch ng minh k t thúc. Còn n u tìm ư c P(t) là lu t, c n l n lư t ch ng minh v bên ph i L1, L2, ..., Ln c a nó. Trong Prolog, câu h i luôn luôn là m t dãy t m t n nhi u ích. Prolog tr l i m t câu h i b ng cách tìm ki m xoá (erase) t t c các ích. Xoá m t ích nghĩa là ch ng minh r ng ích này ư c tho mãn, v i gi thi t r ng các quan h c a chương trình là úng. Nói cách khác, xoá m t ích có nghĩa là ích này ư c suy ra m t cách lôgich b i các s ki n và lu t ch a trong chương trình. N u có các bi n trong câu h i, Prolog tìm các i tư ng thay th vào các bi n, sao cho ích ư c tho mãn. S ràng bu c giá tr c a các bi n tương ng v i vi c hi n th các i tư ng này. N u Prolog không th tìm ư c ràng bu c cho các bi n sao cho ích ư c suy ra t chương trình thì nó s tr l i No. II. Các m c nghĩa c a chương trình Prolog Cho n lúc này, qua các ví d minh ho , ta m i ch hi u ư c tính úng n v k t qu c a m t chương trình Prolog, mà chưa hi u ư c làm cách nào h th ng tìm ư c l i gi i. M t chương trình Prolog có th ư c hi u theo nghĩa khai báo (declarative signification) ho c theo nghĩa th t c (procedural signification). V n là c n phân bi t hai m c nghĩa c a m t chương trình Prolog, là nghĩa khai báo và nghĩa th t c. Ngư i ta còn phân bi t m c nghĩa th ba c a m t chương trình Prolog là nghĩa lôgich (logical semantic). Trư c khi nh nghĩa m t cách hình th c hai m c ng nghĩa khai báo và th t c, ta c n phân bi t s khác nhau gi a chúng. Cho m nh : P :- Q, R. v i P, Q, và R là các h ng nào ó. Theo nghĩa khai báo, ta c chúng theo hai cách như sau : P là úng n u c Q và R u úng. • Q và R d n ra P. • Theo nghĩa th t c, ta cũng c chúng theo hai cách như sau : gi i bài toán P, u tiên, gi i bài toán con Q, sau ó gi i bài toán con R. • xoá P, u tiên, xoá Q, sau ó xoá R. • S khác nhau gi a nghĩa khai báo và nghĩa th t c là ch , nghĩa th t c không nh nghĩa các quan h lôgich gi a ph n u c a m nh và các ích c a thân, mà ch nh nghĩa th t x lý các ích.