KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

ĐỒ ÁN TRÍ TUỆ NHÂN TẠO
BÀI TẬP CHƯƠNG III:

CÁC PHƯƠNG PHÁP BIỂU
DIỄN VÀ XỬ LÝ TRI THỨC

Nhóm 3
GVHD: Th.S: Huỳnh Minh Trí

GVHD:Th.S: Huỳnh Minh Trí

Page 1


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

A. THUẬT GIẢI VƯƠNG HẠO
a)

Ý tưởng
Áp dụng chiến lược “chia để trị” nhằm tách bài toán xuất phát thành các
bài toán con dạng ”và” đơn giản hơn. Bài toán ban đầu sẽ được chứng
minh khi và chỉ khi mọi bài toán con sơ cấp được chứng minh.

b)

Các bước chứng minh bài toán bằng thuật giải Vương Hạo.
Bước 1: Ta đưa VT và VP cùa bài toán cần chứng minh về dạng chuẩn
bằng cách:


GT1, GT2, a , b, GT3,….,, GTn-1, GTn → KL1, c , d , KL2,…, KLm1, KLm.

Bước 4: Nếu dòng hiện hành có một trong hai dạng sau:
Dạng 1:
GT1, GT2,…,a  b,…, GTn-1, GTn → KL1, KL2,…., KLm-1, KLm
Thì thay bằng hai dòng:
GT1, GT2,…, a,…, GTn-1, GTn → KL1, KL2,…., KLm-1, KLm
GT1, GT2,…, b,…, GTn-1, GTn → KL1, KL2,…., KLm-1, KLm
Dạng 2:
GT1, GT2,…, GTn-1, GTn → KL1, KL2,…,a ∧ b,…, KLm-1, KLm
Thì thay bằng hai dòng:
GT1, GT2,…., GTn-1, GTn → KL1, KL2,…,a,…, KLm-1, KLm
GT1, GT2,…., GTn-1, GTn → KL1, KL2,…,b,…, KLm-1, KLm
- Chúng ta có thể tách cùng lúc nhiều nhóm mệnh đề với nhau, nhưng
cách hay nhất là nên chọn một nhóm mệnh đề mà thấy khi tách dòng có
mệnh đề trong nhóm mệnh đề đó ở gt giống mệnh đề ở kl. Như vậy ta sẽ
giảm được số dòng tách tiết kiệm thời gian.

Bước 5: Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở
cả hai vế.

Ví dụ: a ∧ b, c → c (được chứng minh)
Bước 6:
6.a. Một vấn đề được giải quyết trọn vẹn nếu mọi dòng dẫn xuất
biểu diễn ở dạng chuẩn được chứng minh.
6.b. Nếu một dòng không còn dấu liên kết ∧,  và cả hai vế
không có chung mệnh đề nào thì dòng đó không được chứng minh.
Ví dụ: a ∧ b, c → d.
Chú ý: Từ bước 2 - 4 không cần làm theo thứ tự.


Có thể sử dụng mệnh đề này ở bất kỳ bước nào (từ 1-4).

Áp dung luật phân phối (nếu chưa gặp dạng chuẩn cần tìm) phép tuyển đối
với phép hội (hay phép hội đối với phép tuyển).

I.

Ví dụ: p

(q

u) ≡ (p q)

(p u).

p

(q

u) ≡ (p

(p u).

q)

BÀI TẬP THUẬT GIẢI VƯƠNG HẠO.

Bài 1: Cho {(A∧ B) →C, (B∧C) →D, (A∧B)}. Hỏi D ?
Bước 1) Ta đưa VT và VP cùa bài toán cần chứng minh về dạng chuẩn bằng cách:

với bài toán ban đầu.
CM (1).
B2) Chuyển vế này sang vế kia mệnh đề phủ định.
{┐B┐CD, A, B }→ D, A (CM)
CM (2).
B2) Chuyển vế này sang vế kia mệnh đề phủ định.
{┐B┐CD, A, B} → D, B (CM)_
CM (3).
B4) Tách dòng dạng 1:
{C, ┐B, A, B} → D (3.1)
{C, ┐C, A, B }→ D (3.2)
{C, D, A, B }→ D

(3.3)(CM)

Tiếp tục chứng minh các bài toán con của (3).
GVHD:Th.S: Huỳnh Minh Trí

Page 5


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

CM (3.1)
B2) Chuyển vế
{C, A, B} → D, B

(CM)

CM(3.2)

