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

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

Thêm vào BST

Báo xấu

138
lượt xem 43
download

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

Prolog 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 Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 7

110 L p trình lôgic trong Prolog Prolog tr l i : N = 1 + (1 + (1 + (1 + 0))) Yes Phép c ng do không ư c kh i ng m t cách tư ng minh nên s không bao gi ư c th c hi n. Tuy nhiên, ta có th hoán i hai ích c a m nh th hai trong length1 : length1( [ ], 0 ). length1( [ _ | Queue ], N ) :- N = 1 + N1, length1( Queue, N1 ). K t qu ch y chương trình sau khi hoán i v n y h t như cũ. Bây gi , ta l i có th rút g n m nh v ch còn m t ích : length1( [ ], 0 ). length2( [ _ | Queue ], 1 + N ) :- length2( Queue, N ). K t qu ch y chương trình l n này v n y h t như cũ. Prolog không ưa ra tr l i như mong mu n, mà là : ?- length1([ a, b, c, d], N). N = 1+ (1+ (1+ (1+0))) Yes III.3.3. T o sinh các s t nhiên Chương trình sau ây t o sinh và li t kê các s t nhiên : % Natural Numbers nat(0). nat(N) :- nat(M), N is M + 1. Khi th c hi n các ích con trong câu h i : ?- nat(N), write(N), nl, fail. các s t nhiên ư c t o sinh liên ti p nh k thu t quay lui. Sau khi s t nhiên u tiên nat(N) ư c in ra nh write(N), h ng fail b t bu c th c hi n quay lui. Khi ó, lu t th hai ư c v n d ng t o sinh s t nhiên ti p theo và c th ti p t c cho n khi NSD quy t nh d ng chương trình (^C).
111 C u trúc danh sách Tóm t t chương 4 Danh sách là m t c u trúc ho c r ng, ho c g m hai ph n : ph n u là m t • ph n t và ph n còn l i là m t danh sách. Prolog qu n lý các danh sách theo c u trúc cây nh phân. Prolog cho phép • s d ng nhi u cách khác nhau bi u di n danh sách. [ Object1, Object2, ... ] ho c [ Head | Tail ] ho c [ Object1, Object2, ... | Others ] V i Tail và Others là các danh sách. Các thao tác c i n trên danh sách có th l p trình ư c là : ki m tra m t • ph n t có thu c v m t danh sách cho trư c không, phép ghép hai danh sách, b sung ho c lo i b m t ph n t u ho c cu i danh sách, trích ra m t danh sách con... Bài t p chương 4 1. Vi t m t th t c s d ng append xóa ba ph n t cu i cùng c a danh sách L, t o ra danh sách L1. Hư ng d n : L là phép ghép c a L1 v i m t danh sách c a ba ph n t ( ã b xóa kh i L). 2. Vi t m t dãy các ích xóa ba ph n t u tiên và ba ph n t cu i cùng c a m t danh sách L, tr v danh sách L2. 3. nh nghĩa quan h : last_element( Object, List ) sao cho Object ph i là ph n t cu i cùng c a danh sách List. Hãy vi t thành hai m nh , trong ó có m t m nh s d ng append, m nh kia không s d ng append. 4. nh nghĩa hai v t : even_length( List ) và odd_length( List ) ư c thõa mãn khi s các phân t c a danh sách List là ch n hay l tương ng. Ví d danh sách : có dài ch n, [ a, b, c, d ] [ a, b, c ] có dài l . 5. Cho bi t k t qu Prolog tr l i các câu h i sau : ?- [1,2,3] = [1|X]. ?- [1,2,3] = [1,2|X].
112 L p trình lôgic trong Prolog ?- [1 | [2,3]] = [1,2,X]. ?- [1 | [2,3,4]] = [1,2,X]. ?- [1 | [2,3,4]] = [1,2|X]. ?- b(o,n,j,o,u,r) =.. L. ?- bon(Y) =.. [X,jour]. ?- X(Y) =.. [bon,jour]. 6. Vi t chương trình Prolog ki m tra m t danh sách có ph i là m t t p h p con c a m t danh sách khác không ? Chương trình ho t ng như sau : ?- subset2([4,3],[2,3,5,4]). Yes 7. Vi t chương trình Prolog l y ra các ph n t t m t danh sách. Chương trình cũng có th chèn các ph n t vào m t danh sách ho t ng như sau : ?- takeout(3,[1,2,3],[1,2]). Yes ?- takeout(X,[1,2,3],L). X=1 L = [2, 3] ; X=2 L = [1, 3] ; X=3 L = [1, 2] ; No ?- takeout(4,L,[1,2,3]). 4 L= [4, 1, 2, 3] ; L= [1, 4, 2, 3] ; L= [1, 2, 4, 3] ; L= [1, 2, 3, 4] ; No 8. Vi t v t Prolog getEltFromList(L,N,E) cho phép l y ra ph n t th N trong m t danh sách. Th t b i n u danh sách không có N ph n t . Chương trình ho t ng như sau : ?- getEltFromList([a,b,c],0,X). No ?- getEltFromList([a,b,c],2,X). X=b ?- getEltFromList([a,b,c],4,X). No
113 C u trúc danh sách 9. Vi t chương trình Prolog tìm ph n t l n nh t và ph n t nh nh t trong m t danh sách các s . Chương trình ho t ng như sau : ?- maxmin([3,1,5,2,7,3],Max,Min). Max = 7 Min = 1 Yes ?- maxmin([2],Max,Min). Max = 2 Min = 2 Yes 10. Vi t chương trình Prolog chuy n m t danh sách ph c h p, là danh sách mà m i ph n t có th là m t danh sách con ch a các danh sách con ph c h p khác, thành m t danh sách ph ng là danh sách ch ch a các ph n t trong t t c các danh sách con có th , gi nguyên th t lúc u. Chương trình ho t ng như sau : flatten([[1,2,3],[4,5,6]], Flatlist). Flatlist = [1,2,3,4,5,6] Yes flatten([[1,[hallo,[[aloha]]],2,[],3],[4,[],5,6]], Flatlist) Flatlist = [1, hallo, aloha, 2, 3, 4, 5, 6] Yes 11. Vi t các chương trình Prolog th c hi n các v t x lý t p h p cho ph n lý thuy t (m c II). 12. S d ng v t forall vi t chương trình Prolog ki m tra hai danh sách có r i nhau (disjoint) không ? Chương trình ho t ng như sau : ?- disjoint([a,b,c],[d,g,f,h]). Yes ?- disjoint([a,b,c],[f,a]). No 13. V t forall(Cond, Action) th c hi n ki m tra s so kh p tương ng gi a Cond, thư ng k t h p v i v t member, và Action. Ví d dư i ây ki m tra vi c th c hi n các phép toán s h c trong danh sách L là úng n. ?- forall(member(Result = Formula, [2 = 1 + 1, 4 = 2 * 2]), Result =:= Formula). Result = _G615 Formula = _G616 Yes
114 L p trình lôgic trong Prolog 14. S d ng v t forall vi t chương trình Prolog ki m tra m t danh sách có là m t t p h p con c a m t danh sách khác hay không ? Chương trình ho t ng như sau : ?- subset3([a,b,c],[c,d,a,b,f]). Yes ?- subset3([a,b,q,c],[d,a,c,b,f]) No 15. S d ng v t append ghép hai danh sách vi t các chương trình Prolog th c hi n các vi c sau : prefixe(L1, L2) danh sách L1 ng trư c (prefixe list) danh sách L2. suffixe(L1, L2) danh sách L1 ng sau (suffixe list) danh sách L2. isin(L1, L2) các ph n t c a danh sách L1 có m t trong danh sách L2. 16. S d ng phương pháp Quicksort vi t chương trình Prolog s p x p nhanh m t danh sách các s ã cho theo th t tăng d n. 17. c hi u chương trình sau ây r i d ng l i thu t toán : /* Missionarys & Cannibals */ /* Tránh vòng l p */ lNotExist(_,[]). lNotExist(X,[T|Q]) :- X\==T, lNotExist(X,Q). /* Ki m tra tính h p lý c a tr ng thái */ valid(MG,CG,MD,CD) :- MG>=0, CG>=0, MD>=0, CD>=0, MG=0, MD>=CD. valid(MG,CG,MD,CD) :- MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD=0. valid(MG,CG,MD,CD) :- MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD>=CD. /* Xây d ng cung và ki m tra */ sail(1,0). sail(0,1). sail(1,1). sail(2,0). sail(0,2). arc([left,MGi,CGi,MDi,CDi],[droite,MGf,CGf,MDf,CDf]) :- sail(Mis,Can), MGf is MGi-Mis, MDf is MDi+Mis, CGf is CGi-Can, CDf is CDi+Can, valid(MGf,CGf,MDf,CDf). arc([right,MGi,CGi,MDi,CDi],[left,MGf,CGf,MDf,CDf]) :- sail(Mis,Can), MGf is MGi+Mis, MDf is MDi-Mis, CGf is CGi+Can, CDf is CDi-Can, valid(MGf,CGf,MDf,CDf). /* Phép quy */
115 C u trúc danh sách cross(A,A,[A],Non). cross(X,Y,Ch,Non) :- arc(X,A), lNotExist(A,Non), cross(A,Y,ChAY,[A|Non]), Ch=[X|ChAY]. /* i qua */ traverse(X,Y,Ch) :- cross(X,Y,Ch,[X]).
CHƯƠNG 5 K thu t l p trình Prolog I. Nhát c t I.1. Khái ni m nhát c t Như ã th y, m t trình Prolog ư c th c hi n nh các m nh và các ích. Sau ây ta s xét m t k thu t khác c a Prolog cho phép ngăn ch n s quay lui là nhát c t (cut). Prolog t ng quay lui khi c n tìm m t tìm ki m m t m nh khác tho mãn ích. i u này r t có ích i v i ngư i l p trình khi c n s d ng nhi u phương án gi i quy t v n . Tuy nhiên, n u không ki m soát t t quá trình này, vi c quay lui s tr nên kém hi u qu . Vì v y, Prolog s d ng k thu t nhát c t ki m soát quay lui, hay c m quay lui, kh c ph c khi m khuy t này. Trong ví d sau ây, m t chương trình Prolog s d ng k thu t quay lui kém hi u qu . Ta c n xác nh các v trí mà t ó chương trình b t u quá trình quay lui. Ta xét hàm b c thang Ta có ba quy t c xác nh quan h gi a hai tr c X và Y như sau : 1. N u X < 3 thì Y = 0 2. N u X ≤ 3 và X < 6 thì Y = 2 3. N u X ≤ 6 thì Y = 4 Ta vi t thành quan h nh phân f( X, Y ) trong Prolog như sau : % lu t 1 f( X, 0) :- X < 3. f( X, 2) :- 3 =< X, X < 6. % lu t 2 f( X, 4) :- 6 =< X. % lu t 3 117
L p trình lägich trong Prolog 118 Y - - 4- - 2- - +++++++++ 3 6 X Hình I.1.Hàm b c thang có hai b c. Khi ch y chương trình, gi s r ng bi n X c a hàm f( X, Y ) ã ư c nh n m t giá tr s có th th c hi n phép so sánh trong thân hàm. T ây, x y ra hai kh năng s d ng k thu t nhát c t như sau : I.2. K thu t s d ng nhát c t I.2.1. T o ích gi b ng nhát c t Gi s ta t ra câu h i : ?- f( 1, Y ), 2 < Y. Lúc này, Y nh n giá tr 0, ích th hai tr thành : 2
119 K thu t l p trình Prolog Prolog l i không bi t, cho nên c ti p t c áp d ng t t c các lu t m c dù i n th t b i. Trong ví d trên, lu t 1 ư c áp d ng t i v trí «Nhát c t» và gây ra th t b i. tránh s quay lui không c n thi t b t u t v trí này, chúng ta c n báo cho Prolog bi t m t cách tư ng minh, b ng cách s d ng m t nhát c t, ký hi u b i m t d u ch m than «!» th c ch t là m t ích gi (pseudo goal) ư c chèn vào gi a các ích th t khác. Chương trình hàm b c thang ư c vi t l i như sau : f( X, 0) :- X < 3, !. % lu t 1 f( X, 2) :- 3 =< X, X < 6, !. % lu t 2 f( X, 4) :- % lu t 3 6 =< X. Nhát c t ! s c m m i quá trình quay lui t v trí xu t hi n c a nó trong chương trình. N u bây gi ta yêu c u th c hi n ích : ?- f( 1, Y ), 2 < Y. Prolog ch th c hi n nhánh trái nh t ng v i lu t 1 trong hình trên, tr v k t qu th t b i vì x y ra 2 < 0 mà không ti p t c quay lui th c hi n các nhánh tương ng v i lu t 2 và 3, do ã g p nhát c t !. Chương trình m i s d ng nhát c t ch y hi u qu hơn chương trình cũ. Khi x y ra th t b i, Prolog s nhanh chóng d ng, mà không m t th i gian th c hi n nh ng vi c vô ích khác. S d ng nhát c t trong m t chương trình làm thay i nghĩa th t c nhưng không làm thay i nghĩa khai báo. Tuy nhiên sau ây ta s th y r ng nhát c t có th làm m t i nghĩa khai báo. I.2.2. Dùng nhát c t lo i b hoàn toàn quay lui Gi s bây gi ta g i th c hi n ích : ?- f( 7, Y ). Y=4 Yes Quá trình th c hi n ư c mô t như sau : trư c khi nh n ư c k t qu , v nguyên t c, Prolog ph i s d ng c ba lu t có quá trình xoá ích. Th lu t 1 7 < 3 th t b i, quay lui, th lu t 2 (nhát c t chưa ư c s d ng). Th lu t 2 3 ≤ 7 tho mãn, nhưng 7 < 6 th t b i, quay lui, th lu t 3 (nhát c t chưa ư c s d ng). Th lu t 3 6
L p trình lägich trong Prolog 120 th nh t th t b i, thì ích th hai b t bu c ph i ư c tho mãn vì nó là ph nh c a ích th nh t. Vi c ki m tra l n n a s tr nên dư th a vì ích tương ng v i nó có th b xoá. Như v y vi c ki m tra ích 6
121 K thu t l p trình Prolog Ta g i « ích cha» là ích tương ng v i ph n u c a m nh ch a nhát c t. Ngay khi g p nhát c t, Prolog xem r ng m t ích ã ư c tho mãn m t cách t ng, và gí i h n s l a ch n các m nh trong ph m vi gi a l i g i ích cha và th i i m th c hi n nhát c t. T t c các m nh tương ng v i các ích con chưa ư c ki m tra so kh p gi a ích cha và nhát c t u ư c b qua. minh ho , ta xét m nh có d ng : H :- G1, G2, ... Gm, ! , ... , Bn. Gi s r ng m nh này ư c kh i ng b i m t ích G h p nh t ư c v i H, khi ó, G là ích cha. Cho n khi g p nhát c t, Prolog ã tìm ư c các l i gi i cho các ích con G1, G2, ... Gm. Ngay sau khi th c hi n nhát c t, các ích con G1, G2, ... Gm b «vô hi u hoá», k c các m nh tương ng v i các ích con này cũng b b qua. Hơn n a, do G h p nh t v i H nên Prolog không ti p t c tìm ki m so kh p H v i u (head) c a các m nh khác. Ch ng h n, áp d ng nguyên lý trên cho ví d sau : C :- P, Q, R, ! S, T, U. C :- V. A :- B, C, D. ?- A. Gi s A, B, C, D, P, ... u là các h ng. Tác ng c a nhát c t khi th c hi n ích C như sau : quá trình quay lui x y ra bên trong danh sách các ích P, Q, R, nhưng ngay khi th c hi n nhát c t, m i con ư ng d n n các m nh trong danh sách P, Q, R u b b qua. M nh C th hai : C :- V. cũng b b qua. Tuy nhiên, vi c quay lui v n có th x y ra bên trong danh sách các ích S, T, U. ích cha c a m nh ch a nhát c t là C trong m nh : A :- B, C, D. Như v y, nhát c t ch tác ng i v i m nh C, mà không tác ng i v i A. Vi c quay lui t ng trong danh sách các ích B, C, D v n ư c th c hi n, c l p v i nhát c t hi n di n trong C. I.2.3. Ví d s d ng k thu t nhát c t 1. Tìm s max Xây d ng chương trình tìm s l n nh t trong hai s có d ng : max( X, Y, MaX )
L p trình lägich trong Prolog 122 trong ó, Max = X n u X l n hơn ho c b ng Y, và Max = Y n u X nh hơn ho c b ng Y. Ta xây d ng hai quan h như sau : max( X, Y, X ) :- X >= Y. max( X, Y, Y ) :- X < Y. Hai quan h trên lo i tr l n nhau. N u quan h th nh t tho mãn, thì quan h th 2 ch có th th t b i và ngư c l i. Áp d ng d ng i u ki n quen thu c «n u-thì-n u không thì» làm g n chương trình l i như sau : N u X ≥ Y thì Max = X, N u không thì Max = Y. S d ng k thu t nhát c t, chương trình ư c vi t l i như sau : max( X, Y, X ) :- X >= Y, !. max( X, Y, Y ). 2. Ki m tra m t ph n t có thu c danh sách ã cho không Ta ã xây d ng quan h : membre( X, L). ki m tra ph n t X có n m trong danh sách L hay không. Chương trình như sau : membre( X, [X | L]). membre( X, [X | L]) :- membre( X, L). Tuy nhiên, chương trình này ho t ng m t cách «không ơn nh». N u X xu t hi n nhi u l n trong danh sách, thì b t kỳ ph n t nào b ng X cũng ư c tìm th y. Bây gi ta chuy n membre thành m t quan h ơn nh ch tác ng i v i ph n t X u tiên. Vi c thay i r t ơn gi n như sau : ch vi c c m quay lui ngay khi X ư c tìm th y, nghĩa là khi m nh u tiên ư c tho mãn : membre( X, [ X | L ]) :- !. membre( X, [ X | L ]) :- membre( X, L). Khi ó, trong ví d sau, Prolog ch ưa ra m t l i gi i : ?- membre( X, [a, a, b, c]). X=a; No 3. Thêm m t ph n t vào danh sách mà không b trùng l p Thông thư ng, khi mu n thêm m t ph n t m i, ch ng h n X, vào danh sách L, ngư i ta mu n trư c ó, L không ch a ph n t này. Gi s quan h c n xây d ng :
123 K thu t l p trình Prolog ajoute( X, L, L1) có X là ph n t m i c n thêm vào danh sách L, L1 là k t qu có ch a úng m t X. Ta l p lu n như sau : N u X thu c danh sách L, thì L1 = L, N u không, L1 là L ã ư c thêm X vào. Cách ơn gi n nh t là chèn ph n t X vào ngay u danh sách sao cho nó là ph n t u (head) c a L1. Ta có chương trình như sau : ajoute( X, L, L) :- membre( X, L), !. ajoute( X, L, [ X | L ] ). Sau ây là các v n d ng chương trình : ?- ajoute( a, [ b, c ], L). L = [ a, b, c ] ?- ajoute( X, [ b, c ], L). L = [ b, c ] X=b ?- ajoute( a, [ b, c, X ], L). X = _G333 L = [a, b, c, _G333] ?- ajoute( a, [ a, b, c ], L). L = [a, b, c]; Trong ví d này, nh s d ng k thu t nhát c t, ngư i l p trình d dàng thêm m t ph n t m i vào danh sách mà không làm trùng l p ph n t ó. N u không s d ng k thu t nhát c t, vi c thêm m t ph n t m i vào m t danh sách có th làm trùng l p ph n t . Như v y, k thu t nhát c t không nh ng làm t i ưu hi u qu l p trình, mà còn r t c n thi t c t úng n m i quan h gi a các i tư ng. 4. S d ng nhát c t phân lo i d li u Gi s ta c n qu n lý m t CSDL ch a k t qu các tr n u c a các h i viên m t câu l c b qu n v t. Các tr n u không ư c s p x p m t cách có h th ng, mà m i h i viên có th u v i b t c ai. K t qu các tr n u ư c bi u di n b i các s ki n như sau : bat( tom, jim). bat( ann, tom). bat( pat, jim). Ta c n nh nghĩa quan h : classe(Player, CategorY ).
L p trình lägich trong Prolog 124 phân th h ng cho m i ngư i chơi qu n v t trong ba h ng như sau : ngư i luôn th ng trong t t c các tr n u champion ngư i có c bàn th ng và có c bàn thua combative ngư i luôn thua trong t t c các tr n u dilettante T k t qu nh ng tr n u ã có ư c cho trong các s ki n, ta th y Ann và Pat ư c x p h ng quán quân (champion), Tom ư c x p h ng trung bình (combative), còn Jim thì ư c x p h ng y u kém (dilettante). Ta có th d dàng xây d ng các lu t x p h ng như sau : X ư c x p h ng trung bình n u t n t i Y sao cho X th ng Y, và t n t i Z sao cho Z th ng X. X ư c x p h ng quán quân n u X th ng Y, và X không b thua b t kỳ i th nào. Lu t x p h ng quán quân có ch a phép ph nh (not) mà cho n lúc này, ta chưa tìm hi u cách bi u di n như th nào trong Prolog. Lu t x p h ng y u kém cũng xây d ng tương t lu t x p h ng quán quân. Ta có th s d ng sơ if- then-else x lý ng th i hai tình hu ng như sau : N u X th ng và X b thua khi u v i b t kỳ ai thì X ư c x p h ng trung bình n u không, n u X th ng b t kỳ ai thì X ư c x p h ng quán quân n u không, n u X luôn b thua thì X ư c x p h ng y u kém. T sơ trên ta có th chuy n sang Prolog s d ng k thu t nhát c t x lý kh năng lo i tr nhau gi a ba th h ng. classe( X, combative) :- bat( X, _ ), bat( _, X ), !. classe( X, champion) :- bat( X, _ ), !. classe( X, dilettante) :- bat( _, X ). Chú ý r ng không nh t thi t ph i s d ng nhát c t trong m nh champion vì b n ch t c a ba th h ng.
125 K thu t l p trình Prolog I.3. Phép ph nh I.3.1. Ph nh b i th t b i Trong Prolog, ta có th nói ư c câu : «Marie thích t t c loài ng v t tr loài r n» hay không ? i v i v th nh t, ta có th d dàng d ch ra thành : Dù X là gì, Marie thích X n u X là loài ng v t : enjoy( marie, X ) :- animal( X ). Tuy nhiên c n lo i tr loài r n. Lúc này ta c n d ch ra như sau : N u X là loài r n, thì «Marie thích X» là sai, N u không, n u X là loài ng v t thì Marie thích X. Nh ng gì không úng thì có th s d ng ích c bi t fail (th t b i) luôn luôn sai, và cũng làm cho ích cha th t b i. Chương trình ư c vi t l i như sau : enjoy( marie, X ) :- serpent( X ), !, fail. enjoy( marie, X ) :- animal( X ). Lu t th nh t x lý tình hu ng Marie không thích loài r n : n u X là loài r n, thì nhát c t s ngăn s quay lui (và do ó, lu t th hai không ư c th c hi n), và ích fail s gây ra th t b i. Ta có th s d ng d u ; vi t cô ng hai lu t thành m t lu t như sau : enjoy( marie, X ) :- serpent( X ), !, fail; animal( X ). M t cách tương t , ta nh nghĩa quan h khác nhau : diffĩrent( X, Y ) tho mãn n u X và Y là khác nhau. Do s khác nhau có th ư c di n gi i theo nhi u cách nên ta c n ch rõ như sau : • X và Y không ph i là các tr c h ng (literal) ng nh t, • X và Y không th kh p v i nhau, • Các giá tr c a các bi u th c s h c X và Y không th b ng nhau. Ta nói r ng X và Y khác nhau do chúng không th kh p ư c v i nhau : N u X và Y là ng nh t, thì diffĩrent( X, Y ) th t b i, N u không, diffĩrent( X, Y ) thành công. Ta s d ng nhát c t và ích fail vi t quan h này thành hai lu t : diffĩrent( X, X ) :- !, fail.
L p trình lägich trong Prolog 126 diffĩrent( X, Y ). Ho c vi t l i thành m t lu t như sau : diffĩrent( X, Y ) :- X = Y, !, fail; true. Chú ý r ng ích true ( úng) luôn luôn thành công. T ây, ta có th nh nghĩa v t not(Goal) cho phép ki m tra ích không tho mãn như sau : N u Goal tho mãn, thì not(Goal) th t b i, N u không, not(Goal) thành công. Chương trình Prolog : not( P ) :- P, !, fail; true. H u h t các phiên b n Prolog hi n nay u có v t not not(2 = 3). Yes ?- not(2 = 2). No S d ng v t not, ta có th nh nghĩa l i các quan h enjoy, diffĩrent và classe như sau : enjoy( marie, X ) :- animal( X ), not (serpent( X )). diffĩrent( X, Y ) :- not( X = Y ). classe( X, combatif) :- bat( X, _ ), bat( _ , X ). classe( X, champion) :- bat( X _ ), not bat( _ , X ). classe( X, dilettante) :- bat( _ , X ), not bat( X, _ ).
127 K thu t l p trình Prolog I.3.2. S d ng k thu t nhát c t và ph nh Ưu i m c a k thu t nhát c t có th tóm t t như sau : 1. Nâng cao tính hi u qu c a m t chương trình nh nguyên t c thông báo m t cách tư ng minh cho Prolog tránh không i theo nh ng con ư ng d n n th t b i. 2. K thu t nhát c t cho phép xây d ng nh ng lu t có tính ch t lo i tr nhau có d ng : N u i u ki n P x y ra thì k t lu n là Q, N u không, thì k t lu n là R. Tuy nhiên s d ng nhát c t có th làm m t s tương ng gi a nghĩa khai báo và nghĩa th t c c a m t chương trình. N u trong chương trình không xu t hi n nhát c t, thì vi c thay i th t các m nh và các ích ch làm nh hư ng n hi u qu ch y chương trình mà không làm thay i nghĩa khai báo. Còn khi có m t nhát c t trong m t chương trình, thì l i x y ra v n , lúc này có th có th nhi u k t qu khác nhau. Ví d : p :- a, b. p :- c. Xét v m t nghĩa khai báo, chương trình trên có nghĩa : p úng n u và ch n u c a và b u úng, ho c c úng. T ó ta xây d ng bi u th c lôgich như sau : p ⇔ (a ∧ b) ∨ c Nghĩa khai báo không còn úng n a n u ta thay i m nh th nh t b n g cách thêm vào m t nhát c t : p :- a, !, b. p :- c. Bi u th c lôgich tương ng như sau : p ⇔ (a ∧ b) ∨ (~a ∧ c) N u ta o th t hai m nh : p :- c. p :- a, !, b. thì ta l i có cùng nghĩa như ban u: p ⇔ c ∨ (a ∧ b) Ngư i ta ph i th n tr ng khi s d ng k thu t nhát c t do nhát c t làm thay i nghĩa th t c và làm tăng nguy cơ x y ra sai sót trong chương trình. Như ã xét trong các ví d trư c ây, vi c lo i b nhát c t có th làm thay i nghĩa khai báo c a m t chương trình. Tuy nhiên trong m t s trư ng h p, nhát c t không
L p trình lägich trong Prolog 128 nh hư ng n nghĩa khai báo. Ngư i ta g i nh ng nhát c t không làm thay i ng nghĩa c a chương trình là nhát c t xanh (green cuts). ng trên quan i m l p trình d c và d hi u (readability), các nhát c t xanh là an toàn và ngư i ta thư ng hay s d ng chúng. Th m chí, ngư i ta có th b qua s có m t c a chúng khi c chương trình. Ngư i ta nói nhát c t xanh làm rõ ràng (explicit) tính ti n nh (determinism) v n không rõ ràng (implicit). Thông thư ng nhát c t xanh ư c t ngay sau phép ki m tra ti n nh. Ví d s d ng nhát c t xanh tìm s min : minimum(X, Y, X) :- X =< Y, !. minimum(X, Y, Y) :- X > Y, !. Ví d s d ng nhát c t xanh ki m tra ki u c a cây nh phân các s nguyên : int_bin_tree(ab(X,G,D)) :- integer(X), int_bin_tree(G), int_bin_tree(D). int_bin_tree(X) :- integer(X). Trong các trư ng h p khác, các nhát c t nh hư ng n nghĩa khai báo ư c g i là nhát c t (red cuts). S có m t c a các nhát c t thư ng làm cho chương trình tr nên khó c, khó hi u. s d ng ư c chúng, NSD ph i h t s c chú ý. Ví d s d ng nhát c t tìm s min thay i ng nghĩa : minimum_cut( X, Y, X ) :- X =< Y, !. minimum_cut( X, Y, Y ). Trong m t s trư ng h p, m t câu h i có th không liên quan n ng nghĩa c a chương trình. Ví d v t ki m tra m t ph n t có thu c danh sách không : member_cut(X, [ X | _ ] ) :- !. member_cut(X, [ _ | L ] ) :- member_cut(X, L ). V i câu h i member_cut(X, [ 1, 2, 3 ] ) s không cho k t qu X= 2. ?- member_cut(X, [ 1, 2, 3 ] ). X=1; No Thông thư ng, ích fail ư c dùng c p ôi v i nhát c t (cut-fail). Ngư i ta thư ng nh nghĩa phép ph nh m t ích (not) b ng cách gây ra s th t b i c a ích này, th c ch t là cách s d ng nhát c t có h n ch . chương trình d hi u