Bài giảng Trí tuệ nhân tạo - Chương 5: Sử dụng logic mệnh đề và vị từ - Nguyễn Văn Hòa

Chương 5: 
Sử dụng logic mệnh đề 
và vị từ
1
Biểu diễn tri thức nhờ logic vị từ 

 Tri thức được thể hiện dưới dạng lớp của các biểu thức 
logic và cơ sở tri thức giải bài toán được thiết lập trên cơ 
sở lớp của các biểu thức logic này.

 Luật suy diễn và thủ tục chứng minh tri thức được lập 
luận trên cơ sở toán học logic với các yêu cầu đặt ra của 
bài toán. 

 Với phương pháp biểu diễn này cung cấp ý tưởng để tiếp 
cận với ngôn ngữ lập trình Prolog trong lĩnh vực trí tuệ 
nhân tạo. 
2

 Biểu diễn tri thức nhờ logic vị từ còn được gọi là một 
ngôn ngữ biểu diễn dùng để mã hóa tri thức dưới dạng 
sao cho dễ lập trình với ngôn ngữ lập trình Prolog.
Nội dung

 Phép toán mệnh đề

 Biểu diễn sự kiện đơn giản

 Biểu diễn: isa và instance

 Các hàm và vị từ khả tính toán

 Luật phân giải

 Phân giải mệnh đề
3

 Đưa về clause form
Phép toán mệnh đề

 Mệnh đề: là các câu khẳng định về thế giới

 Mệnh đề có thể đúng (true) hoặc sai (false)

 Mệnh đề đơn giản: 
Đồng là một kim loại => Đúng
Gỗ là một kim loại => Sai
Hôm nay là thứ Hai => Sai

 Ký hiệu trong phép tính mệnh đề:
 Ký hiệu mệnh đề: P, Q, R, S,...
4
 Ký hiệu chân lý: true, false
 Các phép toán logic: ∧ (hội), ∨ (tuyển), ¬ (phủ định), 
⇒ (kéo theo) , = (tương đương)
Phép toán mệnh đề 

 Định nghĩa câu trong phép tính mệnh đề:
 Mỗi ký hiệu mệnh đề, ký hiệu chân lý là một câu
 Phủ định của một câu là một câu
 Hội, tuyển, kéo theo, tương đương của hai câu là một câu.

 Ký hiệu ( ), [ ] được dùng để nhóm các ký hiệu vào các 
biểu thức con.

 Một biểu thức mệnh đề được gọi là một câu (hay công 
thức dạng chuẩn- WFF:Well-Formed Formula) ⇔ nó có 
5
thể được tạo thành từ những ký hiệu hợp lệ thông qua một 
dãy các luật trên.
Ví dụ: ( (P∧Q) ⇒ R) = ¬P ∨ ¬Q ∨ R
Phép toán mệnh đề 

 Mệnh đề tương đương
 Dạng hấp thu 
 Dạng khác
A ∧ (A ∨ B) = A
A ∨ (A ∧ B) = A
A ∧ (¬A ∨ B)= A∧B
A ∨ (¬A ∧ B)= A∨B
 Dạng De Morgan
A ⇒ B = ¬A ∨ B
¬ (A ⇒ B) = A ∧ ¬B
A ⇒ B = A ∧ ¬B⇒ FALSE
6
¬ (A ∧ B) = ¬A ∨ ¬B
¬ (A ∨ B) = ¬A ∧ ¬B
Phép toán mệnh đề 

 Các luật suy diễn

 Luật Modus Ponens (MP)
A, A⇒ B ∴ B

 Luật Modus Tollens (MT)
A⇒ B, ¬B ∴ ¬A

 Luật Hội

 Luật Cộng
A ∴ AvB

 Luật tam đoạn luận tuyển
Av B, ¬A ∴ B

 Luật tam đoạn luận giả thiết
7
A,B ∴ A^B

 Luật đơn giản
A^B ∴ A
A⇒ B,B⇒ C∴ A⇒ C
Biểu diễn sự kiện đơn giản: VD1
8
Biểu diễn sự kiện đơn giản: VD2
9
Biểu diễn sự kiện đơn giản

 Sử dụng logic vị từ cấp 1 (PC)
 Ví dụ
10
Biểu diễn sự kiện đơn giản

 Suy diễn
11
Biểu diễn sự kiện đơn giản

 Biểu diễn vị từ cho các câu sau đây:
 Marcus was a man
 Macus was a Pompeian
 All Pompians were Romans
 Caesar was a ruler
 All Romans were either loyal to Caesar or hated hime
 Everyone is loyal to someone
12
 People only try to assassinate rulers they are not loyal 
to
 Marcus tried to assassinate Caesar
Biểu diễn: Isa và instance

 Biểu diễn instance: a1 là thanh viên của A
13
Biểu diễn: isa và instance

 5 câu đầu của ví dụ trên có thể biểu diễn:
 1. man(Marcus)
 2. Pompeian(Marcus)
 3. ∀X: Pompeian(X) → Roman(X)
 4. ruler(Caesar)
 5. ∀ X: Roman(X) → loyalto(X, Caesar) v hate(X, Caesar)
 Hoặc:
 1.instance(Marcus, man)
 2. instance(Marcus, Pompeian)
