Bài giảng Trí tuệ nhân tạo - Chương 3, Phần 1: Kỹ thuật giải quyết vấn đề - Lê Thanh Hương

1Chương 3 
Kỹ thuật giải quyết vấn đề
(tiếp)
Lê Thanh Hương
1
Khoa CNTT – ĐHBKHN
3.6 Biểu diễn bằng logic hình thức và 
các phương pháp chứng minh
VD1. Bài toán con khỉ - nải chuối
B đầ
• Tại(O,x): đối tượng O ở tại vị trí x
an u:
Muốn:
Hành động của khỉ:
• tại(A,x) ⇒ tại (A,y)
• tại(A,x) ∧ tại(O,x) ⇒ tại(A,y) ∧ tại(O,y)
tại(A,4) , tại(B,3) , tại(C,1), tại(D,2)
tại(B,2) , trên(C,B), trên(A,C), trên(D,A)
• Trên(O1,O2): đối tượng O1 nằm trên O2
21 2 3 4
C
D
B
A • tại(A,x) ∧ tại(O,x) ⇒ trên(A,O)• tại(A,x) ∧ tại(O1,x) ∧ tại(O2,x) ⇒
trên(O1,O2)
Logic mệnh đề (Propositional Logic)
• 1 mệnh đề p là 1 phát biểu chỉ có nhận giá trị đúng (true, 
T, 1) hoặc sai (false, F, 0)
• liên kết với nhau tạo thành câu
• Câu (well formed formulas – các công thức đúng ngữ 
pháp)
– T và F là câu
– Các biến mệnh đề là câu: P, Q, R, S
3
– Nếu φ và ψ là câu thì những biểu thức sau cũng là câu: 
(φ), ¬φ, φ∨ψ, φ∧ψ, φ→ψ, φ↔ψ
• Các biểu thức logic mệnh đề được xây dựng trên các tên 
mệnh đề và các phép toán logic theo quy tắc cú pháp 
nhất định
Các toán tử
• Hội (∧ and và) Ké th ( )
Các phép toán logic
 , , 
• Tuyển (∨, or, hoặc)
• Phủ định (¬,∼,not, không) 
A∨B∧C A∨(B∧C)
Thứ tự ưu tiên: ¬ ∧ ∨ → ↔
• o eo ⇒
• Tương đương (⇔)
4
A∧B→C∨D (A∧B)→(C∨D)
A→B∨C↔D (A→(B∨C))↔D
2Ngữ nghĩa
• Ý nghĩa của một câu là giá trị chân lý của nó {T,F}. Ví dụ
P1,2 P2,2 P3,1
false true false
Một số luật đánh giá giá trị chân lý: 
¬S đúng nếu S sai
S1 ∧ S2 đúng nếu S1 đúng và S2 đúng
ế
5
S1 ∨ S2 đúng n u S1 đúng hoặc S2 đúng
¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (true ∨ false) 
= true ∧ true = true
Bảng chân lý
• Giá trị chân lý của một biểu thức được tính dựa trên 
bảng chân lý
6
• Dễ thấy a⇒b ⇔ ¬a∨b ⇔ ¬b⇒¬a
• ∀biểu thức logic mệnh đề đều có thể đưa về dạng 
biểu thức tương đương chỉ chứa phép ∧,¬,∨
Các phép biến đổi tương đương
Hai câu có ý nghĩa tương đương nếu cùng giá trị đúng:
giao hoán 
kết hợp
phủ định kép
tương phản
7
de Morgan
phân phối
Các phép biến đổi tương đương
Luật hấp thu:
• (A ∨ (A ∧ B) ≡ A • (A ∧ (A ∨ B)) ≡ A
Các luật về 0, 1:
• A ∧ 0 ⇔ 0
• A ∨ 1 ⇔ 1 
• ¬1 ⇔ 0
• A ∨ 0 ⇔ A
• A ∧ 1 ⇔ A
• ¬0 ⇔ 1
Luật bài trung:
8
• ¬A ∨A ⇔ 1
Luật mâu thuẫn:
• ¬A ∧A ⇔ 0
3Hợp giải
• Luật hợp giải (Các câu cần được chuyển sang 
dạng kết nối chuẩn trước khi hợp giải)
βα ∨
¬β ∨ γ
α ∨ γ
• Chứng minh KL: thêm ¬KL vào CSTT để xem 
có xung đột không 
9
• Áp dụng hợp giải đến khi xuất hiện mâu 
thuẫn
Hợp giải
Dạng kết nối chuẩn (Conjunctive Normal Form - CNF)
E.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)
• Luật hợp giải cho CNF:
l1 ∨ ∨ lk, m1 ∨ ∨ mn
l1 ∨ ∨ li-1 ∨ li+1 ∨ ∨ lk ∨ m1 ∨ ∨ mj-1 ∨ mj+1 ∨... ∨
mn
trong đó l và m bù nhau
10
 i j 
