CHƯƠNG 6 – CÁC PHƯƠNG PHÁP LẬP LUẬN TRÊN LOGIC MỆNH ĐỀ

4. Câu dạng chuẩn hội và luật phân giải

¾ Câu dạng chuẩn hội là câu hội của các câu tuyển (clause). Như trên đã nói, câu tuyển là câu dạng A1 ∨ A2 ∨…∨An, trong đó các Ai là các ký hiệu mệnh đề hoặc phủ định của ký hiệu mệnh đề. Vậy câu dạng chuẩn hội có dạng: (A

11

∨ A

12

∨…∨A

1n

) ∧ (A

21

∨ A

22

∨…∨A

2m

) ∧ …∧ (A

k1

∨ A

k2

∨…∨A

kr

) clause clause clause Với A

ij

là các literal (là ký hiệu mệnh đề hoặc phủ định của ký hiệu mệnh đề). ¾ Với một câu bất kỳ trong logic mệnh đề, liệu có thể biểu diễn dưới dạng chuẩn hội như trên được không? Câu trả lời là có. Với câu s, chúng ta liệt kê tất cả các ký hiệu mệnh đề xuất hiện trong nó, lập bảng giá trị chân lý để đánh giá s, khi đó s là hội các tuyển mà mỗi tuyển sẽ tương ứng với dòng làm cho s bằng true false. Với mỗi tuyển (tương ứng với một dòng), nếu cột của ký hiệu mệnh đề trên dòng đó có giá trị true thì ký hiệu mệnh đề sẽ là literal dương âm, còn nếu giá trị là false thì ký hiệu mệnh đề sẽ là literal âm dương trong câu tuyển. Ví dụ, chúng ta muốn biết dạng chuẩn hội của câu sau: ¬C ⇒ A∧B Trong câu trên, có 3 ký hiệu mệnh đề là A, B, C. Ta lập bảng giá trị chân lý và chuyển sang dạng chuẩn hội như bảng sau:

Dạng chuẩn hội:

A B C ¬C ⇒ A∧B

Clause

¬C ⇒ A∧B

F F F F

A∨B∨C

= (A∨B∨C)

∧

(A∨¬B∨C)

∧

(¬A∨B∨C)

F F T T

F T F F

A∨¬B∨C

F T T T

T F F F

¬A∨B∨C

T F T T

T T F T

T T T T

¾ Với cách chuyển một câu sang dạng chuẩn hội như dung bảng giá trị chân lý ở trên, chúng ta khẳng định bất kỳ câu nào cũng có thể chuyển sang dạng chuẩn hội được. Ngoài phương pháp sử dụng bảng chân lý, chúng ta có thể áp dụng 4 qui tắc sau đây (theo thứ tự được liệt kê) để chuyển bất kỳ câu nào sang dạng chuẩn hội được. 9 QT1: Loại bỏ ⇔: thay thế α ⇔ β bằng (α ⇒ β)∧(β ⇒ α). 9 QT2: Loại bỏ ⇒: Thay thế α ⇒ β bằng ¬α ∨ β 9 QT3: chuyển hoặc loại bỏ dấu ¬ đặt trước các ký hiệu bằng các luật deMorgan và luật phủ định kép ¬(α∨β)= ¬α ∧ ¬β; ¬(α∧β)= ¬α ∨ ¬β; ¬¬α= α. 9 QT4: Áp dụng luật phân phối của phép ∧ đối với phép ∨ Chẳng hạn, chúng ta cần chuyển câu trong ví dụ trên sang dạng chuẩn hội, bằng cách áp dụng lần lượt các qui tắc trên: ¬C ⇒ A∧B = ¬(¬C) ∨ (A∧B) (QT2) = C ∨ (A∧B) (QT3) = (C∨A) ∧ (C ∨ B) (QT4) Chúng ta có thể dừng lại dạng chuẩn hội này, hoặc cũng có thể chứng minh tiếp rằng công thức này và công thức thu được từ phương pháp lập bảng ở trên là tương đương. ¾ Luật phân giải (resolution): 9 Luật phân giải: Nếu chúng ta có hai clause sau là đúng: (P

1

∨ P

₂

∨… P

_i

∨…∨P

_n

) ∧ (Q

1

∨ Q

2

∨… Q

j

∨…∨Q

m

) và P

i

,Q

j

là các literal phủ định của nhau (P

i

=¬Q

j

) thì chúng ta cũng có clause sau là đúng (P

1

∨ P

2

∨… P

i-1

∨ P

i+1

∨…∨P

n

∨Q

1

∨ Q

2

∨… Q

j-1

∨ Q

j+1

∨…∨Q

m

) (Clause mới là tuyển các literal trong hai clause ban đầu nhưng bỏ đi P

i

và Q

j

)9 Kết quả của phép phân giải cũng là một clause (tuyển các literal), hay nói cách khác phép phân giải có tính đóng, phân giải của các clause là một clause. Đây là tính chất rất quan trong trong việc xây dựng giải thuật suy diễn tự động trình bày phía dưới. ¾ Câu dạng chuẩn tuyển (tham khảo thêm): Câu dạng chuẩn tuyển là câu tuyển của các hội. Giống như cấu trúc của câu dạng chuẩn hội, câu dạng chuẩn tuyển cũng có cấu trúc như vậy, nhưng chúng ta đổi chỗ dấu ∨ bởi dấu ∧ và ngược lại. Với bất kỳ một câu trong logic mệnh đề, chúng ta cũng có thể biểu diễn nó dưới dạng chuẩn tuyển. Tuy nhiên chúng ta không có luật đóng liên quan đến tuyển của hai câu hội để sinh ra câu hội mới như luật phân giải của hai câu tuyển.