Logic mệnh đề, Logic vị từ cấp một trong Hệ chuyên gia

CHƯƠNG 2 Logic mệnh đề - Logic vị từ cấp một

NỘI DUNG

 Logic mệnh đề

◦ Cú pháp và ngữ nghĩa của Logic mệnh đề ◦ Dạng chuẩn tắc ◦ Luật suy diễn  Logic vị từ cấp một

◦ Cú pháp và ngữ nghĩa logic vị từ cấp một ◦ Chuẩn hoá các công thức ◦ Các luật suy diễn

Logic mệnh đề

Cú pháp

• Các ký hiệu ◦ Hằng logic: True, False. ◦ Các ký hiệu mệnh đề (biến mệnh đề): P, Q,... ◦ Các phép kết nối logic: ∧, ∨, , ⇒, ⇔. ◦ Các dấu mở ngoặc”(“ và đóng ngoặc ”)”. • Các quy tắc xây dựng các công thức ◦ Các biến mệnh đề là công thức. ◦ Nếu A và B là công thức thì (A∧B), (A∨B), (A),

(A⇒B), (A⇔B) là các công thức.

Cú pháp ◦ Các công thức là các ký hiệu mệnh đề được gọi là

các câu đơn hoặc câu phân tử.

◦ Các công thức không phải là câu đơn được gọi là

câu phức hợp.

◦ Nếu P là ký hiệu mệnh đề thì P và P được gọi là literal, P là literal dương, còn  P là literal âm. ◦ Câu phức hợp có dạng A1∨...∨Am gọi là câu tuyển

(clause), trong đó Ai là các literal.

Ngữ nghĩa Diễn giải (interpretation): sự kết hợp các kí hiệu

mệnh đề với các sự kiện trong thế giới thực

Ví dụ: diễn giải là một cách gán cho mỗi ký hiệu

mệnh đề một giá trị chân lý True hoặc False

Bảng chân lý của các kết nối logic

Ngữ nghĩa ◦ Một công thức được gọi là thoả được (satisfiable)

nếu nó đúng trong một diễn giải nào đó.

Ví dụ: (P∨ Q) ∧S là thoả được vì nó có giá trị

True trong diễn giải {P = True, Q=False, S=False}.

◦ Một công thức được gọi là vững chắc (valid) nếu

nó đúng trong mọi diễn giải Ví dụ: P∨P là vững chắc

◦ Một công thức được gọi là không thoả được, nếu

nó là sai trong mọi diễn giải

Ví dụ: P∧P là không thỏa được

Ngữ nghĩa Mô hình (model) của một công thức là một diễn giải sao cho công thức là đúng trong diễn giải này.

Như vậy một công thức thoả được là công thức có

một mô hình.

Các công thức tương đương

AB  AB AB  (AB)(BA) (A)  A

De Morgan

(AB)  A B ; (AB) AB

Giao hoán

AB  BA; AB  BA

Kết hợp

(AB)  C  A  (BC); (AB)  C  A  (BC)

Phân phối

A  (BC)  (AB)  (AC); A  (BC)  (AB)  (AC)

Dạng chuẩn hội

 Câu tuyển: A1...Am (Ai : literal)  Dạng chuẩn hội: hội của các câu tuyển  Biến đổi về dạng chuẩn hội:

◦ Bỏ dấu : thay (AB) bởi AB ◦ Chuyển các dấu  vào sát các ký hiệu mệnh đề:

áp dụng De Morgan (thay (A) bởi A)

◦ Chuyển A(BC) về dạng (AB)(AC): áp

dụng luật phân phối

Ví dụ: chuẩn hoá công thức (PQ)(RS) về dạng (PQR)(PQS)

Câu Horn

Câu tuyển có dạng:

P1...Pm  Q1...Qn

(Pi, Qi :literal dương)

tương đương với:

P1...Pm  Q1... Qn

Nếu n1câu này trở thành câu Horn Khi m>0, n=1, câu Horn có dạng:

P1...Pm  Q

Câu Horn dạng này gọi là luật if-then:

If P1 and ... and Pm then Q