E.g., P1,3 ∨ P2,2, ¬P2,2
P1,3
Chuyển đổi sang CNF
B1,1 ⇔ (P1,2 ∨ P2,1)
ằ1. Loại bỏ phép ⇔, thay α ⇔ β b ng (α ⇒ β)∧(β ⇒ α).
(B1,1⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1)
2. Loại bỏ phép ⇒, thay α ⇒ β bằng ¬α∨ β.
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬(P1,2 ∨ P2,1) ∨ B1,1)
3 Đưa vào trong sử dụng luật de Morgan và phủ định kép:
11
. ¬ 
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ ((¬P1,2 ∧ ¬P2,1) ∨ B1,1)
4. Áp dụng luật phân phối đối với phép ∧ :
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬P1,2 ∨ B1,1) ∧ (¬P2,1 ∨ B1,1)
Ví dụ
(A∨B)→(C→D)
1. Loại bỏ phép suy ra
¬(A∨B)∨(¬C∨D)
2. Chuyển phủ định vào trong ngoặc
( A B) ( C D)
12
¬ ∧¬ ∨ ¬ ∨
3. Phân phối
(¬A∨¬C∨D)∧(¬B∨¬C∨D)
4Ví dụ
Chuyển đổi các công thức sau về dạng kết nối 
chuẩn:
1. P ∨ (¬P ∧ Q ∧ R)
2. (¬P ∧ Q) ∨ (P ∧ ¬Q)
3. ¬(P ⇒ Q) ∨ (P ∨ Q)
4. (P ⇒ Q) ⇒ R
13
5. (P ⇒(Q ⇒ R)) ⇒ ((P ∧ S) ⇒ R)
6. (P ∧ (Q ⇒ R)) ⇒ S
7. P ∧ Q ⇒ R ∧ S
Thuật toán hợp giải của 
Robinson
Chứng minh bằng phản chứng: CSTT ∧¬KL không thoả 
mãn
14
Thuật toán hợp giải của Robinson
Chứng minh bằng phản chứng: CSTT ∧¬KL không thoả mãn
Giả sử có GT1, GT2,,GTn. Cần CM KL → phản chứng
GT1
 ><