{(D, ┐D(E∧ F), ┐E  ┐ A B, A)→ D} (3) (CM)
Bước 5) Chứng minh các bài toán con 1, 2. Chúng ta cũng chứng minh qua các
bước giống như bài toán ban đầu.
CM (1).
B2) Chuyển vế
{( ┐D(E∧ F), ┐E  ┐ A B, A)→ D, A } (CM)
CM (2)
B4) Tách dòng dạng 1
{(B, ┐D, ┐E  ┐ A B, A)→ D} (2.1)
{(B, ( E∧ F), ┐E  ┐ A B, A)→ D} (2.2)
B5) Tiếp tục chứng minh các bài toán con 2.1, 2.2.
Cm (2.1)
B2) Chuyển vế
{(B, ┐E  ┐ A B, A)→ D, D} (2.1)
B4) Tách dòng theo dạng 1
{(B, ┐E, A)→ D} (2.1.1) (Không cm được)
{(B, ┐ A, A)→ D} (2.1.2) (CM)
{(B, B, A)→ D} (2.1.3) (Không cm được)
B5) Tới đây các bài toán con của bài toán con 2.1 không chứng minh được
nên không phải chứng minh tiếp các bài toán con của bài toán con 2.2 nữa, chúng ta đi
đến kết luận:
Bước 6) kết luận theo 6b: Bài toán ban đầu xuất phát không đúng.
Bài 3. Cho {(a∧b)→c, (b∧c)→d, ┐d}. Cm a→b?
GVHD:Th.S: Huỳnh Minh Trí

Page 7


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN



{( d, a) → b, d } (2.3)(CM)

GVHD:Th.S: Huỳnh Minh Trí

Page 8


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

B5)Do bài toán con (2.1) không chứng minh được nên bài toán con 2 cũng
không chứng minh được. Vậy nên không cần chứng minh tiếp bài toán con 3 nữa mà đi
tới b6.
Bước 6) Kết luận dạng 6b : do các bài toán con sai nên bài toán xuất phát ban đầu
cũng sai.
Bài 4. Cho {(p∧q)→r, (p∧r) →s, p, q}. Hỏi r ?...
Bước 1) Đưa bài toán cần chứng minh về dạng chuẩn:
{(┐(p∧q) r, ┐(p∧r) s, p, q) →r}
Bước 2) Chuyển vế. Không có mệnh đề phủ định độc lập chuyển qua b3.
Bước 3) Thay dấu đồng thời sử dụng mệnh để De Morgan bỏ đi phủ định của
nhóm mệnh đề (nếu không làm ở bước này cũng không sao, không bắt buộc).
{(┐p ┐q r, ┐p ┐r s, p, q) →r}
Bước 4) Tách dòng theo dạng 1
{(┐p, ┐p ┐r s, p, q) →r} (1)
{(┐q, ┐p ┐r s, p, q) →r} (2)
{(r, ┐p ┐r s, p, q) →r} (3) (CM)
Bước 5) Chứng minh các bài toán con 1, 2, 3.
Cm (1)
B2) Chuyển vế:


B2) Chuyển vế: {(┐q ┐r s, p, q) → s, q} (CM)
Cm (3):
B4) Tách dòng theo dạng 1:
{(r, ┐q, p, q) → s} (3.1)
{(r, ┐r , p, q) → s} (3.2)
{(r, s, p, q) → s} (3.3) (CM)
B5) Chứng minh các bài toán con 3.1, 3.2:
Cm (3.1):
B2) Chuyển vế: {(r, p, q) → s, q} (CM)
Cm (3.2):
GVHD:Th.S: Huỳnh Minh Trí

Page 10


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

B2) Chuyển vế:

{(r, p, q) → s, r } (CM)

Bước 6) Kết luận theo 6a: Tất cả các bài toán con 1, 2, 3 đều chứng minh được.
Vậy nên bài toán ban đầu được chứng minh.
Bài 6. CM [((a ∨ b →c ∧ d) ∧ (c→e) ∧ a)]→[(d ∧ c) ∨ b]?
Bước 1) Dạng chuẩn:
[((┐(a ∨ b) ∨ (c ∧ d)) ∧ (┐c ∨ e) ∧a)] → [(d ∧ c) ∨ b]
Dùng luật phân phối cho mệnh đề [(d ∧ c) ∨ b] ≡ [(b ∨ d) ∧ (b ∨
c)]
Bước 2) Không có chuyển sang bước 3.
Bước 3) Thay dấu ∧ ở GT và dấu ∨ ở KL =’,’.


