1.Thuật giải Robinson

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 mệnh đề được xây dựng từ các biến mệnh đề và 3 phép nối cơ bản : ∧ (dấu tuyển), ∨ (dấu hội) , ¬ (dấu bù)

B2 : Nếu GTi có phép ∧, KLi có phép ∨ thì thay thế bằng dấu “,”

B3:(Khử dấu →) 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ỏ.

B6 : Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng mệnh đề mới.

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.

2.Một số công thức cần nhớ

5

6

7

8

3.Bài tập giải thuật Robinson (Xem bài viết)

NGUYỄN THỊ YẾN NHI

nguyennhipuka@gmail.com

Advertisements