Trí tuệ nhân tạo

VII.2 Thuật giải Robinson

(quy uoc: v:tuyển,
^:hội
! :phủ định )
Thuật giải này 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
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.
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 được xây dựng từ các biến mệnh đề và các phép toán : ^ , v , !
B2 : Nếu GTi có phép ^ thì thay bằng dấu ","
Nếu KLi có phép v thì thay bằng dấu ","
B3 : Biến đổi dòng chuẩn ở B1 về thành danh sách mệnh đề như sau :
{ GT1, GT2, ..., GTn , ! KL1, ! KL2, ..., ! KLm }
B4 : Nếu trong danh sách mệnh đề ở bước 2 có 2 mệnh đề đối ngẫu nhau thì bài toán được chứng minh. Ngược lại thì chuyển sang B4. (a và ! a gọi là hai mệnh đề đối ngẫu nhau)
B5 : Xây dựng một mệnh đề mới bằng cách tuyển một cặp mệnh đề trong danh sách mệnh đề ở bước 2. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu nhau thì các biến đó được loại bỏ.
Ví dụ : &#p v ! q v ! r v s v q
Hai mệnh đề ! q, q là đối ngẫu nên sẽ được loại bỏ
==>p v !r v s
B6 : Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng mệnh đề mới.
Ví dụ :
{ p v !q , !r v s v q , w v r, s v q }
==> { p v !r v s , w v r, s v q }
B7 : Nếu không xây dựng được thêm một mệnh đề mới nào và trong danh sách mệnh đề không có 2 mệnh đề nào đối ngẫu nhau thì vấn đề không được chứng minh.

Ví dụ : Chứng minh rằng
==> p v q, ! q v r, ! r v s, ! u v ! s --> ! p, ! u
B3: { ! p v q, ! q v r, ! r v s, ! u v ! s, p, u }
B4 : Có tất cả 6 mệnh đề nhưng chưa có mệnh đề nào đối ngẫu nhau.
B5 : ==>tuyển một cặp mệnh đề (chọn hai mệnh đề có biến đối ngẫu). Chọn hai mệnh đề đầu :
! p v q v ! q v r ==> ! p v r
Danh sách mệnh đề thành :
{! p v r , ! r v s, !u v !s, p, u }
Vẫn chưa có mệnh đề đối ngẫu.
Tuyển hai cặp mệnh đề đầu tiên
!p v r v ! r v s ==> !p v s
Danh sách mệnh đề thành {! p v s, ! u v !s, p, u }
Vẫn chưa có hai mệnh đề đối ngẫu
Tuyển hai cặp mệnh đề đầu tiên
! p v s v !u v !s ==> !p v !u
Danh sách mệnh đề thành : {! p v !u, p, u }
Vẫn chưa có hai mệnh đề đối ngẫu
Tuyển hai cặp mệnh đề :
!p v !u v u ==> ! p
Danh sách mệnh đề trở thành : {!p, p }
Có hai mệnh đề đối ngẫu nên biểu thức ban đầu đã được chứng minh.

lớp mình có tài liệu gì gửi lên anh em học với