B5) Cm các bài toán con
Cm(2.2.1)
B3) Thay dấu
[c, d, e, a] → [b, d] (CM)
Cm (2.2.2)
B3) Thay dấu
[c, d, e, a] → [b, c] (CM)
Bước 6) Kết luận 6a: Các bài toán con đều được chứng minh. Vậy bài toán ban
đầu đã được chứng minh.
Bài 7. CM { A → B, A → C ∨ E , B ∧ C → D, E → F, F ∨ D → G, A} hỏi G?
Bước 1) Dạng chuẩn:
{ ┐A ∨ B, ┐A ∨ C ∨ E, ┐B ∨ ┐C ∨ D, ┐E ∨ F, ┐F ∧ ┐D ∨ G, A →
G}
Bước 2) Không có, chuyển sang bước 3.
Bước 3) Thay dấu ∧ ở GT và dấu ∨ ở KL =’,’.
{ ┐A ∨ B, ┐A ∨ C ∨ E , ┐B ∨ ┐C ∨ D, ┐E ∨ F, ┐F , ┐D ∨ G, A →
G}
Bước 2) Chuyển vế.
┐A ∨ B, ┐A ∨ C ∨ E, ┐B ∨ ┐C ∨ D, ┐E ∨ F, ┐D ∨ G, A → G, F
Bước 4) Tách dòng theo dạng 1
GVHD:Th.S: Huỳnh Minh Trí

Page 12


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

┐A ∨ B, ┐A ∨ C ∨ E, ┐B ∨ ┐C ∨ D, ┐E ∨ F, G, A → G, F (1)
┐A ∨ B, ┐A ∨ C ∨ E, ┐B ∨ ┐C ∨ D, ┐E ∨ F, ┐D, A → G , F (2)

(2.2.2) ┐A ∨ B, ┐B ∨ ┐C ∨ D, A → G, D, F, E, A (CM)
(2.2.3) ┐A ∨ B, C, ┐B ∨ ┐C ∨ D, A → G, D, F, E
Bước 4: Tách dòng
(2.2.3.1) ┐A, C, ┐B ∨ ┐C ∨ D, A → G, D, F, E
(2.2.3.2) B, C, ┐B ∨ ┐C ∨ D, A → G, D, F, E
Bước 5: Chứng minh các bài toán con
(2.2.3.1) ┐A, C, ┐B ∨ ┐C ∨ D, A → G, D, F, E
Bước 2: chuyển vế
(2.2.3.1) C, ┐B ∨ ┐C ∨ D, A → G, D, F, E , A (CM)
(2.2.3.2) B, C, ┐B ∨ ┐C ∨ D, A → G, D, F, E
Bước 4: tách dòng
(2.2.3.2.1) B, C, ┐B, A → G, D, F, E
(2.2.3.2.2) B, C,┐C, A → G, D, F, E
(2.2.3.2.3) B, C, D, A → G, D, F, E
Bước 5: chứng minh các bài toán con
(2.2.3.2.1) B, C, ┐B, A → G, D, F, E
Bước 2: chuyển vế
(2.2.3.2.1) B, C, A → G, D, F, E, B (CM)
(2.2.3.2.2) B, C,┐C, A → G, D, F, E
Bước 2: chuyển vế
(2.2.3.2.2) B, C, A → G, D, F, E, C (CM)
(2.2.3.2.3) B, C, D, A → G, D, F, E (CM)
Bước 6) Kết luận 6a: Các bài toán con đều được chứng minh. Vậy bài toán ban
đầu đã được chứng minh
GVHD:Th.S: Huỳnh Minh Trí

Page 14


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

Bước 4) Tách dòng
Bước 5) Chứng minh các bài toán con

GVHD:Th.S: Huỳnh Minh Trí

Page 16


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

B. THUẬT GIẢI ROBINSON
a) Ý tưởng: Sử dụng:
Phương pháp chứng minh phản chứng:
[a→b đúng] ≡ [a ∧ ┐b sai hay mâu thuẫn]
Nguyên lý hợp giải:
┐a  b  c, a  d ≡ ┐a  b  c  a  d ≡ b  c 
d.
-

┐a ∧ b, a ∧ d ≡ ┐a ∧ b ∧ a ∧ d ≡ b ∧ d.
Ta thường gặp các trường hợp riêng của nguyên lý này:
a. Nguyên lý Modus Ponens: P đúng, P → Q đúng, suy ra
Q đúng.
b. Nguyên lý Modus Tollens: Q sai, P đúng → Q, suy ra
P sai.

- Để chứng minh từ các Gti suy ra một trong các KLj ta chỉ cần lấy