Khi m=0, n=1, câu Horn trở thành câu đơn Q (sự kiện

Luật suy diễn

H là hệ quả logic của tập G={G1, ..., Gm} nếu trong mọi thể

hiện mà G đúng thì H cũng đúng

Modus Ponens α  , α  Modus Tollens α  ,  α

Bắc cầu

α  ,    α  

Loại bỏ hội

α1... αi ... αm αi

Luật suy diễn

Đưa vào hội

α1,...,αi, ...,αm α1... αi ... αm

Đưa vào tuyển

αi

α1...αi...αm

Phân giải

α  ,   α  

Ví dụ

Giả sử có các công thức sau:

 A  B  C  D

(1)

 E  A

(2)

 F  B

(3)

 E

(4)

 F

(5)

Giả sử cần chứng minh C?

Tiên đề: Các công thức đã cho

Định lý: các công thức được suy ra

Chứng minh: dãy các luật được áp dụng để dẫn tới định lý

Định lý phân giải

- Câu phân giải được: Nếu có thể áp dụng luật phân giải cho các

câu đó

- Giải thức: Kết quả nhận được khi áp dụng luật phân giải cho các

câu

- Câu rỗng: giải thức của hai câu đối lập nhau P và P, ký hiệu □ - G là tập các câu tuyển, R(G) là tập câu bao gồm các câu thuộc G

và tất cả các câu nhận được từ G bằng một dãy áp dụng luật phân giải.

Định lý phân giải: Một tập câu tuyển là không thỏa được nếu và chỉ nếu câu rỗng

□R(G)

Một tập luật suy diễn là đầy đủ nếu mọi hệ quả logic của một tập

các tiên đề đều chứng minh được bằng cách chỉ sử dụng các luật của tập đó

Thủ tục phân giải

Procedure Resolution;

Input: G={các câu tuyển};

Begin

1. Repeat

1.1 Chọn hai câu A, B G;

1.2 If A và B phân giải được then tính Res(A,B);

1.3 If Res(A,B) là câu mới then thêm Res(A,B) vào G;

Until nhận được câu rỗng hoặc không có câu mới nào xuất hiện;

2. If nhận được câu rỗng then thông báo G không thỏa được

else thông báo thỏa được;

End;

Thủ tục phân giải



Sử dụng luật phân giải ta có thể chứng minh được một công thức bất kì có là hệ quả của một tập công thức đã cho hay không bằng phương pháp chứng minh bác bỏ.

 Vì vậy luật phân giải được xem là luật đầy đủ

cho bác bỏ.

Chứng minh bác bỏ

Ví dụ: Giả giử G là tập hợp các câu tuyển sau

(1)

 A ∨  B ∨ P  C ∨  D ∨ P  E ∨ C A E D

(2) (3) (4) (5) (6)

Giả sử ta cần chứng minh P. Thêm vào G câu sau:

 P

(7)

áp dụng luật phân giải cho câu (2) và (7) ta được câu:

(8)

C ∨ D

Từ câu (6) và (8) ta nhận được câu:

C

(9)

Từ câu (3) và (9) ta nhận được câu: (10)

 E

Từ câu (5) và (10) ta nhận được câu rỗng Vậy P là hệ quả logic của các câu (1) --(6).

Logic vị từ cấp 1

Cú pháp



Các ký hiệu:

◦ Hằng: a, b, c,…

◦ Biến: x, y, z,…

◦ Vị từ: P, Q, R, …

 Vị từ n biến p(x1, …, xn)  Vị từ không biến là mệnh đề

◦ Hàm: f, g, … f(x1, …, xn) - hàm n biến ◦ Liên kết logic: , , , , 

◦ Lượng từ: , 

◦ Dấu phảy, đóng mở ngoặc

Cú pháp



Các hạng thức:

◦ Các ký hiệu hằng và biến

◦ Nếu t1, …, tn là các hạng thức, f là hàm n biến,

thì



f(t1, …, tn) là hạng thức Công thức phân tử (câu đơn):

◦ Các vị từ không biến (mệnh đề)

◦ Nếu t1, …, tn là các hạng thức, P là vị từ n biến,

thì P(t1, …, tn) là công thức phân tử

Cú pháp



Công thức:

◦

Các công thức phân tử là công thức

◦

Nếu P, Q là các công thức thì PQ, PQ, P, PQ, PQ là các công thức

◦

Nếu P là công thức, x là biến thì xP, xP là các công thức.

◦

Literal: công thức phân tử hoặc phủ định của công thức phân tử

◦

Công thức đóng: công thức mà tất cả các biến đều là biến bị buộc

◦

Biến bị buộc x nếu trong công thức có dạng xP hoặc xP, còn lại là biến tự do

Ví dụ: x P(x, f(x,y))  x Q(x)

Ngữ nghĩa



Trong một diễn giải:

◦ ◦



Hằng → đối tượng cụ thể Hàm → hàm cụ thể Ngữ nghĩa của các câu đơn Ví dụ: Sinhviên(Lan) Ngữ nghĩa các câu phức

◦

Ví dụ: Sinhviên(Lan)  Thích(Lan, Bóngđá)



Ngữ nghĩa các câu chứa lượng từ

◦

xP : ngữ nghĩa của công thức là hội của tất cả các công thức nhận được từ P bằng cách thay x bởi một đối tượng trong miền xP: ngữ nghĩa của công thức là tuyển của tất cả các công thức nhận được từ P bằng cách thay x bởi một đối tượng trong miền