Giáo trình Trí tuệ nhân tạo (Phần 2)

cat(Y) (“Y là mèo”), animal(Z) (“Z là động vật”). Hãy biểu diễn câu sau trong logic vị từ: “chó, mèo đều là động vật”. 1.3.2. Chuẩn hoá các công thức Từ các câu phân tử, bằng cách sử dụng các kết nối logic và các lượng từ, ta có thể tạo ra các câu phức hợp có cấu trúc rất phức tạp. Để dễ dàng cho việc lưu trữ các câu trong bộ nhớ và thuận lợi cho việc xây dựng các thủ tục suy diễn, chúng ta cần chuẩn hoá các câu bằng cách đưa chúng về dạng chuẩn tắc hội (hội của các câu tuyển). Trong mục này, chúng ta sẽ trình bày thủ tục chuyển một câu phức hợp thành một câu ở dạng chuẩn tắc hội tương đương. Thủ tục chuẩn hoá các công thức bao gồm các bước sau: a. Loại bỏ các kéo theo Để loại bỏ các kéo theo, ta chỉ cần thay công thức P Q bởi công thức tương đương  P  Q, thay P  Q bởi ( P  Q )  (P   Q ) b. Chuyển các phủ định tới các phân tử Điều này được thực hiện bằng cách thay công thức ở vế trái bởi công thức ở vế phải trong các tương đương sau đây:  ( P)  P  (P  Q)   P   Q  (P  Q)   P   Q  (X (P))  X ( P)  (X (P))  X ( P)   122 c. Loại bỏ các lượng từ tồn tại Giả sử p(X,Y) là các vị từ có nghĩa rằng “Y lớn hơn X” trong miền các số. Khi đó công thức x (y (P(x,y))) có nghĩa là “với mọi số X, tồn tại Y sao cho số Y lớn hơn X”. Ta có thể xem Y trong công thức đó là hàm của đối số X, chẳng hạn f(X) và loại bỏ lượng tử Y, công thức đang xét trở thành X (P(X,f(X))). Ví dụ: f(X)=X+1, khi đó X (P(X,f(X)))  X (P(X, X+1)) nghĩa là với mọi giá trị của X thì X+1 lớn hơn X. Một cách tổng quát, giả sử Y(G) là một công thức con của công thức đang xét và nằm trong miền tác dụng của các lượng từ X1,...,Xn. Khi đó ta có thể xem Y là hàm của n biến X1,...,Xn, chẳng hạn f(X1,...,Xn). Sau đó ta thay các xuất hiện của Y trong công thức G bởi hạng thức f(X1,...,Xn) và loại bỏ các lượng từ tồn tại. Các hàm f được đưa vào để loại bỏ các lượng từ tồn tại được gọi là hàm Scholem. Ví dụ: Xét công thức sau X (Y (P(X,Y))  U (V (Q(a,V)  Y ( R(X,Y)))) (1) Công thức con Y (P(X,Y) nằm trong miền tác dụng của lượng từ X, ta xem Y là hàm của X: f(X). Các công thức con V (Q(a,V)) và Y ( R(X,Y)) nằm trong miền tác dụng của các lượng tử X, U ta xem V là hàm g(X,U) và Y là hàm h(X,U) của hai biến X, U. Thay các xuất hiện của Y và V bởi các hàm tương ứng, sau đó loại bỏ các lượng từ tồn tại, từ công thức (1) ta nhận được công thức: X (P(X,f(X))  U (Q(a,g(X,U))   R(X,h(X,U)))) (2) d. Loại bỏ các lượng từ phổ dụng Sau bước 3 trong công thức chỉ còn lại các lượng từ phổ dụng và mọi xuất hiện của biến đều nằm trong miền tác dụng của các lượng từ phổ dụng. Ta có thể loại bỏ tất cả lượng từ phổ dụng, công thức (2) trở thành công thức: P(X,f(X))  Q(a,g(X,U))   R(X,h(X,U))) (3)   123 Cần chú ý rằng, sau khi được thực hiện bước này tất cả các biến trong công thức được xem là chịu tác dụng của các lượng tử phổ dụng. e. Chuyển các tuyển tới các literal Bước này được thực hiện bằng cách thay các công thức dạng: P(QR) bởi (PQ)(PR) và thay (PQ)R bởi (PQ)(PR). Sau bước này công thức trở thành hội của các câu tuyển nghĩa là ta nhận được các công thức ở dạng chuẩn tắc hội. Chẳng hạn, công thức (3) được chuyển thành công thức sau: (P(X,f(X))  Q(a,g(X,U)))  (P(X,f(X))   R(X,h(X,U))) (4) f. Loại bỏ các hội Một câu hội là đúng nếu và chỉ nếu tất cả các thành phần của nó đều là đúng. Do đó công thức ở dạng chuẩn tắc hội tương đương với tập các thành phần. Chẳng hạn, công thức (4) tơng đơng với tập hai câu tuyển sau: P(f(X))  Q(a,g(X,U)) P(f(X))   R(X,h(X,U)) (5) g. Đặt tên lại các biến Đặt tên lại các biến sao cho các biến trong các câu khác nhau có tên khác nhau, chẳng hạn hai câu (5) có hai biến cùng tên là X, ta cần đổi tên biến X trong câu hai thành Z, khi đó các câu (5) tương đương với các câu sau: P(f(X))  Q(a,g(X,U)) P(f(Z))   R(Z,h(Z,U)) (5’) Như vậy, khi tri thức là một tập hợp nào đó các công thức trong logic vị từ, bằng cách áp dụng thủ tục trên ta nhận được cơ sở tri thức chỉ gồm các câu tuyển (tức là ta luôn luôn có thể xem mỗi câu trong cơ sở tri thức là tuyển của các literal). Hoàn toàn tương tự như trong logic mệnh đề, mỗi câu tuyển có thể biểu diễn dưới dạng một kéo theo, vế trái của kéo theo là hội của các câu phân   124 tử, còn vế phải là tuyển của các câu phân tử. Dạng câu này được gọi là câu Kowlski, một trường hợp quan trọng của câu Kowlski là câu Horn (luật if- then) Bài tập 1) Gọi vị từ nt(X) có nghĩa là “X là số nguyên tố” và vị từ sl(X) có nghĩa là “X là số lẻ”. Hãy diễn giải ý nghĩa của công thức: X (nt(X) and sl(X)). Viết lại công thức trên sau khi lấy phủ định và diễn gii ý nghĩa của công thức đó. 2)Biến đổi công thức sau về dạng chuẩn tắc hội XY ((b(X)  c(X))  (d(Y)  b(Y)) 3) Gọi p(X,Y,Z) có nghĩa là: Z=X*Y, là một vị từ 3 biến trên tập số thực. Khi đó tính chất giao hoán của phép nhân X*Y=Y*X được diễn tả như sau: X,Y (p(X,Y,Z)) p(Y,X,Z) Hãy chuẩn hóa công thức trên (đưa về dạng chuẩn tắc hội) 1.3.3. Các luật suy diễn Tất cả các luật suy diễn đã được đưa ra trong logic mệnh đề đều đúng trong logic vị từ cấp một. Bây giờ ta đưa ra một luật suy diễn quan trọng trong logic vị từ liên quan tới lượng tử phổ dụng a. Luật thay thế phổ dụng Giả sử G là một câu, câu X(G) là đúng trong một minh hoạ nào đó nếu và chỉ nếu G đúng với tất cả các đối tượng nằm trong miền đối tượng của minh hoạ đó. Mỗi hạng thức t ứng với một đối tượng, vì thế nếu câu X (G) đúng thì khi thay tất cả các xuất hiện của biến X bởi hạng thức t ta nhận được câu đúng. Công thức nhận được từ công thức G bằng cách thay tất ar các xuất hiện của x bởi t được ký hiệu là G[X/t]. Luật thay thế phổ dụng (universal instatiation) phát biểu rằng, từ công thức X (G) suy ra công thức G[X/t].   125 X (G) G[X/t] Chẳng hạn, từ câu X, like(X, “Football”) (mọi người đều thích bóng đá), bằng cách thay X bởi An ta suy ra câu like(“An”, “Football”) (An thích bóng đá). b. Hợp nhất Trong luật thay thế phổ dụng, ta cần sử dụng phép thế các biến bởi các hạng thức để nhận được các công thức mới từ công thức chứa các lượng tử phổ dụng. Ta có thể sử dụng phép thế để hợp nhất các câu phân tử (tức là để các câu trả lời thành đồng nhất). Chẳng hạn xét hai câu phân tử like(“An”,Y) và x, like(X, “Football”) mà để cho đơn giản ta bỏ đi các lượng tử phổ dụng. Sử dụng phép thế [X/An. Y/Football] hai câu trên trở thành đồng nhất like(“An”, “Football”). Trong các suy diễn, ta cần sử dụng phép hợp nhất các câu bởi các phép thế. Chẳng hạn, cho trước hai câu friend(X,”Ba”) good(X) (mọi bạn của Ba đều là tốt) friend(“Lan”,Y) ( Lan là bạn của của tất cả mọi người) Ta có thể hợp nhất hai câu friend(X,”Ba”) good(X) và friend(“Lan”,Y) bởi phép thay thế [X/Lan, Y/Ba] friend(“Lan”,”Ba”) good(“Lan”) friend(“Lan”,”Ba”) Từ hai câu này, theo luật Modus Ponens, ta suy ra câu good(“Lan”) (Lan là người tốt) Một cách tổng quát, một phép thế  là một dãy các cặp Xi/ti,  = [X1/t1 X2/t2.... Xn/tn] trong đó các Xi là các biến khác nhau, các ti là các hạng thức và các Xi không có mặt trong ti (i=1,....,n). Áp dụng phép thế  vào công thức G, ta nhận được công thức G0, đó là công thức nhận được từ công thức G bằng cách thay mỗi sự xuất hiện của các Xi bởi ti. Chẳng hạn, nếu G=p(X,Y,f(a,X)) và =[X/b, Y/g(Z)] thì G0=P(b,g(Z),f(a,b)).   126 Với hai câu phân tử G và H mà tồn tại phép thế  sao cho G0 và H0 trở thành đồng nhất (G0=H0) thì G và H được gọi là hợp nhất được, phép thế  được gọi là hợp nhất tử của G và H. Chẳng hạn, hai câu Like(An,y) và Like(x, Football) là hợp nhất được bởi hợp nhất tử [X/An, Y/Football]. Vấn đề đặt ra là với hai câu phân tử bất kỳ G và H, chúng có hợp nhất được không và nếu có thì làm thế nào tìm được hợp nhất tử?. c. Luật Modus Ponens tổng quát Giả sử Pi, Pi’ (i=1,...,n) và Q là các công thức phân tử sao cho tất cả các cặp câu Pi, Pi’ hợp nhất được bởi phép thế , tức là Pi0=Pi0’ (i=1,...,n). Khi đó ta có luật: (Pi  ...  Pn  Q), Pi’,...,Pn’ Q’ Trong đó Q’=Q Ví dụ: Giả sử ta có các câu student(X)  male(X)  like(X,“Football”) và student(“Anh”), male(“Anh”). Với phép thế  = [X/Anh], các cặp câu student(X), student(“Anh”) và male(X), male(“Anh”) hợp nhất được. Do đó ta suy ra câu like(“Anh”, “Football”). d. Luật phân giải tổng quát - Luật phân giải trên các câu tuyển Giả sử ta có hai câu tuyển A1  ...  Am  C và B1  ...  Bn   D, trong đó Ai (i=1,..., m) và Bj (j=1,..., n) là các literal, còn C và D là các câu phân tử có thể hợp nhất được bởi phép thế , C=D. Khi đó ta có luật: A1  ...  Am  C, B1  ...  Bn   D A1’  ...  Am’  B1’  ...  Bn’ Trong đó Ai’=Ai (i=1,..., m) và Bj’=Bj (j=1,..., n)   127 Trong luật phân giải này, hai câu ở tử số (giả thiết) của luật được gọi là hai câu phân giải được, còn hai câu ở mẫu số (kết luận) của luật được gọi là phân giải thức của hai câu ở tử số. Ta sẽ ký hiệu của hai câu A và B là Res(A,B). Ví dụ: Giả sử ta có hai câu A=hear(X, “Music”)  play(x, “Tennis”) và B=play(“An”,Y)  study(“An”). Hai câu play(X,“Tennis”) và play(“An”, Y) hợp nhất được bởi phép thế =[X/An, Y/Tennis]. Do đó từ hai câu đã cho, ta suy ra câu hear(“An”, “Music”)  study(“An”). Trong ví dụ này, hai câu A= hear(X, “Music”)  play(X, “Tennis”) và B= play(“An”, Y)  study(“An”) là phân giải được và phân giải thức của chúng là hear(“An”, “Music”)  study(“An”). - Luật phân giải trên các câu Horn Câu Horn (luật If- then) là câu có dạng: P1  ...  Pm  Q Trong đó Pi (i=1,..., m; m 0) và Q là các câu phân tử. Giả sử, ta có hai câu Horn P1  ...  Pm  S  Q và R1  ...  Rn  T, trong đó hai câu S và T hợp nhất được bởi phép thế , S=T. khi đó ta có luật: P1  ...  Pm  S  Q, R1  ...  Rn  T P1’  ...  Pm’  R1’  ...  Rn’  Q’ Trong đó, Pi’=Pi (i=1,..., m), Rj’=Rj (j=1,..., n), Q’=Q Trong thực tế, chúng ta thường sử dụng trường hợp riêng sau đây. Giả sử S và T là hai câu phân tử, hợp nhất được bởi phép thế . Khi đó ta có luật: P1  ...  Pm  S  Q, T P1’  ...  Pm’  Q’ Trong đó Pi’=Pi (i=1,..., m) và Q’=Q   128 Ví dụ: Xét hai câu student(X)  male(X)  play(X, “Football”) và male(“Ba”). Hai câu male(“Ba”) và male(X) hợp nhất được với phép thế [X/Ba], do đó từ hai câu trên ta suy ra student(“Ba”)  play(“Ba”, “Football”). 1.3.4. Thuật toán hợp nhất Về mặt cú pháp, hạng thức và công thức phân tử có cấu trúc giống nhau, do đó ta gọi các hạng thức và các công thức phân tử là các biểu thức đơn . Trong mục này, chúng ta sẽ trình bày thuật toán xác định hai biểu thức đơn cho trước có hợp nhất được hay không và nếu được thuật toán sẽ cho ra hợp nhất tử tổng quát nhất. Như ta đã biết, một phép thế  là một danh sách [X1/t1 X2/t2.... Xn/tn], trong đó các Xi là các biến khác nhau, ti là các hạng thức không chứa Xi (i=1,...,n). Kết quả áp dụng phép thế  vào biểu thức E là biểu thức E nhận được từ E bằng cách thay mỗi xuất hiện của biến Xi bởi ti. Hai biểu thức được xem là hợp nhất được nếu tồn tại phép thế  để chúng trở thành đồng nhất và khi đó  được gọi là hợp nhất tử của chúng. Chẳng hạn, xét hai biểu thức sau: know(“An”, X) know(Y, husband(Z)) Với phép thế  = [Y/An, X/ husband(Z)], cả biểu thức trên trở thành know(“An”, husband(Z)) Tuy nhiên, nếu hai biểu thức hợp nhất được thì nói chúng sẽ có vô số hợp nhất tử. Chẳng hạn, ngoài hợp nhất tử đã nêu, hai câu know(“An”, X) và know(Y, husband(Z)) còn có các hợp nhất tử sau: [Y/An, X/ husband(“Hoa”), Z/ Hoa] [Y/An, X/ husband(“Lan”), Z/ Lan] ... Chúng ta sẽ gọi hợp thành của hai phép thế  và  là phép thế  sao cho với mọi biểu thức E ta có E()=E(). Nói cụ thể hơn, hợp thành của phép thế   129  = [X1/t1 X2/t2.... Xn/tm] và = [Y1/s1 Y2/s2.... Yn/sn] là phép thế = [X1/t1 X2/t2.... Xn/tm, Y1/s1 Y2/s2.... Yn/sn] trong đó ta cần loại bỏ các cặp Yi/si mà Yi trùng với một Xk nào đó. Ví dụ Xét hai phép thế:  = [X/a, V/g(Y,Z)]  = [X/b, Y/c, Z/f(X), V/h(a)] khi đó hợp thành của chúng là phép thế:  = [X/a, V/g(c,f(X)), Y/c, Z/f(X)] Quan sát ví dụ trên ta thấy rằng phép thế  áp đặt nhiều hạn chế cho các biến hn là . Do đó ta sẽ nói rằng phép thế  tổng quát hơn phép thế . Chẳng hạn, phép thế đã đưa ra ở trên [Y/An, X/ husband(Z)] tổng quát hơn phép thế [Y/An, X/ husband(“Hoa”), Z/ “Hoa”]. Giả sử E và F là hai biểu thức đơn hợp nhất được. Ta gọi hợp nhất tử tổng quát nhất của E và F là hợp nhất tử  sao cho  tổng quát hơn bất kỳ hợp nhất tử  nào của E và F. Nói một cách khác,  là hợp nhất tử tổng quát nhất của E và F nếu với mọi hợp nhất tử  của E và F đều tồn tại phép thế  sao cho =. Chẳng hạn với E và F là các câu know( An , X) và know(Y, husband(Z)) thì hợp nhất tử tổng quát nhất là:  = [Y/An, X/ husband(Z)] Sau đây chúng ta sẽ trình bày thuật toán hợp nhất, đó là thuật toán có ba tham biến: hai biểu thức đơn E, F và hợp nhất tử tổng quát nhất là . Thuật toán sẽ dừng và cho ra hợp nhất tử tổng quát nhất  nếu E và F hợp nhất được. Nếu E và F không hợp nhất được, thuật toán cũng sẽ dừng và cho thông báo về điều đó. Ta sẽ giả sử rằng E và F chứa các biến có tên khác nhau, nếu không ta chỉ cần đặt tên lại các biến. Trong thuật toán ta cần tìm sự khác biệt giữa hai biểu thức. Sự khác biệt đựoc xác định như sau: Đọc hai biểu thức đồng thời từ trái sang phải cho tới khi gặp hai ký hiệu khác nhau trong biểu thức. Trích ra hai biểu thức con bắt đầu từ các ký hiệu khác nhau đó. Cặp biểu thức con đó tạo thành sự khác biệt giữa hai biểu   130 thức đã cho. Ví dụ: Sự khác biệt giữa hai câu like(X,f(a,g(Z)) và like(X,Y) là cặp (f(a,g(Z),Y), còn sự biệt giữa hai câu know(X,f(a,U)) và know(X,f(a,g(b))) là cặp (U,g(b)). Thuật toán hợp nhất được mô tả bởi thủ tục đệ quy sau: Procedure Unify(E, F, ); Begin 1. Xác định sự khác biệt giữa E và F; 2. If không có sự khác biệt then {thông báo thành công; stop} 3. If sự khác biệt là cặp (X, t), trong đó X là biến, t là hạng thức không chứa X then begin 3.1. E  E[X/t]; F F[X/t]; {tức là áp dụng phép thế [X/t] vào các biểu thức E và F} 3.2.   [X/t]; {hợp thành của phép thế ? và phép thế [X/t] } 3.3. Unify(E, F, ); end else {thông báo thất bại; stop} End; Thuật toán hợp nhất trên luôn luôn dừng sau một số bước hữu hạn bước vì cứ mỗi lần bước 3 được thực hiện thì số biến còn lại trong hai biểu thức sẽ bớt đi một mà số biến trong hai biểu thức là hữu hạn. Để biết hai biểu thức P và Q có hợp nhất được hay không ta chỉ cần gọi thủ tục Unify(P,Q, ), trong đó  là phép thế rỗng. P(a, X, f(a,g(X,Y)))   131 P(U, h(a), f(U,V)) (1) Sự khác biệt giữa hai biểu thức này là (a,U). Thế U bởi a ta nhận được hai biểu thức sau: P(a, X, f(a,g(X,Y))) P(a, h(a), f(a,V)) (2) Và phép thế  =[U/a] Sự khác biệt giữa hai biểu thức (2) là (X,h(a)). Thế x bởi h(a), ta có hai biểu thức sau: P(a, h(a), f(a,g(h(a),Y))) P(a, h(a), f(a,V)) (3) Và phép thế  =[U/a, X/h(a)] Sự khác biệt giữa hai biểu thức (3) là (g(h(a),Y), V). Thế V bởi g(h(a),Y), hai biểu thức (3) trở thành đồng nhất: P(a, h(a), f(a,g(h(a),Y))) (4) Như vậy hai câu (1) hợp nhất được vi hợp nhất tử tổng quát nhất là:  =[U/a, X/h(a), V/g(h(a),Y)] 2. Một số thuật giải chứng minh. Một trong những vấn đề khá quan trọng của logic mệnh đề là chứng minh tính đúng đắn của phép suy diễn (a  b). Đây cũng chính là bài toán chứng minh thường gặp trong toán học. Rõ ràng rằng với hai phép suy luận cơ bản của logic mệnh đề (Modus Ponens, Modus Tollens) cộng với các phép biến đổi hình thức, ta cũng có thể chứng minh được phép suy diễn. Tuy nhiên, thao tác biến đối hình thức là rất khó cài đặt được trên máy tính. Thậm chí điều này còn khó khăn với cả con người! Với công cụ máy tính, bạn có thể cho rằng ta sẽ dễ dàng chứng minh được mọi bài toán bằng một phương pháp "thô bạo" là lập bảng chân trị . Tuy về lý thuyết,   132 phương pháp lập bảng chân trị luôn cho được kết quả cuối cùng nhưng độ phức tạp của phương pháp này là quá lớn, O(2n) với n là số biến mệnh đề. Sau đây chúng ta sẽ nghiên cứu hai phương pháp chứng minh mệnh đề (ở mục 2.1 v à 2.2) với độ phức tạp chỉ có O(n ). Bài toán Cho tập các giả thiết dưới dạng các biểu thức logic mệnh đề GT={GT1, GT2, ...GTn}. Hãy chứng minh tập kết luận KL={KL1, KL2,..., KLm}. 2.1. Thuật giải Vương Hạo Cơ sở lý luận Cho các giả thiết GT1, GT2, ...,GTn. Để chứng minh tập kết luận KL1, KL2,...,KLm, ta chứng minh GT1, GT2,...,GTn  KL1, KL2,...,KLm: True Thuật giải bao gồm các bước sau: B1: Phát biểu lại giả thiết và kết luận của vấn đề theo dạng chuẩn sau : GT1, GT2, ..., GTn  KL1, KL2, ..., KLm Trong đó các GTi và KLi là các biểu thứclogic dạng chuẩn (chỉ chứa 3 phép toán cơ bản :  ,  ,  ) B2: Nếu GTi có phép  thì tách thành hai dòng con. Nếu ở Kli có phép  thì tách thành hai dòng con. Ví dụ: p  ( p  q)  q thì tách thành 2 dòng: p   p  q và p  q  q Hoặc nếu có p  q  q  r thì tách thành 2 dòng: P  q  q và p  q  r B3: Một dòng được chứng minh nếu:   133 1) Tồn tại chung một mệnh đề ở cả hai phía. Ví dụ : p  q  q  r: True 2) Tồn tại 2 mệnh đề phủ định lẫn nhau (p và p) Ví dụ: p   p  q: True B4 : a) Nếu một dòng không còn phép nối  hoặc  ở cả hai vế và ở 2 vế không có chung một biến mệnh đề thì dòng đó không được chứng minh. b) Một vấn đề được chứng minh nếu tất cả dòng dẫn xuất từ dạng chuẩn ban đầu đều được chứng minh. Ví dụ 1) Cần chứng minh rằng từ a  b  c và b  c  d và a và b, suy ra d (a  b  c)  (b  c  d)  a  b  d a  (b  c  d)  a  b  d: T (b  c)  (b  c  d)  a  b  d b  (b  c  d)  a  b  d: T c  (b  c  d)  a  b  d c  b  a  b  d: T c  (c  d)  a  b  d c  c  a  b  d: T c  d  a  b  d: T Cây suy diễn trong giải thuật Vương Hạo   134 2) Xét các câu đúng sau: “Nếu trời mưa thì Lan mang theo dù” “Nếu Lan mang theo dù thì Lan không bị ướt” “Nếu trời không mưa thì Lan không bị ướt” a) Xây dựng các câu trên bằng các biểu thức logic mệnh đề b) Hãy chứng minh rằng “Lan không bị ướt” bằng phương pháp Vương Hạo Lời giải a) r: “Trời mưa” u: “Lan mang theo dù” w: “Lan bị ướt” Lúc đó, ta có các biểu thức logic đúng sau: r  u u  w r  w Ta phải chứng minh (r  u)  (u  w)  (r  w)  w: True 2.2. Thuật giải Robinson Thuật giải này do Robinson đề xuất và hoạt động dựa trên phương pháp chứng minh phản chứng. Phương pháp chứng minh phản chứng: Bài toán Chứng minh phép suy luận (a  b) là đúng (với a là giả thiết, b là kết luận). Phản chứng: giả sử b sai suy ra  b là đúng. Bài toán được chứng minh nếu a đúng và  b đúng sinh ra một mâu thuẫn.   135 B1 : Phát biểu lại giả thiết và kết luận của vấn đề dưới dạng chuẩn như sau: GT1, GT2, ...,GTn  KL1, KL2, .., KLm Trong đó : GTi và KLj là các biểu thức logic dạng chuẩn (chỉ chứa các phép toán :  ,  ,  ) B2 : Giả sử KL1, KL2,...KLm là đúng, lúc đó ta có các biểu thức logic đúng sau: { GT1, GT2, ..., GTn ,  KL1,  KL2, ...,  KLm } B3 : Sau đó đưa về dạng chuẩn hội (tích các tổng) Ví dụ: pq  t  p  (q  t) (p  q)  (p t) B4 : Xây dựng một mệnh đề mới bằng cách áp dụng đồng nhất đúng: (p  q)  (p  r)  q  r Nghĩa là: nếu (p q)  (p r): True thì có thêm biểu thức r  t: True và đưa vào tập giả thiết. Lặp lại quá trình trên cho đến khi sinh ra 2 mệnh đề có chân trị đối nhau (có sự mâu thuẫn) và bài toán lúc đó kết luận là được chứng minh, hoặc không tạo thêm mệnh đề mới nào gây mâu thuẫn và lúc này kết luận không chứng minh được. Ví dụ 1) Xét bài toán: Sau khi đưa về dạng chuẩn hội, để đơn giản, ta viết các biểu thức (chỉ chứa phép ) trên từng dòng. Ta có: 1. a  b  c 2. b  c  d   136 3. a 4. b Giả sử d đúng, ta có thêm các biểu thúc đúng sau: 5. d 6. b  c (Res 1A, 3) 7. a  c (Res 1B, 4) 8. c  d (Res 2A, 4) 9. b  c (Res 2C, 5) 10. c (Res 3, 7A) 11. c (Res 4, 9A) Mâu thuẫn giữa 10 và 11. Chứng minh xong. 2.3. Chứng minh bằng luật phân giải trên logic vị từ Trong phần logic mệnh đề, ta đã đưa ra các luật suy diễn quan trọng như: luật Modus Ponens, luật Modus Tolens, luật bắc cầu,..., luật phân giải. Chúng ta đã chỉ ra rằng luật phân giải là luật đầy đủ cho bác bỏ. Điều đó có nghĩa là bằng phương pháp chứng minh bác bỏ, chỉ sử dụng luật phân giải ta có thể chứng minh được một công thức có là hệ quả logic của một tập các công thức cho trước hay không. Kết quả quan trọng này sẽ được mở rộng sang logic vị từ. Giả sử ta có một cơ sở tri thức (CSTT) gồm các câu trong logic vị từ. Chúng ta luôn luôn xem CSTT đều đúng. Chẳng hạn minh hoạ đó là thế giới thực của vấn đề mà chúng ta đang quan tâm và CSTT gồm các câu mô tả sự hiểu biết của chúng ta về thế giới hiện thực đó. Không mất tính tổng quát, ta có thể xem các câu trong CSTT là các câu tuyển. Chúng ta có thể sử dụng luật phân giải để suy ra các câu mới là hệ quả logic của CSTT.   137 Ví dụ: Giả sử CSTT gồm các câu tuyển sau:  P(W)  Q(W) (1) P(X)  R(X) (2)  Q(Y)  S(Y)` (3)  R(z)  S(z) (4) Sau đây chúng ta sẽ đưa ra một chứng minh của câu S(a) từ CSTT trên bằng luật phân giải. Áp dụng luật phân giải cho câu (2) và (4) với phép thế [X/a, Z/a], ta suy ra câu sau: P(a)  S(a) (5) Áp dụng luật phân giải cho câu (1) và (3) với phép thế [w/a, y/a] ta nhận được câu:  P(a)  S(a) (6) Áp dụng luật phân giải cho câu (5) và (6), ta suy ra câu S(a)  S(a). Câu này tương đương với câu S(a). Chứng minh bằng cách áp dụng các luật suy diễn để dẫn tới điều cần phải chứng minh (như chứng minh trên) được gọi là chứng minh diễn dịch (deduction proof). Nhưng cần biết rằng luật phân giải không phải là luật đầy dủ cho diễn dịch, tức là từ một tập tiên đề, chỉ sử dụng luật phân giải chúng ta không thể sinh ra tất cả các câu là hệ quả logic của tiên đề đã cho. Tuy nhiên định lý phân giải (trong mục logic mệnh đề) vẫn còn đúng trong logic vị từ cấp một là thoã được hay không thoã được. Nếu một tập câu là không thax được thì qua một số bước áp dụng luật phân giải sẽ sinh ra một câu rỗng (tức là dẫn tới mâu thuẫn). Để chứng minh câu H là hệ quả logic của tập các câu {G1, G2,..., Gn} (các tiên đề), ta có thể áp dụng phương pháp chứng minh bác bỏ, tức là chứng minh tập câu {G1, G2,..., Gn,  H} không thoã được. Mặt khác, ở trên ta đã chỉ ra rằng   138 luật phân giải cho phép ta xác định được một tập câu là thoã được hay không thoã được. Vì vậy luật phân giải được xem là luật đầy đủ cho bác bỏ. Ví dụ Từ CSTT gồm các câu (1) đến (4) trong ví dụ trên, ta có thể chứng minh được câu S(a) bằng phưng pháp bác bỏ như sau. Thêm vào CSTT câu:  S(a) (7) (lấy phủ định của câu cần chứng minh), áp dụng luật phân gii cho câu (3) và (7) với phép thế [y/a], ta suy ra câu:  Q(a) (8) Từ câu (1) và (8) với phép thế [w/a], ta nhận được câu:  P(a) (9) Từ câu (4) và (7) với phép thế [z/a], ta suy ra câu:  R(a) (10) Từ câu (2) và (10) với phép thế [x/a], ta nhận được câu: P(a) (11) Áp dụng luật phân gii cho câu (9) và (11) ta nhận được câu rỗng (mâu thuẫn:  P(a) và P(a)). Thủ tục tổng quát sử dụng luật phân gii để chứng minh một công thức H có là hệ qu logic của một tập công thức G=[G1, G2,...,Gn] Procedure Proof_by_Resolution; Input: tập G=[G1, G2,...,Gn] các công thức {các tiên đề}, công thức cần chứng minh H Begin 1. Biến đổi các công thức Gi (i=1,....,n) vµ  H về dạng chuẩn hội; 2. Từ các dạng chuẩn hội nhận được ở bước 1, thành lập tập các câu tuyển C; 3. Repeat   139 3.1. Chọn ra hai câu A và B trong C; 3.2. If A và B phân gii được then Tính phân gii thức Res(A,B); 3.3. If Res(A,B) là câu mới then Thêm Res(A,B) vào tập C; Until nhận được câu rỗng hoặc không có câu mới nào được sinh ra; 4. If câu rỗng được sinh ra then Thông báo H đúng Else Thông báo H sai; End; 3. Ví dụ và bài tập. Để trình bày gọn, chúng ta quy ước - Phép và (hội hay tích) Ví dụ a và b được ký hiệu a  b hoặc ab - Phép hoặc (tuyển hay tổng) Ví dụ a hoặc b được ký hiệu a  b hoặc a+b - Phép phủ định Ví dụ phủ định của a được ký hiệu a - Phép kéo theo (suy ra) Ví dụ a kéo theo b được ký hiệu a  b Ví dụ 1 Cho các khẳng định đúng với các ý nghĩa như sau: a một người có nhóm máu A b một người có nhóm máu B c một người có nhóm máu AB o một người có nhóm máu O t mẫu máu của một người có xét nghiệm T dương tính   140 s mẫu máu của một người có xét nghiệm S dương tính Hãy viết các biểu thức logic diễn tả những ý tưởng sau: a. Nếu xét nghiệm T dương tính thì người đó có nhóm máu A hoặc AB b. Nếu xét nghiệm S dương tính thì người đó có nhóm máu B hoặc AB c. Nếu một người có nhóm máu B thì xét nghiệm S sẽ dương tính d. Một người có nhóm máu A, B, AB hoặc O Lời giải a. t  a+c b. s  b+c c. b s d. a + b+ c + o Ví dụ 2. Hãy biểu diễn các tri thức sau bằng logic mệnh đề a. Nếu n là số nguyên chẵn và n là số nguyên tố thì n=2 b. Số n là chính phương thì n tận cùng bằng 1, 4, 5, 6 hoặc 9 Lời giải a. Gọi a : “là một số nguyên chẵn”, b : “là một số nguyên tố”, c : “số nguyên 2”. Lúc đó, tri thức sẽ được biểu diễn như sau: ab c b. Gọi a : “là một số chính phương”, b : “số có chữ số tận cùng bằng 1” c : “số có chữ số tận cùng bằng 4” d : “số có chữ số tận cùng bằng 5” e : “số có chữ số tận cùng bằng 5” f : “số có chữ số tận cùng bằng 9”. Lúc đó, tri thức sẽ được biểu diễn như sau: a b+c+d+e+f   141 Ví dụ 3 Cho các biểu thức logic mệnh đề đúng sau 1. a  f 2. a  (f  p) 3. p+q  d 4. a 5. ad g Hãy dùng phương pháp Robinson và Vương Hạo để chứng minh hoặc bác bỏ g1 Lời giải - Chuyển về dạng chuẩn a  f a + f a  (f  p)  a +(fp)  a + (f + p)  a + f + p p+q  d  (p+q)+d  (pq)+d  (p + d)(q + d) ad g  (ad)+g  a+d+g - Dùng phương pháp phân giải Robinson Giả sử g1, ta có các biểu thức đúng sau 1. a + f 2. a + f + p 3. p + d 4. q + d 5. a 6. a+d+g 7. g 8. a+d res(63,7) 9. d res(5, 81)   142 10. a +f +d res(23,31) 11. a + d res(12,102) 12. d res(5,111) Ta thấy 9) kết hợp 12) sẽ cho ra câu rỗng (tức là có sự mâu thuẫn). Vì vậy g1. - Dùng phương pháp Vương Hạo Ta cần chứng minh: (a)(a + f )(a + f + p)(p + d)(q + d)(a+d+g)g: true(I) (1) (2) (3) (4) (5) Để chứng minh (I) tách (1), biểu thức (I) trở thành: I.1) (a)(a)(a + f + p)(p + d)(q + d)(a+d+g)  g : true I.2) af (a + f + p)(p + d)(q + d)(a+d+g)g Chứng minh I.2) tách 2), I.2) trở thành I.2.1) af (a)(p + d)(q + d)(a+d+g)  g: true I.2.2) af (f)(p + d)(q + d)(a+d+g)  g: true I.2.3) afp(p + d)(q + d)(a+d+g)  g Chứng minh I.2.3) tách 3), I.2.3) trở thành I.2.3.1) afp(p)(q + d)(a+d+g)  g: true I.2.3.2) afpd(q + d)(a+d+g)  g Chứng minh I.2.3.2) tách 5), I.2.3.2) trở thành I.2.3.2.1) afpd(q + d)(a)  g : true I.2.3.2.2) afpd(q + d)(d)  g : true I.2.3.2.3) afpd(q + d)g  g : true (I) được chứng minh, vì vậy g1   143 Bài tập1. Biểu diễn các tri thức sau dưới dạng logic mệnh đề a. Trong tam giác vuông, tổng bình phương chiều dài hai cạnh góc vuông bằng bình phương chiều dài cạnh huyền b. Một số nguyên dương có chữ số hàng đơn vị bằng 5 thì số đó chia hết cho 5 c. Nếu x là số lẻ và bình phương của x tận cùng bằng 1 thì x tận cùng bằng 1 hoặc bằng 9 d. Trong tam giác vuông, chiều dài của đườn trung tuyến xuất phát từ góc vuông bằng nữa chiều dài của cạnh huyền Bài tập 2. Cho các biểu thức logic mệnh đề đúng sau 1. n+c+d  p 2. qp  c 3. qc  f +h 4. n+p+h 5. nq Hãy dùng phương pháp Robinson và Vương Hạo để chứng minh hoặc bác bỏ f 1 Bài tập 3. Cho các biểu thức logic mệnh đề đúng sau 1. abc  c 2. abc  p 3. as  h 4. abcp  s 5. abd  Hãy dùng phương pháp Robinson và Vương Hạo để chứng minh hoặc bác bỏ sh 1 Bài tập 4. Ta có cơ sở tri thức của hệ chuyên gia về bệnh cảm cúm như sau:   144 1) “Nếu bệnh nhân rát họng và viêm nhiễm thì viêm họng và đi chữa họng“ 2) “Nếu thân nhiệt >370 thì sốt” 3) “ Nếu ốm trên 7 ngày và sốt thì viêm nhiễm” 4) “Nếu sốt và ho và kèm theo khó thở hoặc kèm theo tếng ran thì viêm phổi” a) Hãy biểu diễn các tri thức trên dưới dạng logic mệnh đề. b) Có một bệnh nhân khai : “Thân nhiệt > 370 “ và “ốm trên 7 ngày”. Dùng phương pháp chứng minh Robinson và Vương Hạo để kết luận bệnh nhân này bị "viêm nhiễm". Bài tập 5. Ta có cơ sở tri thức mô tả mối quan hệ của các thành phần trong một tam giác như sau: - Nếu biết 3 cạnh của 1 tam giác ta có thể biết nủa chu vi của tam giác đó - Nếu biết 2 cạnh và nữa chu vi của một tam giác thì ta có thể biết được cạnh còn lại của tam giác đó - Nếu biết được diện tích và một cạnh của một tam giác thì ta có thể biết được chiều cao tương ứng với cạnh đó - Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của một tam giác thì ta có thể biết được cạnh còn lại của tam giác đó. - Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của một tam giác thì ta có thể biết được diện tích của tam giác đó - Nếu biết ba cạnh và nữa chu vi của một tam giác thì ta biết được diện tích của tam giác đó - Nếu biết diện tích và đường cao của một tam giác thì ta biết được cạnh tương ứng với đường cao của tam giác đó Giả sử biết được 2 cạnh và và góc kẹp giữ hai cạnh đó. Bằng phương pháp Robinson, hãy chứng minh rằng ta có thể suy ra được đường cao tương ứng với cạnh còn lại   145 Hướng dẫn Ký hiệu a: cạnh a của tam giác k: đường cao tương ứng với cạnh a b: cạnh b của tam giác l: đường cao tương ứng với cạnh b c: cạnh c của tam giác m: đường cao tương ứng với cạnh c A: góc tương ứng với cạnh a S: diện tích của tam giác B: góc tương ứng với cạnh b p: nữa chu vi của tam giác C: góc tương ứng với cạnh c - Các tri thức đó được biểu diễn dưới dạng logic mệnh đề như sau: 10) abc  p  11) bpc  a  12) apc  b  13) abp  c  14) Sa  k  15) Sb  l  16) Sc  m  17) abC  c  18) acB  b  19) bcA  a  20) abC  S  21) acB  S  22) bcA  S  23) abcp  S  24) Sk  a  25) Sl  b  26) Sm  c  Sau đó dùng phương pháp Robinson (GT={a, b}, KL={m}) Bài tập 6. Biểu diễn các tri thức sau dưới dạng logic vị từ a. Bất kỳ người nào cũng có cha mẹ b. Mọi số nguyên tố lớn hơn 2 đều là số lẻ c. Chuồn chuồn bay thấp thì mưa Lời giải a. Ký hiệu NGUOI(X): nghĩa là X là người CHAME(X, Y): X là cha mẹ của Y   146 X ( NGUOI(X)  Y: CHAME (Y, X)) b. Ký hiệu P(X): X là số nguyên tố lớn hơn 2 Q(X): X là số lẽ X ( P(X)  Q(X)) c. Ký hiệu BAY(X,Y): con vật X bay với độ cao Y TROIMUA: trời mưa BAY(“chuồn chuồn”, “thấp”)  TROIMUA Bài tập 7. Giả sử chúng ta biết các thông tin sau đây: 1) Ông Ba nuôi một con chó 2) Hoặc ông Ba hoặc ông Am đã giết con mèo Bibi 3) Mọi người nuôi chó đều yêu quý động vật 4) Ai yêu quý động vật cũng không giết động vật 5) Chó mèo đều là động vật Ai đã giết Bibi? Lời giải - Biểu các thông tin trên dưới dạng logic vị từ cấp một như sau Để biểu diễn các tri thức trên trong logic vị từ cấp một, chúng ta cần sử dụng các hằng D, Ba, An, Bibi, các vị từ Dog(x) (x là chó), Cat(y) (y là mèo), Rear(u,v) (u nuôi v), AnimalLover(u) (u là người yêu quý động vật), Kill(u,v) (u giết v), Animal(x) (x là động vật). Sử dụng các hằng và các vị từ trên, chúng ta có thể chuyển các trên thành các câu trong logic vị từ cấp một như sau: 1) Dog(“D”) Rear(“Ba”, “D”) 2) Cat(“Bibi”) (Kill(“Ba”, “Bibi”) + Kill(“Am”, “Bibi”)) 3) X (Y(Dog(Y) Rear(X,Y))  AnimalLover(X))) 4) U (AnimalLover(U)  (V AnimalLover(V)  Kill(U,V)))   147 5) Z (Dog(Z)  Animal(Z)) W (Cat(W) Animal(W)) - Chuyển về dạng chuẩn và dùng phương pháp phân giải Robinson 1) Dog(“D”) 2) Rear(“Ba”, “D”) 3) Cat(“Bibi”) 4) Kill(“Ba”, “Bibi”) + Kill(“Am”, “Bibi”) 5) Dog(Y) + Rear(X,Y) + AnimalLover(X) 6) AnimalLover(U) + Animal(V) + Kill(U,V) 7) Dog(Z) + Animal(Z) 8) Cat(W) + Animal(W) Giả sử Kill(T, “Bibi”) đúng 9) Kill(T, “Bibi”) Từ câu (4) và câu (9) với phép thế [t/Am], ta nhận được câu: 10) Kill(“Ba”, “Bibi”) Từ câu (6) và câu (10) với phép thế [u/Ba, v/Bibi], ta nhận được câu: 11) AnimalLover(“Ba”) + Animal(“Bibi”) Từ câu (3) và câu (8) với phép thế [w/Bibi], ta nhận được câu: 12) Animal(“Bibi”) Từ câu (11) và câu (12), ta nhận được câu: 13) AnimalLover(“Ba”) Từ câu (1) và câu (5), với phép thế [y/D] ta nhận được câu: 14)  Rear(X, “D”) + AnimalLover(X) Từ câu (2) và câu (14), với phép thế [x/Ba] ta nhận được câu: 15) AnimalLover(“Ba”) Từ câu (13) và câu (15) ta suy ra câu rỗng (có sự mâu thuẫn). Như vậy ông Am đã giết con mèo Bibi. Bài tập 8. Giả sử chúng ta biết các thông tin sau đây:   148 a. Mọi người đếu chết b. Mọi phụ nữ đều chết c. Thần thánh không chết d. Tất cả cả những người bệnh phải được điều trị e. Beatrice là phụ nữ f. Christel là phụ nữ g. Marta là phụ nữ h. Socrate là người i. Zeus là thần thánh k. Socrate bị bệnh Dùng phương pháp phân giải Robinson để có thể suy ra được Socrate có được điều trị hay không?   148 Chương 5 TRI THỨC VÀ CÁC PHƯƠNG PHÁP SUY DIỄN Như ta đã biết con người sống trong môi trường có thể nhận được thế giới nhờ các giác quan và sử dụng tri thức tích luỹ được và nhờ khả năng lập luận, suy diễn, con người có thể đưa ra các hành động hợp lý cho công việc mà con người đang làm. Trong khi đó mục tiêu của trí tuệ nhân tạo ứng dụng là thiết kế các tác nhân thông minh (intelligent agent) cũng có khả năng đó như con người. (Tác nhân thông minh là bất cứ cái gì có thể nhận thức được môi trường thông qua các bộ cảm nhận (sensors) và đưa ra hành động hợp lý đáp ứng lại môi trường thông qua bộ phận hành động (effectors). Ví dụ: robots, softrobot (software robot), các hệ chuyên gia,...là các tác nhân thông minh). 1. Tri thức và dữ liệu - Tri thức là sự hiểu biết về một miền chủ đề (lĩnh vực) nào đó. Ví dụ - Hiểu biết về y học, văn học,.... là tri thức - Thu thập thông tin ta được dữ liệu và căn cứ vào tri thức ta có được những quyết dịnh phán đoán. Đối với quả cam ta xét các dữ liệu như vỏ, cuống, màu sắc,...của nó như thế nào? và dựa vào hiểu biết của ta mà xác định xem quả cam đó là ngon hay không ngon, ngon vừa,... Như vậy, tri thức là dạng dữ liệu bậc cao. Khó phân biệt giữa tri thức và dữ liệu (không có ranh giới rõ ràng giữa chúng). Tuy nhiên ta có thể phân biệt theo bảng sau: Dữ liệu Tri thức - Định lượng - Có cấu trúc đơn giản - Ở dạng đơn giản - Định tính - Không có cấu trúc hoặc có cấu trúc phức hợp - Ở dạng phức hợp   149 2. Các dạng mô tả tri thức (các phương pháp biểu diễn tri thức) (Để máy tính có thể sử dụng được tri thức, có thể xử lý được tri thức, chúng ta cần phải biểu diễn tri thức dưới dạng thuận tiện cho máy tính. Đó là mục tiêu của biểu diễn tri thức). Sau nhiều cố gắng, các nhà TTNT đã phát triển một số cách biểu diễn (thể hiện) tri thức có hiệu quả trong máy. 2.1. Biểu diễn tri thức bằng logic Như ta đã nghiên cứu ở phần trước, ta có thể biểu diễn bài toán bằng các biểu thức logic (logic mệnh đề, logic vị từ) 2.2. Biểu diễn tri thức bằng mạng ngữ nghĩa Phương pháp biểu diễn tri thức bằng cách dùng một đồ thị G = (V, E) gồm tập đỉnh V và tập cung E. Trong đó các đỉnh ứng với các đối tượng, khái niệm hay sự kiện cụ thể, các cung thể hiện quan hệ giữa các đối tượng. Có một cung nối giữa hai đối tượng a và đối tượng b, ký hiệu a b nếu có một quan hệ nào đó giữa hai đối tượng a, b. Có 2 loại quan hệ đặc biệt - "a là b" nghĩa là đối tượng a thuộc vào tập đối tượng được biểu diễn bởi khái niệm b hoặc tập các đối tượng biểu diễn bởi khái niệm a là tập con của tập đối tượng biểu diễn khái niệm b. (quan hệ is-a) Ví dụ Yến chim - Ngược lại với quan hệ "là" là quan hệ "bao gồm". Khi có " a là b" (hoặc "b bao gồm a"), các thông tin cơ bản về các đối tượng được cho bởi b sẽ truyền lại cho a (nghĩa là a được thừa hưởng những gì b có).   150 Ví dụ Ưu điểm: - Cho phép biểu diễn một cách trực quan các sự kiện và các mối liên hệ giữa chúng. - Tính mô đun cao theo nghĩa các tri thức mới được thêm vào hoàn toàn độc lập với các tri thức cũ. - Có thể áp dụng một số cơ chế suy diễn trên mạng: cơ chế truyền và thừa hưởng thông tin giữa các đối tượng, cơ chế "cháy" trên mạng Nhược điểm: - Không có một phương pháp suy diễn chung nào cho mọi loại mạng ngữ nghĩa - Khó kiểm soát quá trình cập nhật tri thức để dẫn đến mâu thuẫn trong cơ sở tri thức. 2.3. Biểu diễn tri thức bằng khung (Frame) Khung thực chất là sự tổng quát hoá của cấu trúc bản ghi trong Pascal và tương tự như cấu trúc đối tượng trong C++ Một khung được mô tả bởi cấu trúc: - Tên khung: Định danh đối tượng mô tả - Các khe (slot): trên mỗi khe lưu trữ các thông tin, n\miền giá trị, thuộc tính và chiều mũi tên chỉ đến các khung khác cánh Chim bay Con vậtYến Chíp chíp Cánh cụt đi Không khí is‐a  is‐a is‐a is‐a hoạt động hoạt động thở  có   151 Ví dụ Xét khung (frame) mô tả tập học sinh HOCSINH Frame HOCSINH IS-A: PART-OF: NGUOI-DI-HOC A KIND OF: (HOCSINHCOSO, HOCSINHTRUNGHOC) Cân nặng: 10-60kg Chiều cao: 80-170cm Cấu trúc frame này cho ta một "khung dữ liệu" để khoanh vùng các đối tượng là học sinh. Trường hợp gặp một người cao 175cm, nặng 45kg thì ta có thể khẳng định rằng đó không phải là học sinh vì không thoã mãn các ràng buộc đã có. Ngoài ra, một trong những đặc trưng quan trọng của frame là khả năng thừa kế các thông tin của các khe có cùng tên ở đối tượng bậc trên. Ví dụ Trong frame HOCSINHCOSO, HOCSINHTRUNGHOC có khe chiều cao với giá trị mô tả miền, thì sau khi thừa kế thông tin ở mức trên Frame HOCSINH, khe này cần phải lấy các giá trị trong khoảng 80-170cm. 2.4. Biểu diễn tri thức bằng các luật sản xuất Phương pháp biểu diễn tri thức nhờ logic (logic mệnh đề và logic vị từ) khá trực quan song chỉ phù hợp khi không có quá nhiều luật suy diễn. Một tri thức được thể hiện bằng một câu Horn dạng chuẩn: p1  p2 .... pn  q (Các câu Horn dạng này còn được gọi là luật if- then và được biểu diễn như sau: if P1 and....and Pm then Q) Một câu Horn dạng tổng quát: p1  p2 .... pn  q1  q2 .... qm   152 Lưu ý: Nếu có luật dạng: p1  p2 .... pn  q1  q2 .... qm thì tương đương với m luật sau: p1  p2 .... pn   q2 .... qm  q1 p1  p2 .... pn   q1   q3... qm  q2 p1  p2 .... pn   q1.... qm-1  qm Tuy nhiên ta chỉ xét câu Horn dạng chuẩn (m=1) - Nếu n=0, m=1: câu Horn có dạng  q: gọi là sự kiện (fact) q. - Nếu n>0, m=1: câu Horn có dạng: p1  p2 .... pn  q: gọi là luật (rule). Trong các hệ chuyên gia, cơ sở tri thức gồm 2 phần: tập các sự kiện (facts) và tập luật (rules). Ví dụ 1) Ta có các luật về kinh nghiệm dự báo thời tiết: "Chuồn chuồn bay thấp thì mưa, bay cao thì nắng, bay vừa thì râm" a: chuồn chuồn bay thấp, b: chuồn chuồn bay cao, c: chuồn chuồn bay vừa d: trời mưa, e: trời nắng, f: trời râm lúc đó ta có các luật sau: a  d b  e c  f 2) Nhiều định lý trong toán học có thể biểu diễn bởi các luật, ví dụ: Nếu tam giác có một góc bằng 600 và tam giác có hai cạnh bằng nhau thì tam giác đó là tam giác đều. 3. Suy diễn trên luật sản xuất 3.1. Khái niệm Suy diễn là quá trình suy luận dựa vào các quy luật đã cho, thiết lập các thông tin mới từ các thông tin đã biết. Suy diễn sẽ sử dụng tập sự kiện làm tiên đề.   153 Các phương pháp suy diễn dần dần chuyển từ các giả thiết về các kết luận bằng cách thêm vào giả thiết những sự kiện đã được khẳng định đúng, dựa trên 2 phương thức: - Modus ponens: A, AB B nghĩa là nếu A đúng và AB đúng thì B cũng đúng - Modus tollens B, AB A nghĩa là nếu B sai và biết rằng AB đúng thì A cũng sai. Trong quá trình suy diễn, ta cần quan tâm đến các vấn đề sau: - Xây dựng tập luật, câu hỏi nào được chọn để người sử dụng trả lời - Chọn quá trình tìm kiếm như thế nào - Thông tin nhận được có ảnh hưởng đến quá trình tìm kiếm không 3.2. Bài toán Cho tập sự kiện F= {f1, f2,...,fn} và tập luật R= {r1, r2,...,rm}. Chứng minh tập kết luận G đúng. 3.3. Các phương pháp suy diễn Quá trình suy diễn trong hệ luật sản xuất bao gồm 2 phương pháp cơ bản: suy diễn tiến và suy diễn lùi. a) Suy diễn tiến (lập luận tiến - forward chaining hoặc forward reasoning) (Tư tưởng cơ bản của suy diễn tiến là áp dụng luật suy diễn Modus Ponens tổng quát) Là quá trình suy diễn bắt đầu từ tập sự kiện đã biết, rút ra những sự kiện mới và cứ như vậy cho đến khi có được sự kiện cần chứng minh hoặc không có luật nào sinh ra các sự kiện mới (tập sự kiện đúng là cực đại). - Phương pháp GỌi T là tập các sự kiện tại thời điểm đang xét (khởi tạo tập T=F: tập sự kiện đúng ban đầu ).   154 Xét các luật ri có dạng: p1  p2  .... pn  q và pjT nj ,1 nghĩa là left (ri) T thì T= T+ right (ri) quá trình lặp lại cho đến khi G T hoặc không có luật nào sinh ra thêm sự kiện mới. - Giải thuật Procedure suydientien; Begin T:= F; S:= loc(R, T); { S: là tập luật có dạng p1  p2  .... pn  q sao cho pjT nj ,1 } While G  T and S do Begin r := get(S); T:= T + right(r); R:=R \ {r}; S:= loc(R,T); End; If G  T then write (“thành công”) Else write (“không thành công”); End; Ví dụ 1) Cho trước tập sự kiện F={a,b}. Sử dụng các luật: r1: a  c r2: b  d r3: c  e r4: a  d  e   155 r5: b  c  f r6: e  f  g cần suy ra g r T S R r1 r2 r3 r4 r5 r6 a, b a, b, c a, b, c, d a, b, c, d, e a, b, c, d, e a, b, c, d, e, f a. b, c, d, e, f, g r1, r2, r3 r2, r3, r5 r3, r4, r5 r4, r5 r5 r6 r1, r2, r3, r4, r5, r6 r2,...r6 r3,..., r6 r4, r5, r6 r5, r6 r6 gT nên bài toán được chứng minh (g: true) Chú ý - Quá trình suy diễn tiến là quá trình xem xét các luật, với mỗi luật ta xét phần điều kiện (ở vế trái) tới phần kết luận (ở vế phải) và khi mà tất cả các đièu kiện của luật đều thoã mãn thì ta suy ra sự kiện trong phần kết luận. Chính vì lẽ đó mà có tên là suy diễn tiến. - Trong mỗi bước của thủ tục, người ta xét một luật trong tập luật. So sánh mỗi điều kiện (ở vế trái) của tập luật với các sự kiện trong cơ sở sự kiện, nếu tất cả các điều kiện của luật được thoã mãn thì sự kiện trong phần kết luận được xem là sự kiện được suy ra. nếu sự kiện này là sự kiện mới (không có trong bộ nhớ làm việc) thì nó được đưa vào bộ nhớ làm việc. Quá trình trên cứ lặp lại cho đến khi nào không có luật nào sinh ra sự kiện mới.   156 - Quá trình suy diễn tiến không định hướng tới giải quyết một vấn đề nào cả, không hướng tới tìm ra câu trả lời cho một câu hỏi nào cả. Suy diễn tiến chỉ là quá trình suy ra các sự kiện mới từ các sự kiện có trong bộ nhớ làm việc. b) Suy diễn lùi (lập luận lùi - backward chaining hoặc backward reason) Là quá trình xuất phát từ sự kiện cần chứng minh và thay vào đó là những sự kiện ở vế trái của 1 luật có vế phải là sự kiện cần chứng minh. Quá trình này được thực hiện cho đến khi đưa về các sự kiện là tập sự kiện con của tập sự kiện giả thiết. (Nghĩa là: để đưa ra kết luận b, ta thử tìm tất cả các luật có dạng: a1  .... an  b, để có b, phải đưa ra các kết luận a1,...,an. Quá trình xác định ai cũng tương tự như đối với b, nếu đến một lúc nào đó phát hiện được rằng có một ai nào đó không dẫn xuất được từ các giả thiết thì quay lui sang các luật sản xuất khác sinh ra b có dạng b1....bm  b. Ngược lại, nếu mọi ai đều dẫn xuất được giả thiết thì quá trình dẫn xuất ra b là đúng) - Giải thuật GỌi T là tập các sự kiện cần chứng minh tại thời điểm đang xét (khởi tạo T= G, G là tập kết luận). S(p) ={riR / right(ri) = p} ( là tập các luật trong R sao cho vế phải chứa p) Procedure suydienlui (g); Begin T:= {g}; If T F then write (‘g đã được chứng minh ‘) Else Begin p:=get(T); If S(p) = {} then write (‘g không chứng minh được ‘)   157 Else For ri S(p) do Begin T:= T \ right(ri); T:= T + left(ri); For lT \ F do suydienlui(l); End; End; Ví dụ 1) Cho tập sự kiện F={p, r}, và tập luật R: r1) p  q r2) q  r  s Chứng minh s p r T S(p) s q r2 r1 s q, r r, p r2 r Nhận xét - Suy diễn tiến: Ưu điểm: i) Làm việc tốt khi bài toán có bản chất là đi thu thập thông tin rồi thấy điều cần suy diễn ii) Cho ra khối lượng lớn các thông tin từ một số thông tin ban đầu. Nó sinh ra nhiều thông tin mới. iii) Suy diễn tiến là tiếp cận lý tưởng đối với các loại bài toán cần giải quyết các nhiệm vụ như lập kế hoạch, điều hành, điều khiển và diễn dịch.   158 Nhược điểm: i) Không cảm nhận được rằng chỉ cần một vài thông tin quan trọng. Hệ thống hỏi các câu hỏi có thể hỏi mà không biết rằng chỉ một ít câu đã đi đến kết luận được. ii) Hệ thống có thể hỏi cả câu hỏi không liên quan. Có thể các câu trả lời cũng quan trọng nhưng làm người dùng lúng túng khi phải trả lời các câu chẳng dính đến chủ đề. - Suy diễn lùi: Ưu điểm: i) Phù hợp với bài toán đưa ra giả thuyết và liệu giả thuyết đó có đúng hay không? ii) Tập trung vào đích đã cho. Nó tạo ra một loạt câu hỏi chỉ liên quan đến vấn đề đang xét, thuận tiện đối với người dùng. iii) Khi suy diễn một điều gì từ thông tin đã biết , nó chỉ tìm trên một phần của cơ sở tri thức thích đáng đối với bài toán đang xét. iv) Suy diễn lùi được đánh giá cao trong các bài toán như là chẩn đoán, dự đoán và tìm lỗi. Nhược điểm: Nhược điểm cơ bản của loại suy diễn này là nó thường tiếp theo dòng suy diễn thay vì đúng ra phải dừng ở đó mà sang nhánh khác. - Như vậy, dựa vào các ưu và nhược điềm của từng loại suy diễn mà ta nên chọn kỹ thuật suy diễn nào để áp dụng vào bài toán. Trước tiên, ta xem xét các chuyên gia giải nó như thế nào?. Nếu cần thu thập dữ liệu rồi mới quyết định suy diễn cái gì thì ta chọn suy diễn tiến. còn nếu đã có giử thuyết và cần chứng minh cái đích này thì ta dùng suy diễn lùi. Ví dụ Một bác sĩ có thể hiểu hàng trăm vấn đề có thể xảy ra với một cá nhân, nhưng vẫn phải tìm hiểu hiện trạng của bệnh nhân, lúc đó cần suy diễn   159 tiến. Nguợc lại bác sĩ hầu như thấy được bệnh ( ví dụ như viêm họng) thì ông ta dùng suy diễn lùi. Bài tập 1. Cho các biểu thức logic mệnh đề đúng sau: 1) ac 2) ab f 3) (d +b)f  i 4) h + a + f 5) fgh  i 6) (a + d + c ) 7) ad  gh Chứng minh hoặc bác bỏ mệnh đề i bằng phương pháp suy diễn tiến và suy diễn lùi Lời giải - Biểu diễn các biểu thức đúng đã cho bằng luật sản xuất (xác định tập luật, tập sự kiện ban đầu, tập sự kiện cần chứng minh) Quá trình biến đổi 3) (d+b)f  i  ((d+b)f )+i (d+b)+f+i  (db)+f+i  (d+f+i)(b+f+i)  (df i )(bf i) 4) h + a + f  (ha)+f  ha  f 1) (a + d + c )  (ac)+d  ac  d 2) ad  gh )  (ad)+(gh) )  ((ad)+g) ((ad)+h)  (ad  g)(ad  h) Tập sự kiện F={a, c}, tập sự kiện cần chứng minh G={i} Tập luật R: r1) ab f r5) fgh  i r2) (df i ) r6) ac  d r3) (bf i ) r7) ad  g r4) ha  f r8) ad  h   160 - Suy diễn tiến (tiến hành lập bảng sau) r T S R r6 r7 r8 r4 r2 a, c a, c, d a, c, d, g a, c, d, g, h a, c, d, g, h, f a, c, d, g, h, f, i r6 r7, r8 r8 r4 r2, r5 r1, r2, r3, r4, r5, r6, r7, r8 r1,...r5, r7, r8 r1,...r5, r8 r1,...r5 r1, r2, r3,r5 (trong đó: r: là luật đang xét, T: tập sự kiện đúng tại thời điểm đang xét, S: tập các luật có dạng các mệnh đề ở vế trái thuộc T. R là tập luật tại thời điểm đang xét) Vì iT (là tập sự kiện đúng). Vậy i được chứng minh - Suy diễn lùi (tiến hành lập bảng sau) p r T S(p) i f b quay lui f h d r2 r1 r2 r8 r6 i d, f d, b d d, h d  r2, r3, r5 r1, r2  r2 r8 r6 Vậy i được chứng minh   161 Bài tập 2. Cho cơ sở tri thức được biểu diễn bằng các biểu thức logic đúng sau 1) pt  a 5) p  t 2) qt  s 6) apq  c 3) pq  b 7)bc  t 4) b st 8) pq Biểu diễn tri thức đã cho dưới dạng luật sản xuất và dùng phương pháp suy diễn tiến và suy diễn lùi để chứng minh hoặc bác bỏ sự kiện s1. Bài tập 3. Cho cơ sở tri thức được biểu diễn bằng các biểu thức logic đúng sau 1) (a+c)b  f 2) e +f + a 3) gfh  i 4) (e+ f)b  gi 5) (a+ e +c)abc Dùng phương pháp suy diễn tiến và suy diễn lùi để chứng minh hoặc bác bỏ sự kiện i1. Bài tập 4.. Cho cơ sở tri thức được biểu diễn bằng các biểu thức logic đúng sau 1) efh 2) a + g + d 3) h + c + d 4) af  bg 5) ke  d 6) (ef  a )(c+ e +f ) - Biểu diễn tri thức đã cho dưới dạng luật sản xuất - Dùng phương pháp suy diễn tiến để chứng minh sự kiện d1 đúng. Cho biết các luật dư thừa trong vết suy diễn   162 Bài tập 5.. Trong một lớp học, có một nhóm học sinh gồm 10 bạn có tên lần lượt là: A, B, C, D, E, F, G, H, I và J. Giữa các bạn học sinh đó có mối quan hệ gọi là quan hệ ảnh hưởng. Ví dụ: nếu ta viết AB>C thì có nghĩa là hai bạn đồng thời cùng thuyết phục bạn C tham gia một hoạt động nào đó. Giả sử ban đầu có bốn bạn E, F, H, I tham gia dự thi sản phẩm phần mềm do nhà trưòng tổ chức và ta cũng biết được rằng: 1) ACH>B 2) BH>ACD 3) ABCI>BDI 4) ADEI>BCG 5) CGI>AJE 6) H>BC Hãy dùng phương pháp suy diễn tiến để chứng minh rằng cả 10 bạn trong nhóm trên đều tham gia dự thi sản phẩm phần mềm.