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

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

Thêm vào BST

Báo xấu

169
lượt xem 62
download

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

Nội dung cuốn sách tập trung trình bầy cơ sở lý thuyết và những kỹ thuật lập trình cơ bản trong prolog, rất cần cho sinh viên các ngành tin học và các bạn đọc muốn tìm hiểu về kỹ thuật lập trình ứng dụng trong lĩnh vực trí tuệ nhân tạo.

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 5

69 Các phép toán và s h c ~ v & ~ ~ A B A B Hình I.4. Bi u di n cây c a h ng ~ ( A & B ) ~ A ∨ ~ B Trong ví d trên, ta d dàng nh nghĩa l i các phép toán lôgich như sau : :- op( 800, xfx, ). :- op( 700, xfy, v ). :- op( 600, xfy, & ). :- op( 500, fy, ~ ). T ây, nh lý Morgan ư c vi t l i thành h ng sau (xem hình trên) : ~ ( A & B ) ~ A ∨ ~ B II. Các phép so sánh c a Prolog II.1. Các phép so sánh s h c Prolog có các phép so sánh và hàm s h c như sau : Ký hi u Gi i thích phép toán Thành công n u Expr1 có giá tr s l n hơn Expr2 Expr1 > Expr2 Thành công n u Expr1 có giá tr s nh hơn Expr2 Expr1 < Expr2 Thành công n u Expr1 có giá tr s nh hơn ho c b ng Expr1 =< Expr2 Expr2 Thành công n u Expr1 có giá tr s l n hơn ho c Expr1 >= Expr2 b ng Expr2 Thành công n u Expr1 có giá tr s khác Expr2 Expr1 =\= Expr2 Thành công n u Expr1 có giá tr s b ng Expr2 Expr1 =:= Expr2 Low và High là các s nguyên, Low=< Value=< between(Low, High, High. Value là bi n s ư c nh n giá tr gi a Low Value) và High Thành công n u Int2= Int1+ 1 và Int1>= 0 succ(Int1, Int2) plus(Int1, Int2, Thành công n u Int3= Int1+Int2 Int3)
70 L p trình lôgic trong Prolog Chú ý r ng các phép toán = và =:= là hoàn toàn khác nhau, ch ng h n trong các ích X = Y và X =:= Y : • ích X = Y kéo theo vi c ng nh t các i tư ng X và Y, n u chúng ng nh t v i nhau thì có th ràng bu c m t s bi n nào ó trong X và Y. • ích X =:= Y ch gây ra m t phép tính s h c so sánh mà không x y phép ràng bu c nào trên các bi n. Ví d II.1 : ?- X = Y. X = _G997 Y = _G997 Yes ?- 1 + 2 =:= 2 + 1. Yes. ?- 1 + 2 = 2 + 1. No. ?- 1 + 2 = 1 + 2. Yes. ?- 1 + X = 1 + 2. X=2 A = B + 2. ?- 1 + A=2 B=1 ?- 1 + 2 =:= 2 + 1. Yes. ?- 1 + X =:= 1 + 2. Arguments are not sufficiently instantiated (sai do ERROR: a không ph i là s ) ?- 1 + 2 == 1 + 2. Yes. ?- 1 + 2 == 2 + 1. No. ?- 1 + X == 1 + 2. No. ?- 1 + a == 1 + a. Yes. 1 is sin(pi/2). Yes
71 Các phép toán và s h c ?- 1.0 is sin(pi/2). No ?- 1.0 is float(sin(pi/2)). Yes ?- 1.0 =:= sin(pi/2). Yes II.2. Các phép so sánh h ng Các phép so sánh h ng c a Prolog như sau : Ký hi u Gi i thích phép toán Term1 == Term2 Thành công n u Term1 tương ương v i Term2. M t bi n ch ng nh t v i m t bi n cùng chia s trong h ng (sharing variable) Term1 \== Term2 Tương ương v i \Term1 == Term2. Term1 = Term2 Thành công n u Term1 kh p ư c v i Term2 Term1 \= Term2 Tương ương v i \Term1 = Term2 Term1 =@= Term2 Thành công n u Term1 có cùng c u trúc (structurally equal) v i Term2. Tính có cùng c u trúc y u hơn tính tương ương (equivalence), nhưng l i m nh hơn phép h p nh t Term1 \=@= Term2 Tương ương v i `\Term1 =@= Term2' Term1 @< Term2 Thành công n u Term1 và Term2 theo th t chu n c a các h ng Term1 @=< Term2 Thành công n u ho c hai h ng b ng nhau ho c Term1 ng trư c Term2 theo th t chu n c a các h ng Term1 @> Term2 Thành công n u Term1 ng sau Term2 theo th t chu n c a các h ng Thành công n u ho c hai h ng b ng nhau both ho c Term1 @>= Term2 Term1 ng sau Term2 theo th t chu n c a các h ng compare(?Order, H ng1, H ng2) Ki m tra th t ho c = gi a hai h ng Ví d II.2 : ?- free_variables(a(X, b(Y, X), Z), L). L = [G367, G366, G371] X = G367
72 L p trình lôgic trong Prolog Y = G366 Z = G371 ?- a =@= A. No ?- a =@= B. No ?- x(A, A) =@= x(B, C). No ?- x(A, A) =@= x(B, B). A = _G267 B = _G270 Yes 5 ?- x(A, B) =@= x(C, D). A = _G267 B = _G268 C = _G270 D = _G271 Yes ?- 3 @< 4. Yes ?- 3 @< a. Yes ?- a @< abc6. Yes ?- abc6 @< t(c, d). Yes ?- t(c, d) @< t(c, d, X). X = _G284 Yes II.3. V t xác nh ki u Do Prolog là m t ngôn ng nh ki u y u nên NLT thư ng xuyên ph i xác nh ki u c a các tham i. Sau ây là m t s v t xác nh ki u (type predicates) c a Prolog.. Vt Ki m tra V là m t bi n ? var(V)
73 Các phép toán và s h c X không ph i là m t bi n ? nonvar(X) A là m t nguyên t ? atom(A) I là m t s nguyên ? integer(I) R là m t s th c (d u ch m ng) ? float(R) N là m t s (nguyên ho c th c) ? number(N) A là m t nguyên t ho c m t s ? atomic(A) X là m t h ng có c u trúc ? compound(X) X là m t h ng ã hoàn toàn ràng bu c ? ground(X) Ví d II.3 : ?- var(X). X = _G201 Yes ?- integer(34). Yes ?- ground(f(a, b)). Yes ?- ground(f(a, Y)). No II.4. M t s v t x lý h ng Vt Ki m tra functor(T, F, N) T là m t h ng v i F là h ng t và có N i (arity) Chuy n i h ng T thành danh sách L T =..L Head :- Term là m t lu t trong chương clause(Head, Term) trình ? Th bi n X cho tham i th N c a h ng Term arg(N, Term, X) Chuy n nguyên t A thành danh sách L g m các mã name(A, L) ASCII (danh sách s ư c trình bày trong chương sau). Ví d II.4 : ?- functor(t(a, b, c), F, N). F=t N=3 Yes ?- functor(father(jean, isa), F, N). F = father, N = 2.
74 L p trình lôgic trong Prolog Yes ?- functor(T, father, 2). % _G346 và _G347 là hai bi n c a T = father(_G346, _G347). Prolog ?- t(a, b, c) =..L. L = [t, a, b, c] Yes ?- T =..[t, a, b, c, d, e]. T = t(a, b, c, d, e) Yes ?- arg(1, father(jean, isa), X). X = jean ?- name(toto, L). L = [116, 111, 116, 111]. Yes ?- name(A, [116, 111, 116, 111]). A = toto. Yes Ví d II.5 : Cho cơ s d li u : personal(tom). personal(ann). father(X, Y) :- son(Y, X), male(X). ?- clause(father(X, Y), C). C = (son(Y, X), male(X)). ?- clause(personal(X), C). X = tom, C = true; X = ann, C = true Yes
75 Các phép toán và s h c III. nh nghĩa hàm Prolog không có ki u hàm, hàm ph i ư c nh nghĩa như m t quan h trên các i tư ng. Các tham i c a hàm và giá tr tr v c a hàm ph i là các i tư ng c a quan h ó. i u này có nghĩa là không th xây d ng ư c các hàm t h p t các hàm khác. Ví d III.1 : nh nghĩa hàm s h c c ng hai s b t kỳ % trư ng h p tính Z = X + Y plus(X, Y, Z) :- nonvar(X), nonvar(Y), Z is X + Y. % trư ng h p tính X = Z - Y plus(X, Y, Z) :- nonvar(Y), nonvar(Z), X is Z - Y. % trư ng h p tính Y - Z - X plus(X, Y, Z) :- nonvar(X), nonvar(Z), Y is Z - X. ?- add1(2, 3, X). X=5 Yes add1(7, X, 3). X = -4 Yes add1(X, 2, 6). X=4 Yes III.1. nh nghĩa hàm s d ng quy Trong chương 1, ta ã trình bày cách nh nghĩa các lu t (m nh ) quy. Sau ây, ta ti p t c ng d ng phép quy xây d ng các hàm. Tương t các ngôn ng l p trình m nh l nh, m t th t c quy c a Prolog ph i ch a các m nh tho mãn 3 i u ki n : • M t kh i ng quá trình l p. • M t sơ l p l i chính nó. • M t i u ki n d ng. Ví d th t c quy t o dãy 10 s t nhiên ch n u tiên như sau : u tiên l y giá tr 0 kh i ng quá trình. Sau ó l y 0 là giá tr hi n hành t os ti p theo nh sơ l p : even_succ_nat = even_succ_nat + 2. Quá trình
76 L p trình lôgic trong Prolog c ti p t c như v y cho n khi ã có 10 s 0 2 4 6 8 10 12 14 16 18 thì d ng l i. Trong Prolog, m t m nh quy ( t o sơ l p ) là m nh có ch a trong thân (v ph i) ít nh t m t l n l i g i l i chính m nh ó (v trái) : a(X) :- b(X, Y), a(Y). M nh a g i l i chính nó ngay trong v ph i. D ng sơ l p như v y ư c g i là quy tr c ti p. không x y ra l i g i vô h n, c n có m t m nh làm i u ki n d ng t trư c m nh . M i l n vào l p m i, i u ki n d ng s ư c ki m tra quy t nh xem có th ti p t c g i a hay không ? Ta xây d ng th t c even_succ_nat(Num, Count) t o l n lư t các s t nhiên ch n Num, bi n Count m s bư c l p. i u ki n d ng là Count=10, ta có : even_succ_nat(Num, 10). M nh l p ư c xây d ng như sau : even_succ_nat(Num, Count) :- write(Num), write(' '), Count1 is Count + 1, Num1 is Num + 2, even_succ_nat(Num1, Count1). Như v y, l i g i t o 10 s t nhiên ch n u tiên s là : ?- even_succ_nat(0, 0). 0 2 4 6 8 10 12 14 16 18 Yes M t cách khác xây d ng sơ l p ư c g i là quy không tr c ti p có d ng như sau : a(X) :- b(X). b(X) :- c(Y...), a(Z). Trong sơ l p này, m nh quy a không g i g i tr c ti p n a, mà g i n m t m nh b khác, mà trong b này l i có l i g i n a. không x y ra l i g i lu n qu n vô h n, trong b c n th c hi n các tính toán làm gi m d n quá trình l p trư c khi g i l i m nh a (ví d m nh c). Ví d sơ dư i ây s gây ra vòng lu n qu n vô h n : a(X) :- b(X, Y). b(X, Y) :- a(Z). Bài toán t o 10 s t nhiên ch n u tiên ư c vi t l i theo sơ quy không tr c ti p như sau : a(0).
77 Các phép toán và s h c a(X) :- b(X). b(X) :- X1 is X - 2, write(X), write(' '), a(X1). Chương trình này không g i « quy » như even_succ_nat. K t qu sau l i g i a(20) là dãy s gi m d n 20 18 16 14 12 10 8 6 4 2. Ví d III.2 : Xây d ng s t nhiên (Peano) và phép c ng trên các s t nhiên nh nghĩa s t nhiên */ /* % 0 là m t s t nhiên nat(0). % s(X) cũng là m t s t nhiên nat(s(N)) :- % n u N là m t s t nhiên nat(N). Ch ng h n s 5 ư c vi t : s(s(s(s(s(zero))))) nh nghĩa phép c ng */ /* % lu t 1 : 0 + X = X addi(0, X, X). có th s d ng them lu t 2 : X + 0 = X /* addi(X, 0, X). addi(s(X), Y, s(Z)) :- % lu t 3 : n u X + Y = Z thì (X+1) + Y = (Z+1) addi(X, Y, Z). Ho c nh nghĩa theo nat(X) như sau : addi(0, X, X) :- nat(X). ?- addi(X, Y, s(s(s(s(0))))). X=0 Y = s(s(s(s(0)))) Yes ?- addi(X, s(s(0)), s(s(s(s(s(0)))))). X = s(s(s(0))) Yes ?- THREE = s(s(s(0))), FIVE = s(s(s(s(s(0))))), addi(THREE, FIVE, EIGHT). THREE = s(s(s(0))) FIVE = s(s(s(s(s(0))))) EIGHT = s(s(s(s(s(s(s(s(0)))))))) Yes Ví d III.3 : Tìm ư c s chung l n nh t (GCD: Greatest Common Divisor) Cho trư c hai s nguyên X và Y, ta c n tính ư c s D và USCLN d a trên ba quy t c như sau : 1. N u X = Y, thì D b ng X. 2. N u X < Y, thì D b ng USCLN c a X và c a Y - X. 3. N u X > Y, thì th c hi n tương t bư c 2, b ng cách hoán v vai trò X và Y.
78 L p trình lôgic trong Prolog Có th d dàng tìm ư c các ví d minh ho s ho t ng c a ba quy t c trư c ây. V i X =20 và Y =25, thì ta nh n ư c D =5 sau m t dãy các phép tr . Chương trình Prolog ư c xây d ng như sau : ). gcd( X, X, X gcd( X, Y, D ) :- X < Y, Y1 is Y – X, Y1, D ). gcd( X, gcd( X, Y, D ) :- X > Y, gcd( Y, X, D ). ích cu i cùng trong m nh th ba trên ây có th ư c thay th b i : X1 is X – Y, gcd( X1, Y, D ). K t qu ch y Prolog như sau : ?- gcd( 20, 55, D ). D=5 Ví d III.4 : Tính giai th a fac(0, 1). fac(N, F) :- N > 0, M is N - 1, fac(M, Fm), F is N * Fm. M nh th hai có nghĩa r ng n u l n lư t : N > 0, M = N - 1, Fm is (N-1)!, và F = N * Fm, thì F là N!. Phép toán is gi ng phép gán trong các ngôn ng l p trình m nh l nh nhưng trong Prolog, is không gán giá tr m i cho bi n. V m t lôgich, th t các m nh trong v ph i c a m t lu t không có vai trò gì, nhưng l i có ý nghĩa th c hi n chương trình. M không ph i là bi n trong l i g i th t c quy vì s gây ra m t vòng l p vô h n. Các nh nghĩa hàm trong Prolog thư ng r c r i do hàm là quan h mà không ph i là bi u th c. Các quan h ư c nh nghĩa s d ng nhi u lu t và th t các lu t xác nh k t qu tr v c a hàm... Ví d III.5 : Tính s Fibonacci /* Fibonacci function */
79 Các phép toán và s h c fib(0, 0). % fib0 = 0 % fib1 = 1 fib(1, 1). % fibn+2 = fibn+1 + fibn fib(N, F) :- N > 1, N1 is N - 1, fib(N1, F1), N2 is N - 2, fib(N2, F2), F is F1 + F2. ?- fib(20, F). F = 10946 Yes ?- fib(21, F). ERROR: Out of local stack Ta nh n th y thu t toán tính s Fibonacci trên ây s d ng hai l n g i quy ã nhanh chóng làm y b nh và ch v i N=21, SWI-prolog ph i d ng l i thông báo l i. Ví d III.6 : Tính hàm Ackerman /* Ackerman's function */ ack(0, N, A) :- % Ack(0, n) = n + 1 A is N + 1. ack(M1, 0, A) :- % Ack(m, n) = Ack(m-1, 1) M > 0, M is M - 1, ack(M, 1, A). % Ack(m, n) = Ack(m-1, Ack(m, n-1)) ack(M1, N1, A) :- M1 > 0, N1 > 0, M is M - 1, N is N - 1, ack(M1, N, A1), ack(M, A1, A). Ví d III.7 : Hàm tính t ng plus(X, Y, Z) :- nonvar(X), nonvar(Y), Z is X + Y. plus(X, Y, Z) :- nonvar(Y), nonvar(Z), X is Z - Y. plus(X, Y, Z) :- nonvar(X), nonvar(Z), Y is Z - X. Ví d III.8 : Thu t toán h p nh t
80 L p trình lôgic trong Prolog Sau ây là m t thu t toán h p nh t ơn gi n cho phép x lý trư ng h p m t bi n nào ó ư c thay th (h p nh t) b i m t h ng mà h ng này l i có ch a úng tên bi n ó. Ch ng h n phép h p nh t X = f(X) là không h p l . % unify(T1, T2). % trư ng h p 2 bi n unify(X, Y) :- var(X), var(Y), X = Y. % trư ng h p bi n = không ph i bi n unify(X, Y) :- var(X), nonvar(Y), X = Y. % trư ng h p không ph i bi n = bi n unify(X, Y) :- nonvar(X), var(Y), Y = X. % nguyên t hay s = nguyên t hay s unify(X, Y) :- nonvar(X), nonvar(Y), atomic(X), atomic(Y), X = Y. % trư ng h p c u trúc = c u trúc unify(X, Y) :- nonvar(X), nonvar(Y), compound(X), compound(Y), termUnify(X, Y). % h p nh t h ng v i h ng ch a c u trúc termUnify(X, Y) :- functor(X, F, N), functor(Y, F, N), argUnify(N, X, Y). % h p nh t N tham i c a X và Y argUnify(N, X, Y) :- N>0, argUnify1(N, X, Y), Ns is N - 1, argUnify(Ns, X, Y). argUnify(0, X, Y). argUnify1(N, X, Y) :- % h p nh t các tham i có b c N arg(N, X, ArgX), arg(N, Y, ArgY), unify(ArgX, ArgY). Ví d III.9 : Lý thuy t s Ta ti p t c xây d ng hàm m i trên các s t nhiên ã ư c nh nghĩa trong ví d 1. Ta xây d ng phép so sánh hai s t nhiên d a trên phép c ng như sau : % phép c ng có tính giao hoán egal(+(X, 0), X). egal(+(0, X), X). → egal(+(X, s(Y)), s(Z)) :- % X YZ.egal(X+Y, Z) egal(X+s(Y), s(Z))
81 Các phép toán và s h c egal(+(X, Y), Z). Sau ây là m t s k t qu : ?- egal(s(s(0))+s(s(s(0))), s(s(s(s(s(0)))))). Yes ?- egal(+(s(s(0)), s(s(0))), X). X = s(s(s(s(0)))) ?- egal(+(X, s(s(0))), s(s(s(s(s(0)))))). X = s(s(s(0))) Yes ?- egal(+(X, s(s(0))), s(s(s(s(s(0)))))). X = s(s(s(0))) Yes ?- egal(X, s(s(s(s(0))))). X = s(s(s(s(0))))+0 ; X = 0+s(s(s(s(0)))) ; X = s(s(s(0)))+s(0) ; X = 0+s(s(s(s(0)))) ; X = s(s(0))+s(s(0)) ; X = 0+s(s(s(s(0)))) ; X = s(0)+s(s(s(0))) ; X = 0+s(s(s(s(0)))) ; X = 0+s(s(s(s(0)))) ; X = 0+s(s(s(s(0)))) ; No V i ích egal(X, Y) sau ây, câu tr l i là vô h n : ?- egal(X, Y). X = _G235+0 Y = _G235 ; X = 0+_G235 Y = _G235 ; X = _G299+s(0) Y = s(_G299) ; X = 0+s(_G302) Y = s(_G302) ;
82 L p trình lôgic trong Prolog X = _G299+s(s(0)) Y = s(s(_G299)) ; X = 0+s(s(_G309)) Y = s(s(_G309)) ; X = _G299+s(s(s(0))) Y = s(s(s(_G299))) ; X = 0+s(s(s(_G316))) Y = s(s(s(_G316))) ; X = _G299+s(s(s(s(0)))) Y = s(s(s(s(_G299)))) ; X = 0+s(s(s(s(_G323)))) Y = s(s(s(s(_G323)))) ; X = _G299+s(s(s(s(s(0))))) Y = s(s(s(s(s(_G299))))) ; ... X = 0+s(s(s(s(s(s(_G337)))))) Y = s(s(s(s(s(s(_G337)))))) ; X = _G299+s(s(s(s(s(s(s(0))))))) Y = s(s(s(s(s(s(s(_G299))))))) v.v...
83 Các phép toán và s h c III.2. T i ưu phép quy L i gi i các bài toán s d ng quy trong các ngôn ng l p trình nói chung thư ng ng n g n, d hi u và d qu n lý ư c chương trình. Tuy nhiên, trong m t s trư ng h p, s d ng quy l i x y ra v n v ph c t p tính toán, không nh ng t n kém b nh mà còn t n kém th i gian. Trong các ngôn ng m nh l nh, phép tính n! s d ng quy c n s d ng b nh có c 0(n) và th i gian tính toán cũng có c 0(n), thay vì g i quy, ngư i ta thư ng s d ng phép l p fac=fac*i, i=1..n. Ta xét l i ví d 4 tính s Fibonacci trên ây v i l i g i quy : fib(N, F) :- N > 1, N1 is N - 1, fib(N1, F1), N2 is N - 2, fib(N2, F2), F is F1 + F2. ý r ng m i l n g i hàm fib(n) v i n>1 s d n t i hai l n g i khác, nghĩa là s l n g i s tăng theo lu th a 2. V i n l n, chương trình g i quy như v y d gây tràn b nh . Ví d sau ây là t t c các l i g i có th cho trư ng h p n=5. fib5 4 3 3 2 2 1 2 1 1 0 1 0 1 0 Hình III.1. Bi u di n cây các l i g i quy tìm s Fibonacci M t s ngôn ng m nh l nh tính s Fibonacci s d ng c u trúc l p tránh tính i tính l i cùng m t giá tr . Chương trình Pascal dư i ây dùng hai bi n ph x=fib(i) và y=fib(i+1) : { tính fib(n) v i n > 0 } i:= 1; x:= 1; y:= 0; while i < n do begin x:= x + y; y:= x – y end; Ta vi t l i chương trình Prolog như sau : fibo(0, 0). fibo(N, F) :- N >= 1, fib1(N, 1, 0, F). fib1(1, F, _, F). fib1(N, F2, F1, FN) :-
84 L p trình lôgic trong Prolog N > 1, N1 is N - 1, F3 is F1 + F2, fib1(N1, F3, F2, FN). ?- fibo(21, F). F = 10946 Yes ?- fibo(200, F). F = 2.80571e+041 Yes III.3. M t s ví d khác v quy III.3.1. Tìm ư ng i trong m t th có nh hư ng Cho m t th có nh hư ng như sau : A B C D E Hình III.2. Tìm ư ng i trong m t nh hư ng. th có Ta xét bài toán tìm ư ng i gi a hai nh c a th . M i cung n i hai nh ca th bi u di n m t quan h gi a hai nh này. T th trên, ta có th vi t các m nh Prolog bi u di n các s ki n : arc(a, b). arc(b, c). arc(c, e). arc(c, d). arc(a, e). Gi s c n ki m tra có t n t i m t ư ng i gi a hai nút a và d (không t n t i ư ng i gi a hai nút này như ã mô t ), ta vi t m nh : path(a, d). nh nghĩa này, ta nh n xét như sau : • T n t i m t ư ng i gi a hai nút có cung n i chúng.
85 Các phép toán và s h c • T n t i m t ư ng i gi a hai nút X và Y n u t n t i m t nút th ba Z sao cho t n t i m t ư ng i gi a X và Z và m t ư ng i gi a Z và Y. Ta vi t chương trình như sau : path(X, Y) :- arc(X, Y). path(X, Y) :- arc(X, Z), path(Z, Y). Ta th y nh nghĩa th t c path(X, Y) tương t th t c tìm t tiên gián ti p gi a hai ngư i trong cùng dòng h ancestor(X, Y) ã xét trư c ây. ?- path(X, Y). X=a Y=b; X=b Y=c; ... III.3.2. Tính dài ư ng i trong m t th Ta xét bài toán tính dài ư ng i gi a hai nút, t nút u n nút cu i trong m t th là s cung gi a chúng. Ch ng h n dài ư ng i gi a hai nút a và d là 3 trong ví d trên. Ta l p lu n như sau : • N u gi a hai nút có cung n i chúng thìdài ư ng i là 1. • G i L là dài ư ng i gi a hai nút X và Y, L1 là dài ư ng i gi a m t nút th ba Z và Y n u t n t i và gi s có cung n i X và Z, khi ó L = L1 + 1. Chương trình ư c vi t như sau : trajectory(X, Y, 1) :- arc(X, Y). trajectory(X, Y, L) :- arc(X, Z), trajectory(Z, Y, L1), L is L1 + 1. trajectory(a, d, L). L=3 Yes III.3.3. Tính g n úng các chu i Trong Toán h c thư ng g p bài toán tính g n úng giá tr c a m t hàm s v i chính xác nh tuỳ ý (e) theo phương pháp khai tri n thành chu i Max Loren. Ví d tính hàm mũ ex v i chính xác 10-6 nh khai tri n chu i Max Loren :
86 L p trình lôgic trong Prolog x 2 x3 ex = 1 + x + + ... + 2! 3! G i expower(X, S) là hàm tính giá tr hàm mũ theo X, bi n S là k t qu chính xác e=10-6. T công th c khai tri n Max Loren trên ây, g n úng v i ta nh n th y giá tr c a hàm mũ ex là t ng vô h n có d ng : sum(0) = 1, t0 = 1 tương ng v i x = 0 và ex = 1 sum(i+1) = sum(i) + ti+1, v i ti+1 = ti * x /( i+1), i = 0, 1, 2 ... th c hi n phép l p, ta c n xây d ng hàm quy tính t ng sum(X, S, I, T) trong ó s d ng các bi n trung gian I là bư c l p th i và T là s h ng ti. Theo cách xây d ng này, hàm tính t ng sum(X, S, I, T) là t ng c a các s h ng th I tr i c a chu i. Quá trình tính các t ng d ng l i khi ti< e, nghĩa là ã t ưc chính xác e. T i th i i m này, giá tr c a t ng cũng chính là s h ng ti. i u ki n kh i ng quá trình l p là chuy n v t expower(X, S) thành v t tính t ng sum(X, S, I, T) v i giá tr u I=0 và T=1. Ta có chương trình quy như sau : expower(X, S) :- sum(X, S, 0, 1). sum(_, T, _, T) :- abs(T) < 0.000001. sum(X, S, I, T) :- abs(T) > 0.000001, I1 is I + 1, T1 is T*X/I1, sum(X, S1, I1, T1), S is S1 + T. ?- expower(1, S). S = 2.71828 Yes ?- expower(10, S) S = 22026.5 Yes Tóm t t chương 3 • Các phép toán s h c ư c th c hi n nh các th t c thư ng trú trong Prolog.
87 Các phép toán và s h c • Vai trò c a các phép toán tương t vai trò c a các hàm t , ch nhóm các thành ph n c a các c u trúc mà thôi. • M i NLT có th t nh nghĩa nh ng phép toán riêng c a mình. M i phép toán ư c nh nghĩa b i tên, ưu tiên và ki u g i tham i. • Các phép toán cho phép NLT v n d ng cú pháp linh ho t cho các nhu c u riêng c a h . S d ng các phép toán làm cho chương trình tr nên d c (readability). tính m t bi u th c s h c, m i tham i có m t trong bi u th c ó ph i • ư c ràng bu c b i các giá tr s . • Ch d n op dùng nh nghĩa m t phép toán m i, g m các y u t : tên, ki u và ưu tiên c a phép toán m i. • S d ng các phép toán trung t , ti n t , ho c h u t làm tăng cư ng tính d c c a m t chương trình Prolog. ưu tiên là m t s nguyên n m trong m t kho ng giá tr cho trư c, thông • thư ng n m gi a 1 và 1200. Hàm t chính c a m t bi u th c là phép toán có ưu tiên cao nh t. Các phép toán có ưu tiên th p nh t ư c ưu tiên nh t. • Ki u c a m t phép toán ph thu c vào hai y u t : 1. v trí c a phép toán so v i các tham i, 2. ưu tiên c a các tham i ư c so sánh v i ưu tiên c a phép toán. i v i các ký hi u c t xfy, tham i x có ưu tiên bé hơn h n ưu tiên c a phép toán, còn tham i y có ưu tiên bé hơn ho c b ng ưu tiên c a phép toán. Bài t p chương 3 1. Cho bi t k t qu c a các câu h i sau ây : ?- X=Y. ?- X is Y ?- X=Y, Y=Z, Z=1. ?- X=1, Z=Y, X=Y. ?- X is 1+1, Y is X. ?- Y is X, X is 1+1. ?- 1+2 == 1+2. ?- X == Y. ?- X == X.