GT1, GT2, GT3,………, GTn → KL1, KL2, KL3,……., KLm

Bước 2: Thay phép toán ∧ ở GTi và phép toán ∨ ở KLj bằng dấu “,”.
Chỉ những mệnh đề phủ định đứng độc lập thì mới chuyển vế
GT1, GT2, a ∧ b, GT3,….,, GTn-1, GTn → KL1, c ∨ d, KL2,…,
KLm-1, KLm.
Bài toán chuyển vể dạng:

GT1, GT2, a , b, GT3,….,, GTn-1, GTn → KL1, c , d , KL2,…, KLm1, KLm.

Bước 3: Biến đổi dòng trên thành danh sách các mệnh đề
{GT1, GT2, a, b, ,… , GTn , ┐KL1, ┐KL2, ┐c, ┐d … , ┐KLm}
Bước 4 : Nếu trong danh sách mệnh đề ở bước 2 có 2 mệnh đề đối ngẫu
nhau thì bài toán được chứng minh. Ngược lại thì chuyển sang B5.
(a và ┐ a gọi là hai mệnh đề đối ngẫu nhau).
Bước 5 : Xây dựng một mệnh đề mới bằng cách tuyển một cặp mệnh đề
trong danh sách mệnh đề ở bước 2. Nếu mệnh đề mới có các biến
mệnh đề đối ngẫu nhau thì các biến đối ngẫu được loại bỏ.
Ví dụ : p  ┐q r  s  q
Hai mệnh đề ┐ q, q là đối ngẫu nên sẽ được loại bỏ
pÚrÚs.
Bước 6 : Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng
mệnh đề mới. Áp dụng heuristic cho thuật toán này ”áp dụng hợp
giải sau khi thu được mệnh đề mới {p Ú r Ú s} có thể bỏ 2 mệnh
đề cũ {p  ┐q } và { r  s  q}”. Nếu mệnh đề là mệnh đề
nguyên tử thì không rút gọn mà chuyển về cuối danh sách. Có thể
hợp giải nhiều thứ tự mệnh đề có biến đối ngẫu với nhau, nhưng
cách hay hợp giải mệnh đề nào ra được mâu thuẫn nhanh thì nên
chọn.
Ví dụ :

tượng tràn bộ nhớ(do bùng nổ tổ hợp) đối với các bài toán có kích
thước lớn.

-

Bài toán chứng minh được nhưng có thể kết luận không chứng minh
được nếu áp dụng Heuristic sai.
o Ví dụ: [(p q)→r),(p

r)→s), p q]→r

o B1) Đưa về dạng chuẩn ta có:
┐(p q) Úr), ┐ (p r) Ús), p q]→r
B2) Không có.

o
B3)

┐pÚ ┐q Úr, ┐pÚ ┐ r Ús, p q], ┐r

o

b4) Chưa có mệnh đề đối ngẫu nên chuyển sang B5.

o

b5) Hợp giải 2 mệnh đề đầu ta có:

GVHD:Th.S: Huỳnh Minh Trí


q ) ≡ ┐p

┐q.

Áp dung luật phân phối (nếu chưa gặp dạng chuẩn cần tìm) phép
tuyển đối với phép hội (hay phép hội đối với phép tuyển).
Ví dụ: p

(q

u) ≡ (p q)

(p u).

p

(q

u) ≡ (p

(p u).

q)

BÀI TẬP THUẬT GIẢI ROBINSON
Bài 1: Cho {(A∧ B) →C, (B∧C) →D, (A∧B)}. Hỏi D ?
Bước 1) Ta đưa VT và VP cùa bài toán cần chứng minh về dạng chuẩn bằng

cách:
Thay các phép toán ⇔ (tương đương) bằng phép toán →(kéo

mới như sau:
{┐A  ┐B  D, A, B , ┐D }
Chưa xuất hiện cặp mệnh đề mâu thuẫn.
Bước 5) Tiếp tục tuyển mệnh đề 1, 2 (hay hợp giải mệnh đề 1, 2):
{┐A  ┐B  D, A} ≡ {┐B  D}(Bỏ 2 mệnh đề
đối ngẫu A, ┐A. Có thể không bỏ mệnh đề A cũng được vì nó là mệnh đề nguyên
tử, có thể đưa vào cuối danh sách mệnh đề).
GVHD:Th.S: Huỳnh Minh Trí

Page 21


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

