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

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

Thêm vào BST

Báo xấu

126
lượt xem 39
download

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

Phần còn lại của các mệnh đề trong một chương trình Prolog được gọi là luật. Nó thường thể hiện những phát biểu logic trong bài toán, ví dụ như nếu công tác đèn bật thì đèn sá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 10

167 K thu t l p trình Prolog displaylist( [X | L ] ) :- write( X ), tab( 1), displaylist( L), nl. Yes III.3. ng d ng ch làm vi c v i các t p III.3.1. nh d ng các h ng Gi s m t b n ghi cơ s d li u, là m t s ki n có d ng c u trúc hàm t c a Prolog, có n i dung như sau : family( individual(tom, smith, date(7, may, 1960), work(microsoft, 30000)), individual( ann, smith, date(9, avril, 1962), inactive), [ individual( roza, smith, date(16, june, 1991), inactive), individual( eric, smith, date(23, march, 1993), inactive) ] ). Ta c n in ra n i dung b n ghi s d ng v t write(F) theo quy cách như sau : parents tom smith, birth day may 7,1960, work microsoft, salary 30000 ann smith, birth day avril 9, 1962, out of work children roza smith, birth day june 16, 1991, out of work eric smith, birth day march 23, 1993, out of work Ta xây d ng th t c writefamily( F) như sau : writefamily(family(Husband, Wife, Children)) :- nl, write(parents),nl, nl, writeindividual(Husband) ,nl, writeindividual(Wife), nl, nl, write(children), nl, nl, writeindividual(Children). writeindividual(individual(Firstname, Name, date(D, M, Y), Work)) :- tab(4), write(Firstname), tab(1), write(Name), write(', birth day '), write(M), tab(1), write(D), tab(1), write(', '), write(Y), write(',
L p trình lägich trong Prolog 168 '), writework(Work). writeindividual([ ]). writeindividual([ P | L] ):- writeindividual( P), nl, writeindividual( L). writework(inactive):- write('out of work'). writework(work(Soc, Sal)):- write(' work '), write(Soc), write(', salaire '), write(Sal). Th c hi n íchX = ..., writefamily(X), ta nh n ư c k t qu như sau ?- X = family(individual( tom, smith, date(7, may, 1960), work(microsoft, 30000) ),individual( ann, smith, date(9, avril, 1962), inactive),[individual( roza, smith, date(16, june, 1991), inactive),individual( eric, smith, date(23, march, 1993), inactive) ] ), writefamily(X). parents tom smith, birth day may 7 , 1960, work microsoft, salaire 30000 ann smith, birth day avril 9 , 1962, out of work children roza smith, birth day june 16 , 1991, out of work eric smith, birth day march 23 , 1993, out of work X = family(individual(tom, smith, date(7, may, 1960), work(microsoft, 30000)), individual(ann, smith, date(9, avril, 1962), inactive), [individual(roza, smith, date(16, june, 1991), inactive), individual(eric, smith, date(23, march, 1993), inactive)]) Yes III.3.2. S d ng t p x lý các h ng c d li u trên t p, ngư i ta s d ng dãy ích sau : ..., see( F), fileprocess, see( user), ... Th t c fileprocess c và x lý l n lư t t ng h ng c a F cho n khi c h t t p. Mô hình th t c như sau : filetreat :- read( Term), treat( Term). % K t thúc t p treat( end_of_file) :- !. treat( Term) :-
169 K thu t l p trình Prolog treatment( Term), % X lý h ng hi n hành % X lý ph n còn l i c a t p filetreat. Trong th t c trên, treatment( Terme) th hi n m i thao tác có th tác ng lên h ng. Ch ng h n th t c dư i ây li t kê t ng h ng c a t p k t dòng th N tr i cho n h t t p, kèm theo th t có m t c a h ng ó trong t p : viewfile( N) :- read( Term), viewterm( Term, N). viewterm( end_of_file, _ ) :- !. viewterm( Term, N) :- write( N), tab( 2), write( Term), nl, N1 is N + 1, viewfile( N1). ?- see('exp.txt'), viewfile(1), see( user), seen. 1 parent(pam, bob) 2 parent(tom, bob) 3 parent(tom, liz) 4 parent(bob, ann) 5 parent(bob, pat) … Yes Sau ây là m t mô hình khác x lý t p. Gi s file1 là t p d li u ngu n ch a các h ng có d ng : object( NoObject, Description, Price, FurnisherName). M i h ng mô t m t ph n t c a danh sách các i tư ng. Gi s r ng t p c n xây d ng file2 ch a các i tư ng do cùng m t nhà cung c p c p hàng. Trong t p này, tên nhà cung c p ư c vi t m t l n u t p, mà không xu t hi n trong các i tư ng, có d ng object( No, Desc, Price). Th t c t o t p như sau : createfile(Furnisher) :- write(Furnisher), write( ‘.‘), nl, creatremaining(Furnisher). creatremaining( Fournisseur) :- read( Objet), treat( Objet, Furnisher). treat( end_of_file) :- !. treat(object( No, Desc, Price, Furn), Furn) :- write( object( No, Desc, Price) ), write( ‘.‘), nl, creatremaining(Furn).
L p trình lägich trong Prolog 170 treat( _ , Furnisher) :- creatremaining(Furnisher). Gi s file1 là t p see(' file1.txt'),tell(' file2.txt'), createfile(suzuki), seen, see(user), told, tell(user). Ví d III.10 : Sao chép n i dung m t t p lên m t t p khác : copie :- repeat, read(X), mywrite(X), X == end_of_file, !. mywrite( end_of_file). mywrite( X) :- write( X), write( '.'), nl. ích sau cho phép côpy t t p ngu n f1.txt vào t p ích f2.txt : ?- tell('f2.txt'), see('f1.txt'), copie, seen, told. Yes Trong th t c copie có s d ng v t repeat. V t repeat luôn luôn thành công, t o ra m t vòng l p vô h n. V t repeat ư c nh nghĩa như sau : repeat. repeat :- repeat. III.3.3. Thao tác trên các ký t M t s v t x lý ký t c a Prolog như sau : Tên v t Ý nghĩa ưa Char ra dòng ra hi n hành, Char ho c là m t giá put(Char) tr nguyên trong kho ng 0..255, ho c m t ký t ưa Char ra t p File put(File, Char) c t t p File và h p nh t Char v i ký t ti p theo. get_char(Char) get_char(File, H p nh t Char v i ký t ti p theo trong t p File. Char) c ký t ti p theo get0(Char) get0(File, c ký t ti p theo trong t p File. Char) c ký t khác kho ng tr ng t dòng vào và h p nh t get(-Char) v i Char. c ký t khác kho ng tr ng ti p theo trong t p File. get(File, Char) c vào và b qua các ký t c ư c cho n khi g p skip(Char) úng ký t kh p ư c v i Char.
171 K thu t l p trình Prolog c vào t t p File và b qua các ký t c ư c cho skip(File, n khi g p úng ký t kh p ư c v i Char. Char) Ví d III.11 : % ưa ra liên ti p các ký t A, B và C có mã ASCII l n lư t là 65, 66, 67 ?- put( 65), put( 66), put( 67). ABC yes c và ghi các ký t % ?- get0(X). % Gõ vào m t ký t r i Enter (↵), không gõ d u ch m |: a X = 97 Yes. ?- get0(X). ^D X = -1. Yes. Ví d III.12 : Sau ây ta xây d ng th t c del_space c vào m t câu g m nhi u t cách nhau b i các kho ng tr ng và tr v úng câu ó sau khi ã lo i b các kho ng tr ng th a, ch gi l i m t kho ng tr ng gi a các t mà thôi. Th t c ho t ng tương t các th t c x lý t p, b ng cách c l n lư t t ng ký t r i ưa ra màn hình. Th t c s d ng k thu t nhát c t x lý tình hu ng ký t c vào ho c là m t kho ng tr ng, ho c là m t ch cái, ho c là m t d u ch m k t thúc. Sau ây là th t c del_space : del_space :- get0( C), put( C), follow( C). % 46 là mã ASCII c a d u ch m follow( 46) :- !. follow( 32) :- !, % 32 là mã ASCII c a d u kho ng tr ng get( C), %B qua các d u kho ng tr ng ti p theo put( C), follow( C). follow( Letter) :- del_space. Ch y th như sau : ?- del_space. |: The robot try to cast the balls to the basket.
L p trình lägich trong Prolog 172 The robot try to cast the balls to the basket. Yes III.3.4. Thao tác trên các nguyên t Prolog có v t name/2 cho phép t tương ng các nguyên t v i các mã ASCII : name( A, L) V t tho mãn khi L là danh sách các c a các ký t c a A. Ví d : ?- name(mic29, [109, 105, 99, 50, 57 ]). Yes ?- name( aikieutuido, L). L = [ 97, 105, 107, 105, 101, 117, 116, 117, 105 |... ] Yes ?- name(X, [ 97, 105, 107, 105, 101, 117, 116, 117, 105, 100, 111 ]). X = aikieutuido Yes Hai ch c năng chính c a v t name như sau : 1. Chuy n m t nguyên t thành m t danh sách các ký t (mã ASCII). 2. T o m t nguyên t t m t danh sách các ký t . Ví d III.13 : Xây d ng th t c qu n lý các cu c g i d ch v xe taxi ch hành khách nh các nguyên t sau : Tên các cu c g i call1, call2, ... Tên các lái xe chauffeur1, chauffeur2, ... Tên các xe taxi taxi1, taxi2, ... V t taxi( X ) ki m tra m t nguyên t có bi u di n úng m t taxi theo cách bi u di n như trên không : taxi( T ) :- name( T, Tlist), name( taxi, L), append( L, _ , Tlist). M t cách tương t , ta có th xây d ng các v t chauffer và taxi. Ví d III.14 : Sau ây ta xây d ng th t c cho phép t o ra m t nguyên t b ng cách t h p các ký t . Th t c readsentence( Wordlist) s c m t câu thu c ngôn ng t nhiên r i gán cho Wordlist danh sách các giá tr mã bi u di n trong c a
173 K thu t l p trình Prolog các ký t trong câu. Ti p theo, m i câu ư c xem là m t danh sách các t , m i t ư c chuy n thành m t nguyên t . readsentence( WordList) :- get0( Char), readchain( Char, WordList). readchain( 46,[ ] ) :- !. % d u ch m k t thúc câu readchain( 32, WordList) :- % B qua các d u kho ng tr ng readsentence(WordList). readchain( L, [ W | WordList ] ) :- c các ký t c a readletter( L, Letters, Nextchar ), % t ti p theo name( W, Letters), readchain( Nextchar, WordList). % k t thúc t là m t d u ch m readletter( 46, [ ], 46) :- !. % k t thúc t là m t d u kho ng readletter( 32, [ ], 32) :- !. tr ng readletter( C, [ C | Letters] , Nextchar) :- get0( Char), readletter( Char, Letters, Nextchar). Ch y chương trình, ta có các k t qu như sau : ?- readsentence( WordList). |: The robot ASIMO try to cast the balls to the basket. WordList = ['The', robot, 'ASIMO', try, to, cast, the, balls, to|...] Yes ?- readsentence( WordList). |: " Ai i trăm su i ngàn r ng " % d u Enter ↵ sau d u nháy kép |: . % d u ch m k t thúc câu WordList = [ '" Ai', i, trăm, su i, ngàn, 'r ng "\n' ] Yes Trong th t c, ta ã gi thi t r ng k t thúc câu vào là m t d u ch m và n u có d u ch m câu trong câu, thì tuỳ theo cách xu t hi n mà nó ư c xem như là m t t ho c dính vào v i t . Th t c c ký t u tiên là Char, r i chuy n cho th t c readchain. Th t c readchain x lý 3 trư ng h p như sau : (1) N u Char là m t d u ch m, thì quá trình c câu vào k t thúc. (2) N u Char là m t kho ng tr ng, áp d ng th t c readsentence cho ph n còn l i c a câu.
L p trình lägich trong Prolog 174 (3) N u Char là m t ký t : trư c tiên c t W ư c b t u b i ký t Char, sau ó s d ng readsentence c ph n còn l i c a câu và t o ra danh sách WordList. K t qu ư c tích lu trong [ W | WordList ]. Th t c readletter( L, Letters, Nextchar ) c các ký t c a m t t , trong ó : (1) L là ch cái hi n hành ( ã ư c c) c a t ang c. (2) Letters là danh sách các ch cái, b t u b i L cho n h t t . (3) Nextchar là ký t theo sau t ang c, có th không ph i là m t ch cái. Nh cách bi u di n các t c a câu trong m t danh sách, ngư i ta có th s d ng Prolog x lý ngôn ng t nhiên, như tìm hi u nghĩa c a câu theo m t quy ư c nào ó, v.v.. thu c lĩnh v c trí tu nhân t o. III.3.5. M t s v t x lý cơ s d li u Sau ây là m t s v t chu n cho phép x lý trên các lu t và s ki n c a m t cơ s d li u Prolog. assert(P) Thêm P vào cơ s d li u. Ví d cho cơ s d li u lúc ban u: personal(tom). personal(ann). Sau khi th c hi n ích : ?- assert(personal(bob)). cơ s d li u lúc này tr thành : personal(tom). personal(ann). personal(bob). Do NSD không bi t assert ã thêm P vào u hay cu i c a cơ s d li u, Prolog cho phép s d ng hai d ng khác là : Thêm P vào u cơ s d li u. asserta(P) Thêm P vào cu i cơ s d li u. assertz(P) S d ng v t : assert((P :- B, C, D)). có th làm thay i n i dung m t m nh trong chương trình. Tuy nhiên, ngư i ta khuyên không nên s d ng l nh này. retract(P)
175 K thu t l p trình Prolog Lo i b P kh i cơ s d li u. Ví d cho cơ s d li u lúc ban u: personal(tom). personal(ann). personal(bob). Sau khi th c hi n ích : ?- retract(personal(ann)). cơ s d li u lúc này ch còn : personal(tom). personal(bob). Có th s d ng bi n trong retract như sau : ?- retract(personal(X)). X = tom ; X = bob ; No Lúc này cơ s d li u ã r ng. abolish(Term, Arity) Lo i b t t c các h ng Term có c p Arity kh i cơ s d li u. Ví d : ?- abolish(personal, 2). Lo i b t t c các h ng Term có c p Arity=2. Ví d III.15 Xây d ng b siêu di n d ch Prolog trong Prolog, vi c xoá m t ích ư c vi t l i như sau : prove(Goal) :- call(Goal). ho c : prove(Goal) :- Goal. ho c vi t các m nh : prove(true). prove((Goal1, Goal2)) :- prove(Goal1), prove(Goal2). prove(Goal) :- clause(Goal, Body), prove(Body).
L p trình lägich trong Prolog 176 Tóm t t chương 5 : K thu t nhát c t và ph nh • Nhát c t ngăn c n s quay lui, không nh ng làm t ng hi u qu ch y chương trình mà còn làm t i ưu tính bi u hi n c a ngôn ng . t ng hi u qu ch y chương trình, ngư i l p trình s d ng nhát c t ch • ra cho Prolog bi t nh ng con ư ng d n n th t b i. • Nhát c t cho phép t o ra các k t lu n lo i tr nhau d ng : If Condition Thì Conclusion_1 n u Conclusion_2 • Nhát c t cho phép nh nghĩa phép ph nh : not Goal tho mãn n u Goal th t b i. • Prolog có hai ích c bi t : true luôn luôn úng và fail luôn luôn sai. • C n th n tr ng khi s d ng k thu t nhát c t, nhát c t có th làm sai l ch 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. • Phép ph nh not trong Prolog không hoàn toàn mang ý nghĩa lôgich, c n chú ý khi s d ng not. S d ng các c u trúc Các ví d ã trình bày trong chương này minh ho nh ng c trưng r t tiêu bi u c a k thu t l p trình Prolog : • Trong Prolog, t p h p các s ki n bi u di n m t cơ s d li u. • K thu t t câu h i và so kh p c a Prolog là nh ng phương ti n m m d o cho phép truy c p tù cơ s d li u nh ng thông tin có c u trúc. • C n s d ng phương pháp tr u tư ng hoá d li u như là m t k thu t l p trình cho phép s d ng các c u trúc d li u ph c t p m t cách ơn gi n, làm chương trình tr nên d hi u. Trong Prolog, phương pháp tr u tư ng hoá d li u r t d tri n khai. • Nh ng c u trúc toán h c tr u tư ng như ôtômat cũng r t d cài t trong Prolog. • Ngư i ta có th ti p c n n nhi u l i gi i khác nhau cho m t bài toán nh s d ng nhi u cách bi u di n d li u khác nhau, như trư ng h p bài toán tám quân h u. Cách bi u di n d li u s d ng nhi u thông tin ti t ki m ư c tính toán, m c dù làm cho chương trình tr nên rư m rà, khó cô ng. • K thu t t ng quát hoá m t bài toán, tuy tr u tư ng, nhưng l i làm tăng kh năng hư ng n l i gi i, làm ơn gi n hoá phát bi u bài toán.
177 K thu t l p trình Prolog Làm vi c v i t p Cùng v i ch tương tác câu h i-tr l i, quá trình vào ra và ch làm vi c v i t p ã làm phong phú môi trư ng làm vi c c a Prolog. • Các t p trong Prolog u ho t ng theo ki u tu n t . Prolog phân bi t dòng vào hi n hành và dòng ra hi n hành. • Thi t b cu i (terminal) c a NSD g m màn hình và bàn phím ư c xem như m t t p gi có tên là user. • Prolog có nhi u v t có s n x lý các dòng vào-ra. • Khi làm vi c v i t p, ch c ghi là x lý t ng ký t ho c t ng h ng. Bài t p chương 5 1. Cho chương trình : p( 1 ). p( 2 ) :- !. p( 3 ). Cho bi t các câu tr l i c a Prolog tù các câu h i sau : (a) ?- p( X ). (b) ?- p( X ), p( Y ). (c) ?- p( X ), !, p( Y ). 2. Quan h sau ây cho bi t m t s có th là dương, b ng không, ho c âm : sign( Number, positive) :- Number > 0. sign( 0, null). sign( Number, negative) :- Number < 0. Hãy s d ng k thu t nhát c t vi t l i chương trình trên hi u qu hơn. 3. Th t c separate(Number, Positive, Negative) x p các ph n t trong danh sách Number l n lư t thành hai danh sách, danh sách Positive ch ch a các s dương, ho c b ng không, danh sách Negative ch ch a các s âm. Ví d : separate( [ 3, -1, 0, 5, -2 ], [ 3, 0, 5 ], [ -1, -2 ] ) Hãy nh nghĩa th t c trên theo hai cách, m t cách không s d ng k thu t nhát c t, m t cách có s d ng k thu t nhát c t.
L p trình lägich trong Prolog 178 4. Cho hai danh sách, Accept và Reject, hãy vi t danh sách các ích s d n g k thu t quay lui và các quan h member và not tìm các ph n t có m t trong Accept nhưng không có m t trong Reject. 5. nh nghĩa th t c difference( Set1, Set2, SetDiff) tìm hi u hai t p h p Set1 và Set2 v i quy ư c các t p h p ư c bi u di n b i các danh sách.. Ch ng h n : difference( [ a, b, c, d ], [ b, d, e, f ], [ a, c ] ) 6. Hãy nh nghĩa v t unifiable( List1, Term, List2) ki m tra so kh p, trong ó List2 là danh sách t t c các ph n t c a List1 có th so kh p v i Term nhưng không th c hi n phép th trên các bi n ã ư c so kh p. Ví d : ?- unifiable( [ X, bibo, t( Y ) ], t(a), List ). List = [X, t( Y )] Chú ý r ng X và Y v n là các bi n t do không th c hi n phép th t(a) cho X, hay phép th a cho Y. Mu n v y, th c hi n hư ng d n sau : S d ng phép ph nh not( Term1 = Term2). N u quan h Term1 = Term2 ư c tho mãn, khi ó, not( Term1 = Term2) s th t b i, và phép th bi n không x y ra. 7. Bài toán mã i tu n. Gi s các ô c a bàn c vua 8×8 ư c bi u di n b i các c p to có d ng X/Y, v i X và Y n m trong kho ng 1 và 8. (a) nh nghĩa quan h jump( case1, case2 ), b ng cách s d ng lu t i c a quân mã, và gi s r ng case1 luôn luôn b ràng bu c. Ví d : ?- jump( 1/1, C ). C = 3/2; C = 2/3; No (b) nh nghĩa quan h mvt_ knight( path ), v i path là m t danh sách g m các ô bi u di n l trình các bư c nh y h p lý c a quân mã trên bàn c r ng. (c) S d ng quan h mvt_ knight, vi t m t câu h i tìm t t c các l trình b n bư c nh y h p lý c a quân mã, xu t phát t ô có to 2/1, n biên bên ph i c a bàn c (Y = 8) và n ô 5/4 sau hai bư c nh y. 8. Cho f m t t p ch a các h ng, hãy nh nghĩa th t c findterm(Term) ưa ra màn hình h ng u tiên c a f kh p ư c v i Term ? 9. Cho f m t t p ch a các h ng, hãy nh nghĩa th t c findallterm(Term) ưa ra màn hình t t c các h ng c a f kh p ư c v i Term ? Ki m tra tính ch t bi n Term không th ư c gán giá tr khi th c hi n tìm ki m.
179 K thu t l p trình Prolog 10. Hãy m r ng th t c del_space ã ư c trình bày trong ph n lý thuy t có th x lý lo i b các d u cách th a n m trư c d u ph y (comma) và ch gi l i m t d u cách n m ngay sau d u ph y. 11. Tương t bài 3 cho các d u ch m câu khác như d u ch m (period), d u ch m ph y (semicolon), d u ch m h i (question mark), v.v... 12. nh nghĩa quan h firstchar( Atom, Char) cho phép ki m tra Char có ph i là ký t u tiên c a Atom không (Atom b t u b i Char) ? 13. nh nghĩa th t c cho phép i m t danh t ti ng Anh t s ít (singular) sang s nhi u (plural) ư c th c hi n như sau : ?- plural ( table, X ). X = tables Yes 14. Áp d ng th t c readsentence ã ư c trình bày trong ph n lý thuy t xây d ng th t c : ?- find( Keyword, Sentence ). cho phép tìm trong t p ang c m t câu có ch a t khoá Keyword. Câu Sentence ph i d ng m i ư c c vào chưa x lý, nghĩa là ư c bi u di n b i m t chu i ký t , ho c b i m t nguyên t .
THÔNG TIN V TÁC GI GIÁO TRÌNH “L P TRÌNH LÔGIC” 1 Thông tin v tác gi : + H và tên : Phan Huy Khánh + Quê quán : Ngh An + Cơ quan công tác : Khoa Công ngh Thông tin, Trư ng i h c Bách khoa, i h c à N ng + Email: khanhph@vnn.vn, phk@ud.edu.vn 2 Ph m vi và i tư ng s d ng : + Giáo trình dùng tham kh o cho các ngành Công ngh Thông tin các trư ng có ào t o các chuyên ngành Công ngh Thông tin + Có th dùng + T khóa : S ki n , lu t, lu t quy, m nh , h ng, v t , ích, quy, danh sách, h p nh t, nhát c t. + Yêu c u ki n th c trư c khi h c môn này : Tin h c i cương, Toán r i r c, C u trúc d li u và thu t toán + ã xu t b n : “L p trình logic trong Prolog ”, Nhà Xu t b n i h c Qu c gia Hà N i, 2004