Bài tập về suy diễn tri thức môn Đồ họa máy tính | Trường Đại học Kinh Doanh và Công Nghệ Hà Nội

lOMoAR cPSD| 59114765
BÀI TẬP BIỂU DIỄN TRI THỨC VÀ SUY DIỄN
Bài 1: Chuyển các công thức sau về dạng chuẩn hội, chuẩn tuyển: a. (P Q)v( R S)
-Loại bỏ kí hiệu tương đương trong công thức bằng quy tắc:
P Q ≡ (P=>Q) ∧ (Q=>P)
¬((P⇒Q)∧(Q⇒P))∨(¬R⇒S)
-Tiếp theo, chúng ta sử dụng quy tắc để đưa các phép nghịch đảo về dạng dương bằng cách thay thế:
¬A⇒B≡A∨B -Điều này sẽ cho ta:
¬((¬P∨Q)∧(¬Q∨P))∨(¬¬R∨S)
-Chúng ta cũng cần loại bỏ kí hiệu phủ định kép (¬) bằng cách sử dụng quy tắc: ¬¬A≡A
(¬(P∨¬Q)∧(¬Q∨P))∨(R∨S)
-Cuối cùng, chúng ta đưa mỗi hội trong công thức về dạng hội của các biến bằng cách phân phối:
(A∨B)∧(C∨D)≡(A∧C)∨(A∧D)∨(B∧C)∨(B∧D) -Vậy ta có:
((¬P∧¬Q)∨(P∧Q))∨(R∨S) b. (P Q)v R
Đầu tiên, chúng ta cần loại bỏ kí hiệu tương đương (bi-conditional) trong công
thức bằng cách sử dụng quy tắc:
P⟺Q≡(P⇒Q)∧(Q⇒P)
Vậy công thức sẽ trở thành: ¬((P⇒Q)∧(Q⇒P))∨¬R lOMoAR cPSD| 59114765
Tiếp theo, chúng ta sử dụng quy tắc để đưa các phép nghịch đảo về dạng dương
bằng cách thay thế: ¬A⇒B≡A∨B
Điều này sẽ cho ta: ¬((¬P∨Q)∧(¬Q∨P))∨¬R
Chúng ta cũng cần loại bỏ kí hiệu phủ định kép (¬¬) bằng cách sử dụng quy tắc: ¬¬A≡A
((P∧¬Q)∨(Q∧¬P))∨¬R
Cuối cùng, chúng ta đưa mỗi hội trong công thức về dạng hội của các biến
(CNF) bằng cách phân phối: (A∨B)∧(C∨D)≡(A∧C)∨(A∧D)∨(B∧C)∨(B∧D)
Vậy ta có: ((P∨¬R)∧(¬Q∨¬R)) c. A B ∧ C Đầu tiên, ta
A⇒(B∧C) biến đổi biểu thức thành dạng tương đương
bằng cách sử dụng quy tắc:
A⇒(B∧C)≡¬A∨(B∧C) Sau đó, ta sử
dụng phân phối để chuyển biểu thức về dạng chuẩn hội:
¬A∨(B∧C)≡(¬A∨B)∧(¬A∨C)
Đây là dạng chuẩn hội của công thức ban đầu: (¬A∨B)∧(¬A∨C). D:
Trước tiên, ta biến đổi biểu thức (P⇒Q) thành dạng tương đương sử dụng quy
tắc: (P⇒Q)≡¬P∨Q Tiếp theo, ta R∨¬S)b
iến đổi biểu thức ¬( thành dạng tương đương sử
dụng quy tắc De Morgan: ¬(
R∨¬S)≡¬R∧S Sau đó, ta sử
dụng phân phối để chuyển biểu thức về dạng chuẩn hội:
(¬P∨Q)∨(¬R∧S)≡(¬P∨Q∨¬R)∧(¬P∨Q∨S)
Đây là dạng chuẩn hội của công thức ban đầu:(¬P∨Q∨¬R)∧(¬P∨Q∨S). lOMoAR cPSD| 59114765
Bài 2: Cho cơ sở tri thức:
R1: Brother(X,Y)^Married(Y,Z) => Sister_in_law(X,Z). R2: Brother(tom,peter). R3: Brother(harold,john). R4: Married(peter,mary). R5: Married(john,sue)
Áp dụng thuật toán suy diễn lùi để chứng minh: Sister_in_law(tom,mary) Áp
dụng thuật toán suy diễn tiến vào cơ sở tri thức trên. Bài giải:
Ta có thể nhận thấy rằng từ R2 và R4, ta có thể suy ra rằng peter là anh trai của
tom và peter kết hôn với mary.
Từ quy tắc R1, nếu tom là anh trai của peter và peter kết hôn với mary, thì tom
sẽ là em trai của mary, và do đó mary là chị dâu của tom. Vậy ta suy ra được
Sister_in_law(tom, mary)Sister_in_law(tom, mary).
Bài 4: Cho cơ sở tri thức gồm các câu đúng sau:
- Sinh viên nào giỏi tiếng anh và giỏi toán đều giỏi lập trình.
- Sinh viên nào thông minh hoặc kiên trì đều giỏi tiếng anh.
- Sinh viên nào thông minh thì giỏi toán.
- Lan thông minh nhưng không kiên trì. 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. 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?”. Bài giải: lOMoAR cPSD| 59114765 a.
Đầu tiên, chúng ta sẽ xác định các vị từ và biểu diễn các câu theo dạng công thức logic:
1. GiaoiLapTrinh(X) - "Sinh viên X giỏi lập trình"
2. GiaoiTiengAnh(X) - "Sinh viên X giỏi tiếng Anh"
3. GiaoiToan(X) - "Sinh viên X giỏi toán"
4. ThongMinh(X) - "Sinh viên X thông minh"
5. KienTri(X) - "Sinh viên X kiên trì"
Các câu trong cơ sở tri thức có thể được biểu diễn như sau:
1. (GiaoiTiengAnh(X)∧GiaoiToan(X))⇒GiaoiLapTrinh(X)
2. (ThongMinh(X)∨KienTri(X))⇒GiaoiTiengAnh(X)
3. ThongMinh(X)⇒GiaoiToan(X)
4. ThongMinh(Lan)∧¬KienTri(Lan)
Sau đó, chúng ta chuyển các công thức trên về dạng hội các câu tuyển:
1. (¬GiaoiTiengAnh(X)∨¬GiaoiToan(X)∨GiaoiLapTrinh(X))
2. (¬ThongMinh(X)∨GiaoiTiengAnh(X))∧(¬KienTri(X)∨GiaoiTiengAnh(X))
3. (¬ThongMinh(X)∨GiaoiToan(X)) 4. ThongMinh(Lan)∧¬KienTri(Lan) b.
Tiếp theo, chúng ta chuyển các câu trong cơ sở tri thức về dạng các câu
Horn.Một công thức Horn là một công thức logic có tối đa một phần tử kích hoạt
(head) và một hoặc nhiều phần tử kích hoạt (body).
Chúng ta có thể chuyển đổi các công thức như sau:
1. GiaoiLapTrinh(X)←GiaoiTiengAnh(X)∧GiaoiToan(X)
2. GiaoiTiengAnh(X)←ThongMinh(X)
3. GiaoiTiengAnh(X)←KienTri(X)
4. GiaoiToan(X)←ThongMinh(X)
Cuối cùng, để trả lời câu hỏi "Lan lập trình có giỏi không?", chúng ta áp dụng suy diễn tiến:
Bắt đầu từ các luật Horn, ta sẽ tìm các luật có phần kích hoạt chứa
GiaoiLapTrinh(Lan) trong phần kết quả. Từ đó, ta sẽ tìm các luật có phần kết quả
chứa GiaoiTiengAnh(Lan), GiaoiToan(Lan), ThongMinh(Lan), và KienTri(Lan)
và tiếp tục thực hiện suy diễn cho đến khi không thể thêm được thêm bất kỳ sự suy diễn nào nữa. lOMoAR cPSD| 59114765
Từ câu 4, ta biết Lan thông minh nhưng không kiên trì, từ đó ta có thể suy ra
¬KienTri(Lan). Dùng các quy tắc suy diễn tiến, ta có thể suy ra
GiaoiTiengAnh(Lan), ThongMinh(Lan), và GiaoiToan(Lan).
Tiếp theo, từ luật GiaoiTiengAnh(X)←ThongMinh(X), ta có thể suy ra
GiaoiTiengAnh(Lan). Từ luật GiaoiToan(X)←ThongMinh(X), ta cũng có thể suy
ra GiaoiToan(Lan).
Từ GiaoiTiengAnh(Lan) và GiaoiToan(Lan), ta có thể áp dụng luật
GiaoiLapTrinh(X)←GiaoiTiengAnh(X)∧GiaoiToan(X), suy ra
GiaoiLapTrinh(Lan).
Vậy Lan lập trình có giỏi.