∀
14
 3. X: instance(X, Pompeian) → instance(X, Roman)
 4. instance(Caesar, ruler)
 5. ∀ X: instance(X, Roman) → loyalto(X, Caesar) v hate(X, 
Caesar)
Các hàm và vị từ khả tính toán

 Các trường hợp có thể khai báo được, như:
 tryassassinate(Marcus, Ceasar).
 loyalto(Marcus, Caesar)
 

 Trong trường hợp như quan hệ trên các số, như:
 1 < 2
 2 <3
7 >(3+2)
15

 → Không thể ghi đủ: lt(q,1), lt(2,3); 
 Gọi hàm để tính (3 + 2) → tính toán được gt(7,3+2) và trả về trị 
(true)
Các hàm và vị từ khả tính toán 

 Dùng hàm và vị từ tính toán được (VD):
 1. Marcus was a man.
man(Marcus)
 2. Marcus was a Pompeian.
Pompeian(Marcus)
 3. Marcus was born in 40 A.D
born(Marcus,40)
16
 4. All men are mortal.
∀ X: man(X) → mortal(X)
Các hàm và vị từ khả tính toán 

 Dùng hàm và vị từ tính toán được (VD)
 5. All Pompeian died when the vocano erupted in 79 AD.
erupted(vocano, 79) ^ ∀ X: [Pompeian(X) → died(X, 79)]
 6. No mortal lives longer then 150 years.
 ∀ X: ∀ T1: ∀ T2 : mortal(X) ^ born(X, T1) ^ gt(T2 – T1, 150) →
dead(X, T2)
 7. It is now 1991

 now = 1991

 Question:
Is Marcus alive ?
17


 Hay:
 alive(Marcus, now)

 OR: ¬alive(Marcus, now)
Các hàm và vị từ khả tính toán 

 Dùng hàm và vị từ tính toán được (VD):
 → Cơ sở tri thức không chứa mối quan hệ giữa alive và 
dead
 → Bổ sung:
 8. Alive means not dead.
∀ X: ∀ T: [alive(X,T) → ¬dead(X,T)] ^
[¬dead(X,T) → alive(X,T)]
9. Is someone dies, he is dead at all later times
18

∀ X: ∀ T1: ∀ T2: died(X,T1) ^ gt(T2, T1) → dead(X, 
T2)
Các hàm và vị từ khả tính toán 
19
Luật phân giải

 Thủ tục chứng minh chỉ dựa trên 1 phép toán – phân giải.

 Dạng chứng minh: phản chứng.

 Chứng minh P bằng cách giả thiết ¬P rồi cố gắng đưa ra 
mâu thuẩn.

 Yêu cầu: các biểu thức phải được chuẩn hoá trước ở dạng 
clause (clause form)

 Clause Form = clause ^ clause ^ clause ^ 

 Clause = term v term v term

 Ví dụ clause:
 P v ¬Q v R.
 ¬P v Q v ¬R
20
 ¬Roman(X) v hate(X, Ceaser)

 Luật phân giải:
 Mệnh đề
 Vị từ
Luật phân giải 

 Để chứng minh P từ tập F của các mệnh đề:
 1. Chuyển F sang clause form
 2. Lập ¬P, chuyển ¬P sang clause form. Thêm vào các 
clause ở bước 1
 3. Lặp đến khi gặp mâu thuẩn, hoặc không thể đi tiếp được 
nữa:

 1. Chọn 2 clauses ở dạng.
a v C1
¬a v C2
21
Với C1, C2 biểu thức con của 1 clause

 2. Thêm vào tập clauses dòng:
(C1 – a) v (C2 – ¬a )
Dấu “–” nghĩa là loại bỏ a khỏi C1 và ¬a khỏi C2
Luật phân giải: ví dụ
22
Luật phân giải: ví dụ

 Chứng minh
23
Luật phân giải: ví dụ

 Ví dụ: Chứng minh hình thức bằng luật phân giải cho 
đoạn văn sau đây: 
“ Nam hoặc là chuyên gia hoặc là người cá biệt. Nếu Nam 
là chuyên gia thì Nam có nhiều báo cáo có tiếng và được 
đồng nghiệp tin cậy. Nếu Nam có nhiều báo cáo có tiếng 
thì hộp thư của Nam có nhiều thư. Nếu Nam là người cá 
biệt thì Nam không được bạn bè tôn trọng. Quan sát thấy 
rằng, hộp thư của Nam không có nhiều thư “.
24
chứng mính: “Nam không được bạn bè tôn trọng.“
Luật phân giải: ví dụ 

 Các mệnh đề:
 P1 = “Nam là chuyên gia”
P2 = “Nam là người cá biệt”
 P3 = “Nam có nhiều báo cáo có tiếng”
 P4 = “Nam được đồng nghiệp tin cậy”
 P5 = “Hộp thư của Nam có nhiều thư”
 P6 = “Nam được bạn bè tôn trọng”

 Các câu:
