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

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

Thêm vào BST

Báo xấu

154
lượt xem 50
download

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

Nguyên lý của prlog dựa trên phép suy diễn logic, liên quan đến những khái niệm toán học như phép hợp nhất herbran, hợp giả Robinson, logic vị từ bậc một

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 3

31 Ng nghĩa c a chương trình Prolog II.1. Nghĩa khai báo c a chương trình Prolog V m t hình th c, nghĩa khai báo, hay ng nghĩa ch ý (intentional semantic) xác nh các m i quan h ã ư c nh nghĩa trong chương trình. Nghĩa khai báo xác nh nh ng gì là k t qu ( ích) mà chương trình ph i tính toán, ph i t o ra. Nghĩa khai báo c a chương trình xác nh n u m t ích là úng, và trong trư ng h p này, xác nh giá tr c a các bi n. Ta ưa vào khái ni m th nghi m (instance) c a m t m nh C là m nh C mà m i m t bi n c a nó ã ư c thay th b i m t h ng. M t bi n th (variant) c a m t m nh C là m nh C sao cho m i m t bi n c a nó ã ư c thay th b i m t bi n khác. Ví d II.1 : Cho m nh : hasachild(X) :- parent(X, Y). Hai bi n th c a m nh này là : hasachild(A) :- parent(A, B). hasachild(X1) :- parent(X1, X2). Các th nghi m c a m nh này là : hasachild(tom) :- parent(tom, Z). hasachild(jafa) :- parent(jafa, small(iago)). Cho trư c m t chương trình và m t ích G, nghĩa khai báo nói r ng : M t ích G là úng (tho mãn, hay suy ra ư c t chương trình m t cách logic) n u và ch n u (1) t n t i m t m nh C c a chương trình sao cho (2) t n t i m t th nghi m I c a m nh C sao cho: (a) ph n u c a I là gi ng h t G, và (b) m i ích c a ph n thân c a I là úng. nh nghĩa trên ây áp d ng ư c cho các câu h i Prolog. Câu h i là m t danh sách các ích ngăn cách nhau b i các d u ph y. M t danh sách các ích là úng n u t t c các ích c a danh sách là úng cho cùng m t ràng bu c c a các bi n. Các giá tr c a các bi n là nh ng giá tr ràng bu c t ng quát nh t.
32 L p trình lôgic trong Prolog II.2. Khái ni m v gói m nh (packages of clauses) là t p h p các m nh M t gói hay bó m nh có cùng tên h ng t chính (cùng tên, cùng s lư ng tham i). Ví d sau ây là m t gói m nh : a(X) :- b(X, _). a(X) :- c(X), e(X). a(X) :- f(X, Y). Gói m nh trên có ba m nh có cùng h ng là a(X). M i m nh c a gói là m t phương án gi i quy t bài toán ã cho. Prolog quy ư c : • m i d u ph y (comma) t gi a các m nh , hay các ích, óng vai trò phép h i (conjunction). V m t lôgich, chúng ph i úng t t c . • m i d u ch m ph y (semicolon) t gi a các m nh , hay các ích, óng vai trò phép tuy n (disjunction). Lúc này ch c n m t trong các ích c a danh sách là úng. Ví d II.2 : P :- Q; R. ư c c là : P úng n u Q úng ho c R úng. Ngư i ta cũng có th vi t tách ra thành hai m nh : P :- Q. P :- R. Trong Prolog, d u ph y (phép h i) có m c ưu tiên cao hơn d u ch m ph y (phép tuy n). Ví d : P :- Q, R; S, T, U. ư c hi u là : P :- (Q, R); (S, T, U). và có th ư c vi t thành hai m nh : P :- (Q, R). P :- (S, T, U). Hai m nh trên ư c c là : P úng n u ho c c Q và R u úng, ho c c S, T và U u úng. V nguyên t c, th t th c hi n các m nh trong m t gói là không quan tr ng, tuy nhiên trong th c t , c n chú ý tôn tr ng th t c a các m nh . Prolog s l n lư t th c hi n theo th t xu t hi n các m nh trong gói và trong chương trình theo mô hình tu n t b ng cách th quay lui mà ta s xét sau ây.
33 Ng nghĩa c a chương trình Prolog II.3. Nghĩa lôgich c a các m nh Nghĩa lôgich th hi n m i liên h gi a c t lôgich (logical specification) c a bài toán c n gi i v i b n thân chương trình. 1. Các m nh không ch a bi n Nghĩa lôgich M nh Ký hi u Toán h c P(X) úng n u X = a P(a). P(X) ⇔ X = a P(X) ⇔ (X = a) ∨ (X P(a). P(X) úng n u X = a ho c X = b P(b). = b) P(X) úng n u X = a và Q(c) P(a) :- P(X) ⇔ X = a ∧ Q(c) úng Q(c). P(X) ⇔ (X = a ∧ P(a) :- P(X) úng n u ho c (X = a và Q(c). Q(c)) Q(c) úng) ho c X = b P(b). ∨ (X = b) Quy ư c : n u = n u và ch n u. 2. Các m nh có ch a bi n Nghĩa lôgich M nh Ký hi u Toán h c V i m i giá tr c a X, P(X) úng P(X). ∀X P(X) V i m i giá tr c a X, P(X) úng n u Q(X) P(X) :- P(X) ⇔ Q(X) úng Q(X). V i m i giá tr c a X, P(X) úng n u t n t i P(X) :- Q(X, Y). Y là m t bi n c c b sao cho Q(X, Y) P(X) ⇔ ∃Y Q(X, Y) úng V i m i giá tr c a X, P(X) úng n u t n t i P(X) :- m t giá tr nào ó c a Y sao cho Q(X, Y) Q(X, P(X) ⇔ ∃Y Q(X, Y) úng (không quan tâm n giá tr c a Y như _). th nào) P(X) :- V i m i giá tr c a X, P(X) úng n u t n t i P(X) ⇔∃Y Q(X, Y) ∧ Q(X, Y sao cho Q(X, Y) và R(Y) úng Y), R(Y) R(Y). P(X) :- V i m i giá tr c a X, P(X) úng n u ho c P(X) ⇔ (∃Y Q(X, Y) Q(X, t n t i Y sao cho Q(X, Y) và R(Y) úng, Y), ∧ R(Y)) R(Y). ho c X = a ∨ (X = a) p(a).
34 L p trình lôgic trong Prolog 3. Nghĩa lôgich c a các ích Nghĩa lôgich ích Có ph i p(a) úng (tho mãn) ? p(a). p(a), Q(b). Có ph i c p(a) và Q(b) u úng ? Cho bi t giá tr c a X P(X) là úng ? P(X). Cho bi t các giá tr c a X và c a Y P(X) và Q(X, P(X), Q(X, Y). u là úng ? Y) II.4. Nghĩa th t c c a Prolog Nghĩa th t c, hay ng nghĩa thao tác (operational semantic), l i xác nh nh n ư c k t qu , nghĩa là làm cách nào các quan h ư c làm cách nào x lý th c s b i h th ng Prolog. Nghĩa th t c tương ng v i cách Prolog tr l i các câu h i như th nào (how) hay l p lu n trên các tri th c. Tr l i m t câu h i có nghĩa là tìm cách xóa m t danh sách. i u này ch có th th c hi n ư c n u các bi n xu t hi n trong các ích này ư c ràng bu c sao cho chúng ư c suy ra m t cách lôgich t chương trình (hay t các tri th c ã ghi nh n). Prolog có nhi m v th c hi n l n lư t t ng ích trong m t danh sách các ích t m t chương trình ã cho. «Th c hi n m t ích» có nghĩa là tìm cách tho mãn hay xoá ích ó kh i danh sách các ích ó. chương trình (s ki n+lu t) d u hi u thành danh sách các ích execute công/th t b i ràng bu c các bi n Hình II.1. Mô hình vào/ra c a m t th t c th c hi n m t danh sách các ích. G i th t c này là execute (th c hi n), cái vào và cái ra c a nó như sau : Cái vào : m t chương trình và m t danh sách các ích Cái ra : m t d u hi u thành công/th t b i và m t ràng bu c các bi n Nghĩa c a hai cái ra như sau : (1) D u hi u thành công/th t b i là Yes n u các ích ư c tho mãn (thành công), là No n u ngư c l i (th t b i). (2) S ràng bu c các bi n ch x y ra n u chương trình ư c th c hi n.
35 Ng nghĩa c a chương trình Prolog Ví d II.3 : Minh ho cách Prolog tr l i câu h i cho ví d chương trình gia h trư c ây như sau : ích c n tìm là : ?- ancestor(tom, sue) Ta bi t r ng parent(bill, sue) là m t s ki n. s d ng s ki n này và lu t 1 (v t tiên tr c ti p), ta có th k t lu n r ng ancestor(bill, sue). ây là m t s ki n kéo theo : s ki n này không có m t trong chương trình, nhưng có th ư c suy ra t các lu t và s ki n khác. Ta có th vi t g n s suy di n này như sau : ⇒ parent(bill, sue) ancestor(bill, sue) Nghĩa là parent(bill, sue)kéo theo ancestor(bill, sue) b i lu t 1. Ta l i bi t r ng parent(tom, bill) cũng là m t s ki n. M t khác, t s ki n ư c suy di n ancestor(bill, sue), lu t 2 (v t tiên gián ti p) cho phép k t lu n r ng ancestor(tom, sue). Quá trình suy di n hai giai o n này ư c vi t : ⇒ ancestor(bill, sue) parent(bill, sue) parent(tom, bill) và ancestor(bill, sue) ⇒ ancestor(tom, sue) Ta v a ch ra các giai o n xoá m t ích, g i là m t ch ng minh. Tuy nhiên, ta chưa ch ra làm cách nào Prolog nh n ư c m t ch ng minh như v y. Prolog nh n ư c phép ch ng minh này theo th t ngư c l i nh ng gì ã trình bày. Thay vì xu t phát t các s ki n ch a trong chương trình, Prolog b t u b i các ích và, b ng cách s d ng các lu t, nó thay th các ích này b i các ích m i, cho n khi nh n ư c các s ki n sơ c p. xoá ích : ?- ancestor(tom, sue). Prolog tìm ki m m t m nh trong chương trình mà ích này ư c suy di n ngay l p t c. Rõ ràng ch có hai m nh tho mãn yêu c u này là lu t 1 và lu t 2, liên quan n quan h ancestor. Ta nói r ng ph n u c a các lu t này tương ng v i ích. Hai m nh này bi u di n hai kh năng mà Prolog ph i khai thác x lý. Prolog b t u ch n x lý m nh th nh t xu t hi n trong chương trình : ancestor(X, Z) :- parent(X, Z). Do ích là ancestor(tom, sue), các bi n ph i ư c ràng bu c như sau :
36 L p trình lôgic trong Prolog X = tom, Z = sue Lúc này, ích ban u tr thành : parent(tom, sue) Hình dư i ây bi u di n giai o n chuy n m t ích thành ích m i s d n g m t lu t. Th t b i x y ra khi không có ph n u nào trong các m nh ca chương trình tương ng v i ích parent(tom, sue). ancestor(tom, sue) B i lu t 1 parent(tom, sue) Hình II.2. X lý bư c u tiên : ích phía trên ư c tho mãn n u Prolog có th xoá ích phía dư i. Lúc này Prolog ph i ti n hành quay lui (backtracking) tr l i ích ban u, ti p t c x lý m nh khác là lu t th hai : ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). Tương t bư c x lý th nh t, các bi n X và Z ư c ràng bu c như sau : X = tom, Z = sue ích phía trên ancestor(tom, sue) ư c thay th b i hai ích là : parent(tom, Y), ancestor(Y, sue). Nhưng lúc này, Y chưa có giá tr . Lúc này c n xoá hai ích. Prolog s ti n hành xoá theo th t xu t hi n c a chúng trong chương trình. i v i ích th nh t, vi c xoá r t d dàng vì ó là m t trong các s ki n c a chương trình. S tương ng s ki n d n n Y ư c ràng bu c b i giá tr bill. Các giai o n th c hi n ư c mô t b i cây h p gi i sau ây :
37 Ng nghĩa c a chương trình Prolog ancestor(tom, sue) B i lu t 1 B i lu t 2 Th t b i parent(tom, parent(tom, Y) sue) ancestor(Y, Hình II.3. Các giai o n th c hi n x lý xoá ích. Sau khi ích th nh t parent(tom, bill) tho mãn, còn l i ích th hai : ancestor(bill, sue) cũng ph i ư c tho mãn M t l n n a, lu t 1 ư c s d ng. Chú ý r ng vi c áp d ng l n th hai cùng lu t này không liên quan gì n l n áp d ng th nh t. Prolog s d ng các bi n m i m i l n lu t ư c g i n. Lu t 1 bây gi có th ư c t tên l i như sau : ancestor(X’, Z’) :- parent(X’, Z’). Ph n u ph i tương ng v i ích th nh t, ancestor(bill, sue), t c là : X’ = bill, Z’ = sue ancestor(tom, B i lu t 1 B i lu t 2 parent(tom, Y) parent(tom, sue) ancestor(Y, sue) Y = bill b i Th t b i parent(tom, bill) ancestor(bill, sue) B i lu t 1 Thành công parent(bill, Hình II.4. Quá trình th c hi n xoá ích ancestor(tom, sue). T ó ích (trong ph n thân) ph i thay th b i : parent(bill, sue) ích này ư c tho mãn ngay l p t c, vì chính là m t s ki n trong chương trình. Quá trình x lý ư c minh ho l i y trong Hình II.4.
38 L p trình lôgic trong Prolog Hình 2.4. có d ng m t cây. M i nút tương ng v i m t ích, hay m t danh sách các ích c n tho mãn. M i cung n i hai nút tương ng v i vi c áp d n g m t lu t trong chương trình. Vi c áp d ng m t lu t cho phép chuy n các ích c a m t nút thành các ích m i c a m t nút khác. ích trên cùng (g c c a cây) ư c xoá khi tìm ư c m t con ư ng i t g c n lá có nhãn là thành công. M t nút lá có nhãn là thành công khi trong nút là m t s ki n c a chương trình. Vi c th c thi m t chương trình Prolog là vi c tìm ki m nh ng con ư ng như v y. Nhánh bên ph i ch ng t r ng có th xoá ích. Trong quá trình tìm ki m, có th x y ra kh năng là Prolog i trên m t con ư ng không t t. Khi g p nút ch a m t s ki n không t n t i trong chương trình, xem như th t b i, nút ư c g n nhãn th t b i, ngay l p t c Prolog t ng quay lui lên nút phía trên, ch n áp d ng m t m nh ti p theo có m t trong nút này ti p t c con ư ng m i, ch ng nào thành công. Ví d trên ây, ta ã gi i thích m t cách không hình th c cách Prolog tr l i câu h i. Th t c execute dư i ây mô t hình th c và có h th ng hơn v quá trình này. th c hi n danh sách các ích : G1, G2, ..., Gm th t c execute ti n hành như sau : N u danh sách các ích là r ng, th t c thành công và d ng. • N u danh sách các ích khác r ng, th t c duy t scrutinize sau ây • ư c th c hi n Th t c scrutinize : Duy t các m nh trong chương trình b t u t m nh u tiên, cho n khi nh n ư c m nh C có ph n u trùng kh p v i ph n u c a ích u tiên G1. N u không tìm th y m t m nh nào như v y, th t c rơi vào tình tr ng th t b i. N u m nh C ư c tìm th y, và có d ng : H :- D1, ..., Dn khi ó, các bi n c a C ư c t tên l i nh n ư c m t bi n th C’ không có bi n nào chung v i danh sách G1, G2, ..., Gm. M nh C’ như sau : H’ :- D’1, ..., D’n
39 Ng nghĩa c a chương trình Prolog Gi s S là ràng bu c c a các bi n t vi c so kh p gi a G1 và H’, Prolog thay th G1 b i D’1, ..., D’n trong danh sách các ích nh n ư c m t danh sách m i : D1’, ..., Dn’, G2, ..., Gm Chú ý r ng n u C là m t s ki n, khi ó, n=0 và danh sách m i s ng n hơn danh sách cũ. Trư ng h p danh sách m i r ng, k t qu thành công. Thay th các bi n c a danh sách m i này b i các giá tr m i ch nh b i ràng bu c S, ta nh n ư c m t danh sách các ích m i : D"1, ..., D"n, G"2, ..., G"m Th c hi n th t c m t cách quy cho danh sách các ích m i này. N u k t thúc thành công, ti p t c th c hi n danh sách ban u. Trong trư ng h p ngư c l i, Prolog b qua danh sách các ích quay lui l i th t c scrutinize. Quá trình tìm ki m các m nh trong chương trình ư c b t u l i t sau m nh C, v i m t m nh m i.
40 L p trình lôgic trong Prolog Quá trình th c hi n th t c execute ư c mô t như sau : G1, G2, ..., Gm Chương trình Prolog Không có bi n hay cơ s d li u trùng nhau : C' : H’ :- D’1, Gi, D’j, ..., D’n H' .. . N u n=0 C H :- D1, S = (G1| H’) m nh m i ..., Dn s ng n hơn D1’, ..., Dn’, G2, ..., G D"1, ..., D"n, G"2, ..., G" Hình II.5. Quá trình th c hi n execute. Sau ây là th t c execute ư c vi t b ng gi ng Pascal. Procedure execute(program, goallist, success); { Tham i vào : danh sách các m nh program danh sách các ích goallist i ra : Tham ki u Boolean, là true n u goallist là true i v i tham success i program Các bi n c c b : ích goal othergoals danh sách các ích ki u Boolean satisfied ki u Boolean matchOK ràng bu c c a các bi n process các ích H, H’, D1, D1’, ..., Dn, Dn’ Các hàm ph : có giá tr true n u L là danh sách r ng empty(L) tr v ph n t u tiên c a danh sách L head(L) tr v danh sách L sau khi ã b i ph n t u tiên tail(L) add(L1, L2) ghép danh sách L2 vào sau danh sách L1 match(T1, T2, matchOK, process) so kh p các h ng T1 và T2, n u thành công, bi n matchOK có giá tr true, và process ch a các ràng bu c tương ng v i các bi n.
41 Ng nghĩa c a chương trình Prolog substitute(process, goals) thay th các bi n c a goals b i giá tr ràng bu c tương ng trong process. } begin { execute_main } if empty(goallist) then success:= true else begin goal:= head(goallist); othergoals:= tail(goallist); satisfied:= false; while not satisfied and there_are_again_some_terms do begin Let the following clause of program is: H :- D1, ..., Dn constructing a variant of this clause: H’ :- D1’, ..., Dn’ match(goal, H’, matchOK, process) if matchOK then begin newgoals:= add([ D1’, ..., Dn’ ], othergoals); newgoals:= substitute(process, newgoals); execute(program, newgoals, satisfied) end { if } end; { while } satisfied:= satisfied end end; { execute_main } T th t c execute trên ây, ta có m t s nh n xét sau. Trư c h t, th t c không mô t làm cách nào nh n ư c ràng bu c cu i cùng cho các bi n. Chính ràng bu c S ã d n n thành công nh các l i g i quy. Milnligi quy execute th t b i (tương ng v i m nh C), th t c scrutinize tìm ki m m nh ti p theo ngay sau m nh C. Quá trình th c thi là hi u qu , vì Prolog b qua nh ng ph n vô ích r sang nhánh khác. Lúc này, m i ràng bu c cho bi n thu c nhánh vô ích b lo i b hoàn toàn. Prolog s l n lư t duy t h t t t c các con ư ng có th n thành công. Ta cũng ã th y r ng ngay sau khi có m t k t qu tích c c, NSD có th yêu c u h th ng quay lui tìm ki m m t k t qu m i. Chi ti t này ã không ư c x lý trong th t c execute. Trong các cài t Prolog hi n nay, nhi u kh năng m i ã ư c thêm vào nh m t hi u qu t i ưu. Không ph i m i m nh trong
42 L p trình lôgic trong Prolog chương trình u ư c duy t n, mà ch duy t nh ng m nh có liên quan n ích hi n hành. Ví d II.4 : Cho chương trình : thick(bear). % clause 1 thick(elephant). % clause 2 small(cat). % clause 3 brown(bear). % clause 4 grey(elephant). % clause 5 black(cat). % clause 6 dark(Z) :- black(Z). % clause 7: all this who is black is dark dark(Z) :- brown(Z). % clause 8: all this who is brown is dark Câu h i : ?- dark(X), thick(X). % who is thick and dark ? X = bear Yes (1) Danh sách ban u c a các ích là : dark(X), thick(X). (2) Tìm ki m (duy t) t u n cu i chương trình m t m nh có ph n u tương ng v i ích u tiên dark(X). Prolog tìm ư c m nh 7 : dark(Z) :- black(Z). Thay th ích u tiên b i ph n thân c a m nh 7 sau khi ã ư c ràng bu c (th bi n Z b i X) nh n ư c m t danh sách các ích m i : black(X), thick(X). (3) Tìm ki m trong chương trình m t m nh sao cho ích con black(X) ư c so kh p : tìm ư c m nh 6 là s ki n black(cat). Lúc này, ràng bu c thành công, danh sách các ích thu g n thành : thick(cat) (4) Tìm ki m ích con thick(cat). Do không tìm th y m nh nào tho mãn, Prolog quay lui l i giai o n (3). Ràng bu c X=cat b lo i b . Danh sách các ích tr thành : black(X), thick(X). Ti p t c tìm ki m trong chương trình b t u t m nh 6. Do không tìm th y m nh nào tho mãn, Prolog quay lui l i giai o n (2) ti p t c tìm ki m b t u t m nh 7. K t qu tìm ư c m nh 8 : dark(Z) :- brown(Z).
43 Ng nghĩa c a chương trình Prolog Sau khi thay th b i brown(X)trong danh sách các ích, ta nh n ư c : brown(X), thick(X) (5) Tìm ki m cho ràng bu c brown(X), ư c k t qu là brown(bear). M nh này là m t s ki n, danh sách các ích thu g n l i thành : thick(bear) (6) Vi c tìm ki m trong chương trình d n n k t qu thick(bear). Do ây là m t s ki n, danh sách các ích tr nên r ng. i u này ch ng t chương trình ã th c hi n thành công, s ràng bu c cho bi n là : X = bear Quá trình th c hi n ư c gi i thích trong hình dư i ây. dark(X), thick(X) dark(Z) :- black(Z). dark(Z) :- brown(Z). Quay lui (Z|X) (Z|X) black(X), thick(X) brown(X), thick(X) brown(bear). black(cat). Quay lui (X|bear) (X|cat) thick(cat) thick(bear) Th t b i Thành công, X=bear Hình II.6. Quá trình th c hi n xoá ích dark(X), thick(X). II.5. T h p các y u t khai báo và th t c Ngư i ta thư ng quan tâm n tính ưu vi t c a Prolog là kh năng t qu n lý các chi ti t th t c. i u này cho phép NLT (NLT) d ki n trư c ư c nghĩa khai báo c a m t chương trình m t cách c l p v i nghĩa th t c c a nó. V nguyên t c, do k t qu th c hi n c a m t chương trình ph thu c vào ph n khai báo, nên ph i khai báo y các s ki n, lu t và quan h khi l p trình. i u này mang tính th c ti n, vì luôn luôn các y u t khai báo c a m t chương trình d hi u hơn so v i các chi ti t th t c. t n d ng ư c kh năng t qu n lý các chi ti t th t c c a Prolog, NLT ph i t p trung c bi t vào y u t khai báo, tránh nh m l n trong ch ng m c có th b i các chi ti t th c hi n chương trình. C n cho Prolog t gi i quy t các chi ti t mang tính th t c này.
44 L p trình lôgic trong Prolog Nh ti p c n khai báo, l p trình trên Prolog luôn luôn thu n ti n hơn so v i các ngôn ng th t c khác như Pascal. Tuy nhiên, ti p c n khai báo không ph i luôn luôn y . Như s th y sau này, i v i các chương trình l n, không th lo i b hoàn toàn tính ti p c n th t c, do tính hi u qu th c ti n c a nó khi th c hi n chương trình. Vì v y, tuỳ theo chương trình Prolog mà s d ng hoàn toàn y u t khai báo, lo i b y u t th t c khi ràng bu c th c ti n cho phép. Như s th y trong chương sau r ng vi c s p t th t các m nh và các ích cũng như th t các h ng trong m i m nh có vai trò quan tr ng trong vi c tìm ra k t qu . M t khác, m t s chương trình tuy úng n v m t khai báo nhưng l i không ch y ư c trong th c t . Ranh gi i gi a y u t th t c và y u t khai báo r t khó suy xét. M nh sau ây là m t minh ch ng v vi c khai báo úng, nhưng l i hoàn toàn vô ích v m t ch y chương trình : ancestor(X, Z) :- ancestor(X, Z). Do nh ng ti n b c a k thu t l p trình, ngư i ta quan tâm n nghĩa khai báo b qua nh ng chi ti t th t c, t n d ng nh ng chi ti t khai báo làm l i gi i ơn gi n hơn và d hi u hơn. Không ph i là NLT, mà chính h th ng ph i qu n lý nh ng chi ti t th t c. Prolog là ngôn ng nh m vào m c ích này. Như ta ã th y, Prolog ch giúp qu n lý úng n m t ph n nh ng chi ti t th t c, mà không th qu n lý ư c t t c . M t y u t th c t n a là ngư i ta d dàng ch p nh n m t chương trình ch y ư c ( úng nghĩa th t c) hơn là m t chương trình ch úng n v m t khai báo mà chưa ch y ư c. Vì v y, gi i quy t m t bài toán nào ó m t cách có l i, ngư i ta t p trung gi i quy t nh ng y u t khai báo, ti n hành ch y th chương trình trên máy, r i s p t l i các m nh và các ích n u nó v n chưa ch y úng v m t th t c. III. Ví d : con kh và qu chu i III.1. Phát bi u bài toán Trong trí tu nhân t o, ngư i ta thư ng l y tài con kh và qu chu i (monkey and banana problem) minh ho vi c h p gi i bài toán. Sau ây, ta s trình bày làm cách nào v n d ng so kh p và quay lui cho nh ng ng d ng như v y. Ta s tri n khai m t cách phi th t c, sau ó nghiên c u tính th t c m t cách chi ti t.
45 Ng nghĩa c a chương trình Prolog Hình III.1. Minh ho bài toán con kh và qu chu i. Ta s d ng m t bi n th (variant) c a bài toán như sau : m t con kh ang trư c c a m t căn phòng. Trong phòng, chính gi a tr n có treo m t qu chu i. Con kh ang ói nên tìm cách l y qu chu i, nhưng qu chu i l i treo quá cao i v i nó. c nh c a s , có t m t cái h p con kh có th trèo lên. Con kh có th th c hi n các ng tác như sau : bư c i trong phòng, nh y lên h p, di chuy n cái h p (n u con kh ng c nh cái h p), và v i l y qu chu i n u nó ang ng trên h p t úng phía dư i qu chu i. Câu h i t ra là con kh có ăn ư c qu chu i hay không ? Trong l p trình, v n quan tr ng là làm sao bi u di n ư c bài toán phù h p v i ngôn ng ang s d ng. Trư ng h p c a chúng ta có th nghĩ n tr ng thái c a con kh có th bi n i theo th i gian. Tr ng thái hi n hành ư c xác nh b i v trí c a các i tư ng. Ch ng h n, tr ng thái ban u c a con kh ư c xác nh b i : (1) Con kh ang trư c c a (to the door). (2) Con kh ang trên sàn nhà (on the floor). (3) Cái h p ang c nh c a s (to the window). (4) Con kh chưa l y ư c qu chu i (not have). Ta có th nhóm b n thông tin trên thành m t i tư ng có c u trúc duy nh t. G i state là hàm t mà ta l a ch n nhóm các thành ph n c a i tư ng. Hình 2.9. trình bày cách bi u di n tr ng thái u là m t tư ng có c u trúc. state tothedoor onthefloor tothewindow nothave Hình III.2. Tr ng thái u c a con kh là m t i tư ng có c u trúc g m b n thành ph n : v trí n m ngang, v trí th ng ng c a con kh , v trí c a cái h p và m t ch d n cho bi t con kh ã l y ư c qu chu i chưa. III.2. Gi i bài toán v i Prolog Bài toán con kh và qu chu i ư c xem như m t trò chơi ch có m t ngư i chơi. Ta hình th c hoá bài toán như sau : u tiên, ích c a trò chơi là tình hu ng con kh l y ư c qu chu i, nghĩa là m t tr ng thái state b n thành ph n, thành ph n th tư là possessing (chi m h u) : state(_, _, _, possessing)
46 L p trình lôgic trong Prolog Ti p theo, ta tìm các ng tác c a con kh chuy n t m t tr ng thái này sang m t tr ng thái khác. Có b n ki u ng tác (movement) như sau : N m l y qu chu i (grab). (1) Trèo lên h p (climbing). (2) y cái h p (pushing). (3) Di chuy n (walking). (4) Tuỳ theo tr ng thái hi n hành, không ph i t t c m i ng tác u có th s d ng. Ch ng h n, ng tác «n m l y qu chu i ch » có th x y ra khi con kh ã ng trên cái h p, úng v trí phía dư i qu chu i ( chính gi a phòng), và nó chưa n m l y qu chu i. Quy t c Prolog displacement dư i ây có ba i s mô t di chuy n c a con kh như sau : displacement(State1, Movement, State2). Vai trò c a các i s dùng th hi n di chuy n là : State1 State 2 Hình III.3. Di chuy n tr ng thái. Quy ư c state1 là tr ng thái trư c khi di chuy n, M là di chuy n ã th c hi n, và state2 là tr ng thái sau khi di chuy n. ng tác «n m l y qu chu i» v i i u ki n u c n thi t ư c nh nghĩa b i m nh có n i dung : «sau khi di chuy n, con kh ã l y ư c qu chu i, và nó ang ng trên cái h p, gi a ư c vi t trong Prolog như sau : căn phòng». M nh displacement( state(tothecenter, onthebox, tothecenter, nothave), % trư c khi di chuy n % di chuy n grab, state(tothecenter, onthebox, tothecenter, % sau khi di chuy n possessing). M t cách tương t , ta có th di n t di chuy n c a con kh trên sàn nhà t m t v trí n m ngang P1 b t kỳ nào ó n m t v trí m i P2. Vi c di chuy n c a con kh là c l p v i v trí c a cái h p, và c l p v i s ki n con kh ã l y ư c qu chu i hay là chưa : displacement( state(P1, onthefloor, G, H), % di chuy n t P1 n P2 walking(P1, P2), state(P2, onthefloor, G, H). M nh trên ây có r t nhi u nghĩa :
47 Ng nghĩa c a chương trình Prolog Di chuy n ã th c hi n là « i t P1 n P2». • Con kh trên sàn nhà trư c và sau khi di chuy n. • V trí h p là G không thay i sau khi di chuy n. • Qu chu i v n v trí cũ trư c và sau khi di chuy n • (chưa b con kh l y i). M nh này c trưng cho m t t p h p y các ng tác vì có th áp d ng cho b t kỳ m t tình hu ng nào tương ng v i tr ng thái ã ch ra trư c khi di chuy n. Ngư i ta g i các m nh ki u này là m t sơ di chuy n. Hai ki u hành ng khác là « y» và «trèo» cũng ư c c trưng m t cách tương t . displacement M S1 S2 S3 Sn … couldtake couldtake possessing Hình III.4. D ng quy c a v t couldtake. Câu h i t ra cho bài toán s là «Xu t phát t v trí u S, con kh có th l y ư c qu chu i không ?» v i v t sau ây : couldtake(S) v i tham i S là m t tr ng thái ch v trí c a con kh . Chương trình xây d ng cho v t này d a trên hai quan sát sau ây : V i m i tr ng thái S mà con kh ã l y ư c qu chu i, v t (1) couldtake có giá tr true, không c n m t di chuy n nào khác n a. i u này tương ng v i s ki n : couldtake(state(_, _, _, possessing)). Trong các trư ng h p khác, c n th c hi n m t ho c nhi u di (2) chuy n. Xu t phát t m t tr ng thái S1, con kh có th l y ư c qu chu i n u t n t i m t s l n di chuy n M nào ó t S1 n m t tr ng thái S2 sao cho trong tr ng thái S2, con kh có th l y ư c qu chu i. Ta có m nh sau : couldtake(S1) :- displacement(S1, M, S2), couldtake(S2). V t couldtake có d ng quy, tương t v i quan h ancestor ã xét u chương. Chương trình Prolog y như sau :
48 L p trình lôgic trong Prolog displacement( state(tothecenter, onthebox, tothecenter, nothave), % v i l y qu chu i grab, state(tothecenter, onthebox, tothecenter, possessing)). displacement( state(P, onthefloor, P, H), % trèo lên h p climbing, state(P, onthebox, P, H)). displacement( state(P1, onthefloor, P1, H), y cái h p t P1 n P2 pushing(P1, P2), % state(P2, onthefloor, P2, H)). displacement( state(P1, onthefloor, G, H), % di chuy n t P1 n P2 walking(P1, P2), state(P2, onthefloor, G, H)). pushing(tothewindow, tothecenter). walking(tothedoor, tothewindow). % couldtake(state) : con kh có th l y ư c qu chu i trong state % trư ng h p 1 : couldtake(state(_, _, _, possessing)). con kh ã có qu chu i % trư ng h p 2 : c n ph i hành ng couldtake(State1) :- % hành ng displacement(State1, Move, State2), % l y qu chu i couldtake(State2). Chương trình trên ây ã ư c phát tri n m t cách phi th t c. xét tính th t c c a chương trình, ta t ra câu h i sau ây : ?- couldtake(state(tothedoor, onthefloor, tothewindow, nothave)). Yes có câu tr l i, Prolog ph i tho mãn m t danh sách các ích theo ng nghĩa th t c. ó là quá trình tìm ki m cho con kh m t di chuy n h p lý trong m i di chuy n có th . ôi khi, quá trình này s d n n m t ngõ c t, thoát ra, c n ph i quay lui. Câu h i trên c n quay lui m t l n. Các di chuy n h p lý ti p theo ư c tìm th y ngay do các m nh liên quan n quan h displacement có m t trong chương trình, phù h p v i tình hu ng. Tuy nhiên, v n có th x y ra kh năng các di chuy n không h p lý. Con kh i t i i lui mãi mà không ch m ư c cái h p, ho c không có ích th c s . Trong ví d trên, ta ã ưu tiên quá trình so kh p các m nh d n n thành công.
49 Ng nghĩa c a chương trình Prolog Hình III.5. L i gi i c a bài toán con kh và qu chu i. state(tothedoor, onthefloor, tothewindow, nothave) Quá trình tìm ki m b t u t nút trên cùng và ti p t c xu ng dư i. grab phép th th c hi pushing t t trái qua ph i. Các climbing walking(tothedoor, P2) n l n lư failure x y rfailure l n quay lui mà thôi. Ch am t failure state(P2, onthefloor, tothewindow, nothave) grab climbing pushing(P2, P2’) failure backtrack state(tothedoor, onthebox, tothewindow, nothave) state(P2’, onthefloor, P2’, nothave) grab climbing walking pushing grab climbing failure failure failure failure failure state(P2’, onthebox, P2’, nothave) Grab P2’ = tothecenter state(tothecenter, onthebox, tothecenter, possessing)