Sưu tầm bởi: www.daihoc.com.vn
57
 p, q, r,  p  s   q,  s
B4 : 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
p,  p  q p, q  q
B5 : Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở ở cả hai phía.
Ví dụ :
p, q  q được chứng minh
p,  p  q  p p, q
B6 :
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.
VII.2 Thuật giải Robinson
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 :
GT
1
, GT
2

Ví dụ : &#p   q   r  s  q
Hai mệnh đề  q, q là đối ngẫu nên sẽ được loại bỏ
 p   r  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   q ,  r  s  q , w  r, s  q }
 { p   r  s , w  r, s  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  q,  q  r,  r  s,  u   s   p,  u
B3: {  p  q,  q  r,  r  s,  u   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  q   q  r   p  r
Danh sách mệnh đề thành :
{ p  r ,  r  s,  u   s, p, u }
Vẫn chưa có mệnh đề đối ngẫu.
Sưu tầm bởi: www.daihoc.com.vn
59
Tuyển hai cặp mệnh đề đầu tiên
 p  r   r  s   p  s
Danh sách mệnh đề thành { p  s,  u   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  s  u   s   p   u

60
Tùy vào các vấn đề đang quan tâm mà luật sinh có những ngữ nghĩa hay cấu tạo
khác nhau :
Trong logic vị từ : P
1
, P
2
, ..., Pn, Q là những biểu thức logic.
Trong ngôn ngữ lập trình, mỗi một luật sinh là một câu lệnh.
IF (P
1
AND P
2
AND .. AND Pn) THEN Q.
Trong lý thuyết hiểu ngôn ngữ tự nhiên, mỗi luật sinh là một phép dịch :
ONE  một.
TWO  hai.
JANUARY  tháng một
Để biễu diễn một tập luật sinh, người ta thường phải chỉ rõ hai thành phần chính sau
:
(1) Tập các sự kiện F(Facts)
F = { f
1
, f
2
, ... fn


R2 : B  D { A, B, D, E, H, K }
R6 : D  E  K  C { A, B, C, D, E, H, K }
Suy diễn lùi : là quá trình suy luận ngược xuất phát từ một số sự kiện ban đầu, ta
tìm kiếm các sự kiện đã "sinh" ra sự kiện này. Một ví dụ thường gặp trong thực tế là
xuất phát từ các tình trạng của máy tính, chẩn đoán xem máy tính đã bị hỏng hóc ở
đâu.
Ví dụ :
Tập các sự kiện :
• Ổ cứng là "hỏng" hay "hoạt động bình thường"
• Hỏng màn hình.
• Lỏng cáp màn hình.
• Tình trạng đèn ổ cứng là "tắt" hoặc "sáng"
• Có âm thanh đọc ổ cứng.
• Tình trạng đèn màn hình "xanh" hoặc "chớp đỏ"
• Không sử dụng được máy tính.
• Điện vào máy tính "có" hay "không"
Tập các luật :
R1. Nếu ( (ổ cứng "hỏng") hoặc (cáp màn hình "lỏng")) thì không sử dụng được máy
tính.
R2. Nếu (điện vào máy là "có") và ( (âm thanh đọc ổ cứng là "không") hoặc tình
trạng đèn ổ cứng là "tắt")) thì (ổ cứng "hỏng").
R3. Nếu (điện vào máy là "có") và (tình trạng đèn màn hình là "chớp đỏ") thì (cáp
màn hình "lỏng").
Để xác định được các nguyên nhân gây ra sự kiện "không sử dụng được máy tính", ta
phải xây dựng một cấu trúc đồ thị gọi là đồ thị AND/OR như sau :