Bài giảng Suy diễn với logic bậc nhất - Tô Hoài Việt

Bài giảng Suy diễn với logic bậc nhất - Tô Hoài Việt nhằm trình bày những nội dung về cơ sở của hợp giải trên logic bậc nhất, hợp giải trên logic bậc nhất, các ví dụ, suy diễn tiến và suy diễn lùi, thuật giải suy diễn tiến, thuật giải suy diễn lùi.

Nội dung trích xuất từ tài liệu:
Bài giảng Suy diễn với logic bậc nhất - Tô Hoài ViệtSUY DIỄN VỚI LOGIC BẬC NHẤT Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn 1 Tổng quát• Cơ sở của hợp giải trên logic bậc nhất• Hợp giải trên logic bậc nhất• Các ví dụ• Suy diễn tiến và suy diễn lùi• Thuật giải suy diễn tiến• Thuật giải suy diễn lùi 2 Cơ sở của hợp giải FOL• Hợp giải (Robinson): để chứng minh một tập KB có suy dẫn logic được một câu hay không, viết lại KB dưới dạng mệnh đề (clausal form) và cố gắng suy dẫn ra mệnh đề sai (hợp giải hai mệnh đề đối ngẫu)• Phép đồng nhất: Unify(P(x),P(A))  = {x/A} 3 Ví dụChứng minh rằng (P(x) Q(x)) và P(A) suy dẫn logic z.Q(z)1. P(x) Q(x) Tiền đề2. P(A) Tiền đề3. Q(z) Kết luận4. P(z) 1, 3 = {x/z}5. False 2, 4 = {x/z, z/A} 4 Ví dụ (tt)Cho trước (P(x) Q(x)) và P(A) và P(B), tìm z sao cho Q(z) là đúng1. P(x) Q(x) Tiền đề2. P(A) Tiền đề3. P(B) Tiền đề4. Q(z) Kết luận5. P(z) 1, 4 = {x/z}6. False 2, 5 = {x/z, z/A}7. False 3, 5 = {x/z, z/B} 5 Ví dụ Quan hệ họ hàngArt là cha của Bob và Bud.Bob là cha của Cal và Coe.Ông nội là cha của cha. F(Art, Bob) F(Art, Bud) F(Bob, Cal) F(Bob, Coe) F(x, y) F(y,z) G(x,z) 6Art có phải là Ông của Coe?1. F(Art, Bob) Tiền đề2. F(Art, Bud) Tiền đề3. F(Bob, Cal) Tiền đề4. F(Bob, Coe) Tiền đề5. F(x, y) F(y,z) G(x,z) Tiền đề6. G(Art, Coe) Kết luận7. F(Art, y) F(y,Coe) 5, 6 ={x/Art, z/Coe}8. F(Art, Bob) 4, 7 ={x/Art, z/Coe, y/Bob}9. False 1, 8 ={x/Art, z/Coe, y/Bob} 7 Ai là Ông của Coe?1. F(Art, Bob) Tiền đề2. F(Art, Bud) Tiền đề3. F(Bob, Cal) Tiền đề4. F(Bob, Coe) Tiền đề5. F(x, y) F(y,z) G(x,z) Tiền đề6. G(x2, Coe) Kết luận7. F(x2, y) F(y,Coe) 5, 6 = {z/ Coe, x/x2}8. F(Bob, Coe) 1, 7 = {z/ Coe, x/x2, x2/ Art, y/ Bob}9. False 4, 8 = {z/ Coe, x/x2, x2/ Art, y/ Bob} 8 Ai là Cháu của Art?1. F(Art, Bob) Tiền đề2. F(Art, Bud) Tiền đề3. F(Bob, Cal) Tiền đề4. F(Bob, Coe) Tiền đề5. F(x, y) F(y,z) G(x,z) Tiền đề6. G(Art, z2) Kết luận7. F(Art, y) F(y,z2) 5, 6 = {x/Art, z/z2}8. F(Bob, z2) 1, 7 = {x/Art, z/z2,, y/Bob}9. F(Bud, z2) 2, 7 = {x/Art, z/z2, y/Bud}10. False 3, 8 = {x/Art, z/z2, y/Bob, z2/Cal}11. False 4, 8 = {x/Art, z/z2, y/Bob, z2/Coe} 9 Ông và cháu?1. F(Art, Bob) Tiền đề2. F(Art, Bud) Tiền đề3. F(Bob, Cal) Tiền đề4. F(Bob, Coe) Tiền đề5. F(x, y) F(y,z) G(x,z) Tiền đề6. G(x, z) Kết luận7. F(x, y) F(y,z) 5, 6 = {}8. F(Bob, z) 1, 7 = {x/Art, y/Bob}9. F(Bud, z) 2, 7 = {x/Art, y/Bud}10. False 3, 8 = {x/Art, y/Bob, z/Cal}11. False 4, 8 = {x/Art, y/Bob, z/Coe} 10 Suy diễn tiến và suy diễn lùi• Suy diễn tiến (Forward chaining) và suy diễn lùi (Backward chahining) được áp dụng lên các biểu thức dạng Horn• Biểu thức dạng Horn: trong biểu thức có nhiều nhất một literal khẳng định p1 p2 p3 … pn• Hay dạng luật (luật sinh) p2 p3 … pn p1 11 Thuật toán Suy diễn TiếnFOL-FC-Ask(KB, ){ repeat until new là rỗng new  {} với mọi câu r trong KB // r ở dạng chuẩn hóa (p1 … pn => q) với mọi phép thế sao cho (p1 … pn) = (p’1 … p’n) với p’1,…,p’n nào đó ...