Bài tập Lập trình và logic môn Trí tuệ nhân tạo | Trường Đại học Kinh Doanh và Công Nghệ Hà Nội

lOMoAR cPSD| 58457166 Bài 1.
a. Thành lập các vị từ, công thức thích hợp biểu diễn các câu trên, sau đó
chuyển chúng về dạng hội các câu tuyển.
Gọi: P(x) là x giỏi tiếng anh Q(x) là x giỏi toán
R(x) là x giỏi lập trình S(x) là x thông minh T(x) là x kiên trì Từ đó suy ra:
1. Sinh viên nào giỏi tiếng Anh và giỏi toán đều giỏi lập trình:
• Logic: (P(x) ∧ Q(x) → R(x)
• Phủ định: l(P(x) ∧ Q(x)) ∨ R(x)
• De Morgan: lP(x) ∨ lQ(x) ∨ R(x)
• Dạng tuyển: lP(x) ∨ lQ(x) ∨ R(x) (đúng cho mọi x)
2. Sinh viên nào thông minh hoặc kiên trì đều giỏi tiếng Anh:
• Logic: (S(x) ∨ T(x) → P(x)
• Phủ định: l(S(x) ∨ T(x)) ∨ P(x)
• De Morgan: (lS(x) ∧ lT(x)) ∨ P(x)
• Dạng tuyển: lS(x) ∨ P(x) và lT(x) ∨ P(x) (2 mệnh đề riêng)
3. Sinh viên nào thông minh thì giỏi toán: • Logic: (S(x) → Q(x))
• Phủ định: lS(x) ∨ Q(x)
• Dạng tuyển: lS(x) ∨ Q(x) (đúng cho mọi x)
4. Lan thông minh nhưng không kiên trì: lOMoAR cPSD| 58457166 Logic: S(Lan) ∧ lT(Lan)
• Dạng tuyển: S(Lan) và lT(Lan) (2 mệnh đề riêng)
b. Chuyển các câu trong cơ sở tri thức về dạng các câu Horn. Dùng phương
pháp suy diễn tiến để trả lời câu hỏi “Lan lập trình có giỏi không?”.
1. lP(x) ∨ lQ(x) ∨ R(x) ≡ P(x) ∧ Q(x)→R(x)
2. lS(x) ∨ P(x) ≡ S(x)→P(x) và lT(x) ∨ P(x) ≡ T(x)→P(x)
3. lS(x) ∨ Q(x) ≡ S(x)→Q(x) 4. S(Lan) và và lT(Lan) Bài 2.
1. Sử dụng thuật toán Vương Hạo để chứng minh bài toán sau:
Cho {(p ∧q) →r, (r∧ s) → q, s} Suy ra: p → r Chuyển về dạng tuyển: 1. (p∧q)→r •
l(p∧q)∨ r (loại bỏ hàm ý) •
lp ∨ lq ∨ r (áp dụng De Morgan) •
dạng tuyển: lp ∨ lq ∨ r 2. (r∧s)→q • l(r∧s) ∨ q • lr ∨ ls ∨ q •
Dạng tuyển: lr ∨ ls ∨ q 3. s • Dạng tuyển: s
Chuyển phủ định của kết luận: l(p→r) •
l(lp ∨ r) (loại bỏ hàm ý) •
p ∧ lr (áp dụng De Morgan) lOMoAR cPSD| 58457166
dạng tuyển: p và lr (tách thành 2 câu tuyển)
cơ sở tri thức đầy đủ ở dạng tuyển: • lp ∨ lq ∨ r (1) • lr ∨ ls ∨ q (2) • s (3) • p (4) (từ l(p→r)) •
lr (5) (từ l(p→r)) áp dụng phương pháp phân giải: p (4) + lp ∨ lq ∨ r
(1) → lq ∨ r (6) s (3) + lr ∨ ls ∨ q (2) → lr ∨ q (7) lr (5) + lr ∨ q(7) → q (8) q (8) +
lq ∨ r (6)→ r (9) r (9)+ lr (5) → Ø
Ta đã tìm thấy Ø khi giả sử l(p→r)) cùng với tiền đề. Điều này chứng tỏ {(p∧q)→r,
(r∧s)→q, s}∧ l(p→r) không thỏa mãn.
Theo nguyên lý phản chứng trong logic, nếu A ∧ lB không thỏa mãn được thì A suy ra B
Vậy p →r được suy ra từ {(p∧q)→r,(r∧s)→q,s}
2. chứng minh bằng thuật toán robison {a
∧ b→c, b ∧ c→d , a ∧ b} . Kết luận: {d} Chuyển về dạng tuyển: 1. (a ∧b)→c: • l(a ∧b) ∨ c • la ∨ lb ∨ c 2. (b ∧c)→d: 3. a∧b: a, b
4. ld (phủ định kết luận d) lOMoAR cPSD| 58457166
Áp dụng phương pháp robinson:
- Kiểm tra A∧ lB (phản chứng)
la ∨ lb ∨ c, lb ∨ lc ∨ d, a, b, ld
- phân giải: a+ la ∨ lb ∨
c→ lb ∨ c b+ lb ∨ lc ∨ d→ lc ∨ d lc ∨ d+ ld→ lc lb ∨ c + lc→lb b+ lb→ Ø (mâu thuẫn)
Vì a∧ ld không thỏa mãn (có mâu thuẫn), nên từ {a ∧ b→c, b ∧ c→d , a ∧ b } ta có thể suy ra d phải đúng