GTn
¬KL
Viết mỗi GTi, ¬KL trên 1 dòng
Đưa GTi, ¬KL về dạng chuẩn CNF
( ) ( ) (*)
15
p1∨∨pn ∧ q1∨∨qn 
Tách mỗi dòng (*) thành các dòng con:
p1∨∨pn
q1∨∨qn
Thuật toán hợp giải của Robinson
Xét 1 cặp dòng
u) ¬p∨q
v) p∨r
Hợp giải:
w) q∨r
Vô lý xuất hiện khi
i) ¬t
16
ii) t
⇒ đpcm
5Ví dụ
VD1: VD2:
1. a
2. a→b
3. b→(c→d)
4. c
1. a∧b→c
2. b∧c →d
3. a
4. b
Chứng minh d
17
Chứng minh d
Ví dụ
VD3:
1. p
VD4:
1. ((a∨b)∧c)→(c∧d)
2. p→q
3. q∧r∧s→t
4. p→u
5. v→w
6 u→v
2. a∧m∧d→f
3. m→b∧c
4. a→c
5. (a∧f)→(¬e∨g)
6 (m∧f)→g
18
.
7. v→t
Cho r,s. CM t
.
Cho a,m. CM g
Ví dụ 5
1. a1 ∨ a2 ⇒ a3 ∨ a4
2. a1 ⇒ a5 
3. a2 ∧ a3 ⇒ a5
4. a2 ∧ a4 ⇒ a6 ∧ a7 
5. a5 ⇒ a7
6. a1 ∧ a3 ⇒ a6 ∨ a7 
ề
19
• Cho các mệnh đ a1, a2 đúng. 
• Đưa các biểu thức logic trên về dạng chuẩn 
• áp dụng phương pháp hợp giải của Robinson, chứng 
minh a7 đúng.
Logic vị từ cấp 1 
(First Order Logic – FOL)
• Logic mệnh đề chỉ xử lý thông tin kiểu sự kiện đúng hoặc sai 
như “trời mưa” .
• Với logic vị từ cấp 1, biến được dùng thay cho các đối tượng 
cụ thể.
• FOL cho phép biểu diễn các đối tượng, thuộc tính của đối 
tượng, và quan hệ giữa các đối tượng.
• Vị từ p(x,y) là một phát biểu chứa các biến x,y sao cho 
khi x,y nhận giá trị cụ thể thì p(x,y) nhận giá trị đúng hoặc 
sai
20
.
• VD. Nếu p(x,y,z) nghĩa là x.y = z thì tính chất giao hoán của 
phép nhân x.y = y.x được biểu diễn dưới dạng
∀x,y p(x,y,z) ⇒ p(y,x,z)
• Logic vị từ cấp 1 còn sử dụng thêm các toán tử ∃, ∀
6Chuyển đổi câu sang dạng logic vị từ
21
1. Loại bỏ dấu suy ra
α↔β⇒(α→β)∧(β→α)
Các phép biến đổi tương đương
α→β⇒¬α∨β
2. Chuyển phủ định vào trong ngoặc
¬(α∨β)⇒¬α∧¬β
¬(α∧β)⇒¬α∨¬β
¬¬α⇒α
∀x α⇒∃x α
22
¬ , ,¬
¬∃x,α⇒∀x,¬α
3. Đặt tên các biến khác nhau
∀x, ∃y,(¬P(x)∨∃x,Q(x,y))⇒∀x1,∃x2,(¬P(x1)∨∃x3,Q(x3,y2)
Phép gán trị
VD: Định lý đường trung bình:
r1: trđ(U XY) ∧ trđ(V XZ)⇒ ss(UV YZ) , , ,
X
U V
A
L I
23
Phép gán trị θ ={A/X,B/Z,D/Y,L/U,I/V}:
• r1θ: trđ(L,AD) ∧ trđ(I,AB) ⇒ ss(LI,DB)
Y Z D B
Hợp giải Robinson cho logic vị từ
1. Viết mỗi GTi, ¬KL trên 1 dòng
2. Đưa GTi, ¬KL về dạng chuẩn CNF
∀x1∀x2∀xn [p1()∨∨pn()] ∧ [q1()∨∨qm()] (*)
3 Tách mỗi dòng (*) thành các dòng con:. 
∀x1∀x2∀xn [p1()∨∨pn()]
∀x1∀x2∀xn [q1()∨∨qm()]
tất cả đều với ∀
4. Hợp giải:
u) ¬p(x1,x2,,xn) ∨ q() ⇒ w) q() ∨ r() với phép gán trị 
24
v) p(y1,y2,,yn) ∨ r()
5. Vô lý xảy ra khi
i) ¬p(x1,x2,,xn) 
ii) p(y1,y2,,yn)
với phép gán trị 
{ }
n
n
n
n
y
z
x
z
y
z
x
z ,,...,,
1
1
1
1=θ
{ }
n
n
n
n
y
z
x
z
y
z
x
z ,,...,,
1
1
1
1=θ
7Ví dụ về bước 4
• Sử dụng phép gán trị nào để hợp giải 
P(a,x,b), và 
¬P(y,z,z)
⎭⎬
⎫
⎩⎨
⎧
x
b
z
b
y
a ,,Phép gán trị θ = 
25
• P(a,b,b)
• ¬P(a,b,b)
Ví dụ về bước 4 (tiếp)
• Sử dụng phép gán trị nào để hợp giải 
P(a,x,x,b), và 
¬P(y,y,z,b)
26
Ví dụ về bước 4 (tiếp)
• Cho các sự kiện p(a,b), p(c,d), q(d,c,c) đúng
• Cho luật
p(x,y) ∧ q(y,x,x) ⇒ r(x,y)
• Sử dụng các phép gán trị với luật trên, hãy đưa ra các 
sự kiện mới đúng.
• Gợi ý: 
Thử ới ( ) ( b) h ặ ( ) ( d)
27
– v p x,y ≡ p a, o c p x,y ≡ p c,
Ví dụ về hợp giải
Hợp giải 1 và 3
)()(
)()(
RP
xQxPx
∀
→∀
)()(1 xQxP ∨
)()(.5 xSxP ∨¬
Hợp giải 2 và 5
)()(.6 xSxR ∨
Chuyển về dạng chuẩn
)()(
)()(
xSxRx
xSxQx
xxx
→∀
→∀
→¬
28
)()(.4
)()(.3
)()(.2
.
xSxR
xSxQ
xRxP
∨¬
∨¬
∨
¬
Hợp giải 4 và 6
)(.7 xS
8Bài toán con khỉ - nải chuối
• tại(C,1)
• tại(B,3)
• tại(A,4)
• tại(D,2)
• tại(A,x) ⇒ tại (A,y)
• tại(A,x) ∧ tại(O,x) ⇒ tại(A,y) ∧ tại(O,y)
tại(A x) tại(O x) trên(A O)
1 2 3 4
C
D
B
A
29
• , ∧ , ⇒ ,
• tại(A,x) ∧ tại(O1,x) ∧ tại(O2,x) ⇒ trên(O1,O2)
KL: tại(B,2) ∧ trên(C,B) ∧ trên(A,C) ∧ trên(D,A)
¬KL: ¬ tại(B,2) ∨ ¬ trên(C,B) ∨ ¬ trên(A,C) ∨ ¬ trên(D,A)
Bài tập
• Cho tập các phát biểu:
– John owns a dog
– Anyone who owns a dog is a lover of animals
– Lovers of animals do not kill animals
• Chứng minh:
– John does not kill animals.
30
Bài tập
• Nếu xem một ai đó lừa dối người khác là kẻ bịp bợm 
và bất kỳ ai đồng tình với kẻ bịp bợm cũng là kẻ bịp 
bợm. Trong tập thể có một người nhút nhát đồng tình 
với kẻ lừa dối thì chắc chắn có 1 tên bịp bợm tính 
tình nhút nhát.
31
Nhận xét
• Thuật giải Robinson vẫn vấp phải sự bùng nổ tổ hợp. 
Có thể áp dụng các heuristics:
– Chiến lược ưu tiên các biểu thức đơn
– Chiến lược đơn giản hóa các biểu thức
– Chiến lược giảm số lần hợp giải
– Chiến lược sắp thứ tự các hợp giải
– Chiến lược tập tựa
• Thuật giải Robinson được áp dụng trong CM định lý
32
tự động. 2 nhược điểm:
– con người không tư duy theo cách này
– chúng ta bị mất ngữ nghĩa và nội dung thông tin khi chuyển 
về dạng câu CNF
93.7 Một số phương pháp GQVĐ khác
• Phương pháp thử và sai (test & set)
• Phương pháp giải quyết bài toán tổng quát 
(General Problem Solving - GPS)
• Phương pháp thỏa mãn ràng buộc (Constraint 
S ti fi ti M th d)
33
a s ca on e o
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.7.1 Phương pháp thử và sai 
(test & set)
• Xuất phát từ n0 : Mở = {n0}; Đóng = ∅
ầ ố• Lan d n xu ng
• Bí quyết: tại mỗi thời điểm, chọn n ∈ Mở để xét:
• Mở = queue: d(n) min
• Mở = stack: d(n) ?
• TKCT: g(n) = c(n0,n) min
n0
34
• TKCT*: f(n) = g(n) + h(n) min
• Thử và sai: n ← get random(Mở)
Đích
Đóng (đã)
Γ(n)
n
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.7.2 Phương pháp GPS
Về lý thuyết tốt nhất, trên thực tế không tốt lắm
TKCT*: Lấy n ∈ Mở: f(n) = g(n) + h(n) min
GPS: 
• Với ∀n ∈ Mở, xác định sự khác biệt giữa n và Đích: 
Δ = {δ1, , δm}
• Chọn sự khác biệt quan trọng nhất δi.
• Chọn biện pháp Oj phù hợp để giảm sự khác biệt δj bằng cách:
– Xác định tập các phép biến đổi (toán tử) trong không gian 
O={O1, , On}
– Xây dựng ma trân M với các cột là các toán tử, các hàng là 
35
các sự khác biệt: 
M = (mij), i=1÷m, j = 1÷n
mij = 1 nếu Oj làm giảm δi
0 nếu ngược lại
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.7.3 Phương pháp thỏa mãn ràng buộc 
• Mục đích: Tìm các trạng thái bài toán sao cho thỏa mãn tập 
ràng buộc nào đó
• Quá trình tìm lời giải gồm 2 phần:
– Tìm kiếm trong KGBT các ràng buộc 
– Tìm kiếm trong KGBT ban đầu
Nội dung:
Thực hiện 1 → 5 cho đến khi tìm được lời giải đầy đủ hoặc khi tất cả 
các đường đều đã duyệt nhưng không cho kết quả.
1. Cho 1 đỉnh n ∈ MO
2. Áp dụng các luật suy dẫn với các ràng buộc vào đỉnh đã chọn để sinh 
ra tất cả các ràng buộc mới có thể có
3 Nế tập các ràng b ộc mới có mâ th ẫn thông báo đ ờng đi hiện
36
. u u u u → ư 
tại đi vào ngõ cụt
4. Nếu tập ràng buộc mô tả lời giải đầy đủ của bài toán → dừng, thông 
báo “thành công”. Ngược lại sang bước 5.
5. AD các luật trong KGTT, tạo các lời giải bộ phận phù hợp với tập các 
ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tìm 
kiếm.
Lê Thanh Hương – Khoa CNTT - ĐHBKHN