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

Bài 1: Biểu diễn tri thức và suy diễn
a) Biểu diễn các câu bằng vị từ logic và chuyển về dạng hội các câu tuyến
Gọi các vị từ như sau:
● G(x)G(x): xx giỏi lập trình
● E(x)E(x): xx giỏi tiếng Anh ● T(x)T(x): xx giỏi toán ● I(x)I(x): xx thông minh ● K(x)K(x): xx kiên trì
Chuyển các câu trong bài toán sang dạng logic:
1. Sinh viên nào giỏi tiếng Anh và giỏi toán đều giỏi lập trình ∀x
(E(x)∧T(x)→G(x))∀x (E(x)∧T(x)→G(x)) Chuyển về dạng chuẩn tắc (CNF):
¬E(x)∨¬T(x)∨G(x)¬E(x)∨¬T(x)∨G(x)
2. Sinh viên nào thông minh hoặc kiên trì đều giỏi tiếng Anh
∀x (I(x)∨K(x)→E(x))∀x (I(x)∨K(x)→E(x)) CNF:
¬I(x)∨¬K(x)∨E(x)¬I(x)∨¬K(x)∨E(x)
3. Sinh viên nào thông minh thì giỏi toán
∀x (I(x)→T(x))∀x (I(x)→T(x)) CNF: ¬I(x)∨T(x)¬I(x)∨T(x)
4. Lan thông minh nhưng không kiên trì
I(Lan),¬K(Lan)I(Lan),¬K(Lan)
b) Chuyển về dạng các câu Horn và suy diễn tiến
Chuyển về dạng các câu Horn:
1. E(x) T(x)→G(x)E(x) T(x)→G(x) ∧ ∧
⟹ G(x)G(x) nếu E(x)E(x) và T(x)T(x) đều đúng.
2. I(x) K(x)→E(x)I(x) K(x)→E(x) ∨ ∨
⟹ E(x)E(x) nếu I(x)I(x) đúng hoặc K(x)K(x) đúng.
3. I(x)→T(x)I(x)→T(x) ⟹ T(x)T(x) nếu I(x)I(x) đúng.
4. I(Lan)I(Lan), ¬K(Lan)¬K(Lan).
Suy diễn tiến để xác định "Lan có giỏi lập trình không?"
● Từ I(Lan)I(Lan) và I(x)→T(x)I(x)→T(x), suy ra T(Lan)T(Lan).
● Từ I(Lan)I(Lan), K(Lan)=falseK(Lan)=false và I(x)∨K(x)→E(x)I(x)∨K(x)→E(x), suy ra E(Lan)E(Lan).
● Từ E(Lan)E(Lan) và T(Lan)T(Lan), áp dụng quy tắc
E(x)∧T(x)→G(x)E(x)∧T(x)→G(x), suy ra G(Lan)G(Lan).
Kết luận: Lan giỏi lập trình.
Bài 2: Chứng minh bằng thuật toán Vương Hạo và RobinSon
1. Chứng minh bằng thuật toán Vương Hạo
Cho tập hợp các mệnh đề:
(p∧q)→r,(p∧s)→q,s(p∧q)→r,(p∧s)→q,s Chứng minh: p→rp→r.
Bước 1: Biểu diễn lại các mệnh đề
● (p q)→r(p q)→r chuyển thành ¬(p q) r¬(p q) r, tương đương ∧ ∧ ∧ ∨ ∧ ∨ ● (
p s)→q(p s)→q chuyển thành
¬(p s) q¬(p s) q, tương đương
¬p ¬s q¬p ¬s q.∨ ∨ ∨ ∨ ● ss giữ nguyên.
● Cần chứng minh: p→rp→r, tức là ¬p∨r¬p∨r.
Bước 2: Áp dụng thuật toán Vương Hạo
1. Từ ss, thay vào ¬p∨¬s∨q¬p∨¬s∨q, ta có ¬p∨q¬p∨q.
2. Từ ¬p∨q¬p∨q và ¬p∨¬q∨r¬p∨¬q∨r, xét các trường hợp:
○ Nếu pp sai, ¬p¬p đúng, suy ra p→rp→r.
○ Nếu pp đúng, qq có thể đúng hoặc sai.
○ Nếu qq đúng, từ ¬p q¬p q, ta không có mâu thuẫn.∨ ∨ ○
Nếu qq sai, từ ¬p∨¬q∨r¬p∨¬q∨r, suy ra rr.
Kết luận: p→rp→r đúng.
2. Chứng minh bằng thuật toán RobinSon Cho tập hợp:
{a∧b→c,b∧a∧c→d,a,b}{a∧b→c,b∧a∧c→d,a,b} Chứng minh: dd.
Bước 1: Biểu diễn lại các mệnh đề
● a∧b→ca∧b→c chuyển thành ¬a∨¬b∨c¬a∨¬b∨c.
● b∧a∧c→db∧a∧c→d chuyển thành ¬b∨¬a∨¬c∨d¬b∨¬a∨¬c∨d. ● aa và bb giữ nguyên.
Bước 2: Áp dụng thuật toán RobinSon (Phương pháp phân giải)
1. Kết hợp aa và bb với ¬a∨¬b∨c¬a∨¬b∨c, ta suy ra cc.
2. Kết hợp cc với ¬a ¬b ¬c d¬a ¬b ¬c d, ta suy ra dđ∨ ∨ ∨ ∨ ∨ ∨ 3. —> d đúng