1. (P1 ^ ¬P2) v (¬P1 ^ P2)
25
2. P1 → (P3 ^ P4)
3. P3 → P5
4. P2 → ¬P6
5. ¬P5
Luật phân giải: ví dụ 
26
Luật phân giải: ví dụ 

 Chứng minh
27
Đưa về claus form

 Câu sau được dùng làm ví dụ trong thủ tục đưa về 
clause form.
 “All Romans who know Marcus either hate Caesar 
or think that anyone who hates anyone is crazy”
 ∀ X: [roman(X) ^ know(X, Marcus)] →
[hate(X, Ceasar) v
(∀ Y: ∃ Z: hate(Y,Z) → thinkcrazy(X,Y))]
28
Đưa về claus form
1. Loại bỏ →
dùng tương đương: a→b = ¬a v b
 Ví dụ
 ∀ X: [roman(X) ^ know(X, Marcus)] →
[hate(X, Ceasar) v
(∀ Y: ∃ Z: hate(Y,Z) → thinkcrazy(X,Y))]
∀ X: ¬[roman(X) ^ know(X, Marcus)] v
29

[hate(X, Ceasar) v
(∀ Y: ∃ Z: hate(Y,Z) → thinkcrazy(X,Y))]
Đưa về claus form
2. Thu giảm tầm vực của ¬ vào đến mức term.
 Dùng tương đương:
¬(¬p) = p
De Morgan:
¬(a v b) = ¬a ^ ¬b
¬(a ^ b) = ¬a v ¬b
 Tương đương lượng từ:
¬ ∀ X: P(X) = ∃ X: P(X)
¬ ∃: P(X) = ∀ X: P(X)
Áp dung cho ví dụ trước
30


 ∀ X: [¬roman(X) v ¬know(X, Marcus)] v 
[hate(X,Ceasar) v 
(∀ Y: ∃ Z: ¬hate(Y,Z) v thinkcrazy(X,Y))]
Đưa về claus form
3. Chuẩn hoá các biến để các lượng từ chỉ ràng buộc 
1 biến duy nhất.
 Biến đổi như VD sau:
∀ X: P(X) v ∀ X: Q(X) = ∀ X: P(X) v ∀ Y: Q(Y)
4. Chuyển lượng từ về bên trái. Chú ý, không 
chuyển thứ tự của chúng
 Ví dụ: tiếp bước 2.
31
∀ X: ∀ Y: ∃ Z: [¬roman(X) v ¬know(X, Marcus)] v 
[hate(X, Ceasar) v 
(¬hate(Y,Z) v thinkcrazy(X,Y))]
Đưa về claus form

 5. Loại bỏ lượng từ tồn tại : Sử dụng hàm skolem
 Hàm skolem:
∀ X: ∀ Y: ∃ Z : P(X,Y,Z) = ∀ X: ∀ Y: P(X,Y,f(X,Y))
 Biến của lượng từ tồn tại được thay là hàm theo những biến 
của lượng từ với mọi trước nó

 Bỏ qua các lượng từ (với mọi) còn lại ở bước 5. xem như 
mọi biến đều bị tác động bởi lượng từ với mọi (∀ )
 Ví dụ: tiếp bước 4
32
[¬roman(X) v ¬know(X, Marcus)] v [hate(X, Ceasar) v 
(¬hate(Y,Z) v thinkcrazy(X,Y))]
Đưa về claus form
7. Chuyển hội chuẩn (Conjunctive Normal Form - CNF)
 Một chuỗi các mệnh đề kết nối nhau bằng quan hệ AND (^). 
Mỗi mệnh đề có dạng một tuyển OR (v) của các biến mệnh 
đề.
 Dùng phép phân phố giữa v và ^
 Dạng thường gặp:
(a ^ b) v c = (a v c) ^ (b v c)
(a ^ b) v (c ^ d) = (a v c) ^ (a v d) ^ (b v c) ^ (b v d)
33
 Ví dụ: tiếp bước 6
¬roman(X) v ¬know(X, Marcus) v
hate(X, Ceasar) v ¬hate(Y,Z) v thinkcrazy(X,Y)
Đưa về claus form
8. Tách riêng các clause trong CNF ở trên
 Nếu có clause form:
(a v ¬b) ^ (¬a v c v d) ^ (a v ¬c v e)
 Thì được tách riêng thành các clause:
1. (a v ¬b)
2. (¬a v c v d)
3. (a v ¬c v e)
34

 Đưa các lượng từ về từng clause
 (∀ X: P(X) ^ Q(X) ) = ∀ X: P(X) ^ ∀ X: Q(X)
Đưa về claus form

 BT: đưa về clause form các câu sau:
1. ∀X A(X) v ∃ X B(X) → ∀XC(X) ^ ∃X D(X)
2. ∀X (p(X) v q(X)) → ∀X p(X) v ∀X q(X)
3. ∃X p(X) ^ ∃X q(X) → ∃X(p(X) ^ q(X))
4. ∀X ∃Y p(X,Y) → ∀Y ∃X p(X,Y)
5. ∀ X (p(X, f(X)) → p(X,Y))
35