Bước 6) Thay thế 2 mệnh đề cũ bằng mệnh đề mới. Ta có danh sách mệnh
đề mới như sau:
{┐B  D , B , ┐D }
Vẫn chưa xuất hiện cặp mệnh đề mâu thuẫn. Chuyển sang B5
Bước 5) Hợp giải 2 mệnh đề đầu tiên ta có:
{┐B  D  B } ≡ {D}
Bước 6) Thay thế 2 mệnh đề cũ bằng mệnh đề mới, ta có:
Danh sách mệnh đề trở thành {D, ┐D }
Bước 7) Đã tìm được 2 mệnh đề đối ngẫu nên bài toán ban đầu đã được
chứng minh.
Bài 2. Cho {A→BD, D→E ∧ F, E ∧ A→B}. Hỏi A→D
Bước 1) Đưa GT, KL của bài toán cần chứng minh về dạng chuẩn:
Thay dấu →(kéo theo) bằng các phép toán ┐(phủ định),  (hay)
A→BD ≡ ┐ABD
D→E ∧ F ≡ ┐D(E∧ F)
E ∧ A→B ≡ ┐(E ∧ A) B

{ ┐A B,┐D F, A, ┐D }
Vẫn chưa xuất hiện mệnh đề đối ngẫu.
Tuyển mệnh đề 1, 2 trong danh sách mệnh đề mới:
{ ┐A  B ┐D  F  A} ≡ { B  ┐D  F } (Bỏ mệnh đề đối
ngẫu A,┐ A. Có thể không bỏ mệnh đề A).
Danh sách mệnh đề mới: { B  ┐D  F , ┐D}.
Bước 7) Tới đây không còn cách nào hợp giải để sinh ra mệnh đề mới được. Vậy
bài toán không được chứng minh.
Bài 3. Cho {(a∧b)→c, (b∧c)→d, ┐d}. Cm a→b?
Bước 1) Đưa bài toán cần chứng minh về dạng chuẩn:
Thay dấu →(kéo theo) bằng các phép toán ┐, ∨
(a∧b)→c ≡ ┐(a∧b) c
GVHD:Th.S: Huỳnh Minh Trí

Page 23


KHOA CNTT_TRƯỜNG ĐẠI HỌC SÀI GÒN

(b∧c)→d ≡ ┐(b∧c) d
a→b≡ ┐ab

Ta có: {(┐(a∧b) c, ┐(b∧c) d, ┐d) → ┐ab}
Bước 2) Thay phép toán ∧ ở GT và phép toán ∨ ở KL bằng dấu “,”:
Áp dụng luật De MorGan: ┐(a∧b) c ≡ ┐a∨┐b c
┐(b∧c) d ≡ ┐b∨┐c d
Ta có danh sách mệnh đề được thay:
{(┐a∨┐b c, ┐b∨┐c d, ┐d) → ┐a, b}
Bước 3) Biến đổi các dòng trên thành danh sách mệnh đề bằng cách bỏ dấu →,
đưa KL sang GT đồng thời ┐KL:

Dạng chuẩn của bài toán:

{(┐(p∧q) r, ┐(p∧r) s, p, q) →r}

Bước 2) Không có chuyển sang bước 3.
Bước 3) Biến đổi các dòng trên thành danh sách mệnh đề bằng cách bỏ dấu →,
đưa KL sang GT đồng thời ┐KL:
Đồng thời sử dụng luật De MorGan đối với mệnh đề 1, 2
{┐p ∨┐q∨ r, ┐p ∨ ┐r ∨ s, p, q, ┐r}
Bước 4) Có 5 mệnh đề nhưng chưa có mệnh đề đối ngẫu nên ta chuyển sang b5.
Bước 5) Tuyển mệnh đề 1, 3:
{┐p ∨┐q ∨ r p} ≡ {┐q ∨ r} (bỏ 2 mệnh đề đối ngẫu p, ┐p)
Bước 6) Danh sách mệnh đề mới : {┐q ∨ r, ┐p ∨ ┐r ∨ s, p, q, ┐r }
Chưa có mệnh đề đối ngẫu nên tiếp tục lặp lại b5, b6 để xây dựng mệnh đề mới.
Tuyển mệnh đề 1, 4 :
{┐p ∨ r ∨ q} ≡ {r} (Bỏ mệnh đề đối ngẫu q, ┐q)
Danh sách mệnh đề mới : {r, ┐p ∨ ┐r ∨ s, p, q, ┐r }
Bước 7) Tìm được cặp mệnh đề đối ngẫu {r, ┐r} trong danh sách mệnh đề mới.
Vậy bài toán ban đầu đã được chứng minh.
GVHD:Th.S: Huỳnh Minh Trí

Page 25