B9 - Hop giai menh de mon hoc logic cua thay nghiem

use it

1. HỢP GIẢI MỆNH ĐỀ Proposional Resolution SGU - Phạm Đình Nghiệm

2. HỢP GIẢI MỆNH ĐỀ Propositional Resolution Là phương pháp chứng minh tự động Người sáng tạo: Robinson Là cơ sở của lập trình logic SGU - Phạm Đình Nghiệm

3. Công thức dạng tuyển Đơn tử: p, q, r, p, q, … Dạng tuyển: Tuyển của các đơn tử A 1  A 2  …  A n Ở đây: n  N, A i là đơn tử Ví dụ   n = 0 p n = 1 p  q n = 2  p  q  r n = 3 SGU - Phạm Đình Nghiệm

4. Quy trình INDO I – Implication Out A  B   A  B A  B  ( A  B) & ( B  A ) N – Negation In   A  A  (A  B)   A &  B  (A & B)   A   B SGU - Phạm Đình Nghiệm

5. Quy trình INDO D – Dijunction In A  (B & C)  (A  B) & (A  C) (B & C)  A  (A  B) & (A  C) A  (B  C)  (A  B)  C A & (B & C)  (A & B) & C O – Operator Out A & B  A, B SGU - Phạm Đình Nghiệm

6. Quy trình INDO: Ví dụ (p  q)  r I:  (p  q)  r N: (  p &  q)  r D: (  p  r) & (  q  r) O:  p  r ,  q  r SGU - Phạm Đình Nghiệm

7. Quy tắc hợp giải R Tổng quát Ví dụ p  q  r  q  s p  r  s SGU - Phạm Đình Nghiệm

8. Quy tắc hợp giải R Đặc biệt: Trường hợp 1 Ví dụ p  q  r  q  r  s p  r  s SGU - Phạm Đình Nghiệm

9. Quy tắc hợp giải R Đặc biệt: Trường hợp 2 Ví dụ p  p   SGU - Phạm Đình Nghiệm  

10. Quy tắc hợp giải R: Cảnh báo ! p  q  p   q  Không được triệt tiêu hơn một cặp đơn tử ! SGU - Phạm Đình Nghiệm 

11. Phương pháp hợp giải  A 1 , A 2 , …, A n  → B X =  A 1 , A 2 , …, A n ,  B  X mâu thuẫn  Rút ra B X không mâu thuẫn  Không rút ra B Vấn đề: Làm sao biết X mâu thuẫn hay không? SGU - Phạm Đình Nghiệm

12. Làm sao biết X mâu thuẫn hay không? Áp dụng R vào X, kết quả thêm vào X đến khi Xuất hiện  : X mâu thuẫn Không áp dụng được R : X không mâu thuẫn Áp dụng được R, nhưng X không đổi : X không mâu thuẫn SGU - Phạm Đình Nghiệm 

13. Ví dụ thành công  p  q  r,  p  s,  r  s,  q  s  → s ? X =  p  q  r,  p  s,  r  s,  q  s,  s  p  q  r  p  s q  r  s  r  s q  s  q  s s  s   r  s SGU - Phạm Đình Nghiệm 

14. Ví dụ thành công  p  q  r,  p  s,  r  s,  q  s  → s ? X =  p  q  r,  p  s,  r  s,  q  s,  s  p  q  r  p  s q  r  s  r  s q  s  q  s s  s  SGU - Phạm Đình Nghiệm 

15. Ví dụ thất bại 1 Xét {p  q, q  s  r, r  p}   s X = {p  q, q  s  r, r  p, s} Không áp dụng được R vào X ! FAIL SGU - Phạm Đình Nghiệm

16. Ví dụ thất bại 2   p  q,  r  p  s  → s ? X =   p  q,  r  p  s,  s   p  q  r  p  s q   r  s q   r  s  r  p  s  r  q  p  q X không đổi nữa SGU - Phạm Đình Nghiệm

17. Hợp giải tuyến tính Linner Resolution Khởi đầu từ phủ định kết luận hoặc một phần của nó Tiếp tục với kết quả đã đạt được SGU - Phạm Đình Nghiệm

18. Ví dụ hợp giải tuyến tính  p  q  r,  p  s,  r  s,  q  s  → s ? X =  p  q  r,  p  s,  r  s,  q  s,  s   s  p  s  p  r  s q  r  q  s r  s  s  p  q  r s SGU - Phạm Đình Nghiệm 

19. Tìm theo chiều sâu Quay lui một bước Tìm dứt điểm từng nhánh SGU - Phạm Đình Nghiệm

