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