20. Giản lược tiền đề một chiều Đơn tử một chiều Tập tiền đề X p xuất hiện trong X p không xuất hiện trong X Tiền đề một chiều = Tiền đề chứa đơn tử một chiều Giản lược, phản ứng dây chuyền p là đơn tử một chiều trong X SGU - Phạm Đình Nghiệm

21. Tiền đề một chiều Xét {p  q, q   s  r, p,  p   r, s  u,  q}  s X = {p  q, q   s  r, p,  p   r, s  u ,  q,  s } u là đơn tử một chiều .  s  u là tiền đề một chiều Giản lược. X1 = {p  q, q   s  r , p,  p   r,  q,  s } X2 = {p  q, p,  p   r ,  q} X3 = { p  q , p ,  q} X4 = {  q} X5 = {} Vậy không được kết quả. SGU - Phạm Đình Nghiệm

22. Tiền đề yếu A  X, B  X, A chứa B  A là tiền đề yếu Ví dụ: X = {p  q, q  s  r , r  p,  p   r, s  u, q  r } Trong X tiền đề q  s  r yếu , vì chứa tiền đề q  r . Tiền đề yếu không cần thiết SGU - Phạm Đình Nghiệm

23. Giản lược tiền đề quy luật Tiền đề quy luật chứa cặp đơn tử trái ngược nhau Ví dụ: X = {r  p,  p   r  p , s  u, q  r} p   r  p là tiền đề quy luật , vì chứa cả p và  p Tiền đề quy luật không cần thiết , có thể lược bỏ. SGU - Phạm Đình Nghiệm

24. Ví dụ l ược bỏ t iền đề quy luật Xét tập hợp X = {p   q,  s  q  s  r , r  p,  s   r,  s   p } Trong X , tiền đề  s  q  s  r là quy luật . Loại bỏ t iền đề quy luật này, được X = { p   q , r  p,  s   r ,  s   p }  q và  s là đơn tử một chiều, nên p   q ,  s   r , và  s   p thành tiền đề một chiều, vậy loại bỏ, được: X = { r  p } r  p thành tiền đề một chiều, vậy loại bỏ, được: X = { } SGU - Phạm Đình Nghiệm

25. Ví dụ : Suy luận sau đúng không? Nếu anh ấy biết lập chương trình cho máy tính và giỏi về toán quy hoạch thì anh ấy có thể giải quyết vấn đề kinh doanh này. Anh ấy không thể giải quyết được vấn đề kinh doanh này. Vậy suy ra rằng anh ấy hoặc là không biết lập chương trình cho máy tính, hoặc là không giỏi về toán quy hoạch SGU - Phạm Đình Nghiệm

26. Ví dụ Nếu anh ấy biết lập trình và giỏi về toán thì gq được vđ (p & q)  r Anh ấy không gq được vđ .  r ------------------------------------------------------------ ----- Anh ấy không biết lập trình, hoặc là a nh ấy không giỏi toán  p  q SGU - Phạm Đình Nghiệm

27. Ví dụ Chuyển thành xét: {(p & q)  r ,  r } → (  p  q ) Tạo tập X: {(p & q)  r ,  r ,  (  p  q )} SGU - Phạm Đình Nghiệm

28. Ví dụ Áp dụng INDO cho các tiền đề: (p & q)  r I:  ( p & q)  r N: (  p   q)  r D, O:  p   q  r  (  p  q ) N: p & q O: p, q SGU - Phạm Đình Nghiệm

29. Hợp giải X trở thành: {  p   q  r ,  r , p, q } Kết luận: Suy luận đã cho đúng. SGU - Phạm Đình Nghiệm p  p   q  r  q  r  r  q q 

30. Ví dụ khác Xét : {(p & q)   r ,  r } → (  p  q ) Tạo tập X: {(p & q)   r ,  r ,  (  p  q )} SGU - Phạm Đình Nghiệm

31. Ví dụ khác Áp dụng INDO cho các tiền đề: (p & q)  r I:  ( p & q)   r N: (  p   q)   r D, O:  p   q   r  (  p  q ) N: p & q O: p, q SGU - Phạm Đình Nghiệm

32. Ví dụ khác Ta có: X = {  p   q   r ,  r , p, q }  r là đơn tử 1 chiều, g iản lược tiền đề 1 chiều : X = { p, q } p , q là đơn tử 1 chiều, g iản lược tiền đề 1 chiều : X = { } Kết luận: Suy luận đã cho sai. SGU - Phạm Đình Nghiệm