Bài giảng Trí Tuệ Nhân Tạo - Chương 5: Sử dụng logic mệnh đề và vị từ - Nguyễn Văn Hòa

pdf

35 trang huongle 2510

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí Tuệ Nhân Tạo - Chương 5: Sử dụng logic mệnh đề và vị từ - Nguyễn Văn Hòa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_tri_tue_nhan_tao_chuong_5_su_dung_logic_menh_de_va.pdf

Nội dung text: Bài giảng Trí Tuệ Nhân Tạo - Chương 5: Sử dụng logic mệnh đề và vị từ - Nguyễn Văn Hòa

Ch ươ ng 5: S d ng logic m nh đ và v t 1
Bi u di n tri th c nh logic v t Tri th ức đượ c th ể hi ện d ướ i d ạng l ớp c ủa các bi ểu th ức logic và c ơ s ở tri th ức gi ải bài toán đượ c thi ết l ập trên c ơ sở l ớp c ủa các bi ểu th ức logic này. Lu ật suy di ễn và th ủ t ục ch ứng minh tri th ức đượ c l ập lu ận trên c ơ s ở toán h ọc logic v ới các yêu c ầu đặ t ra c ủa bài toán. Với ph ươ ng pháp bi ểu di ễn này cung c ấp ý t ưở ng để ti ếp cận v ới ngôn ng ữ l ập trình Prolog trong l ĩnh v ực trí tu ệ nhân t ạo. Bi ểu di ễn tri th ức nh ờ logic v ị t ừ còn đượ c g ọi là m ột ngôn ng ữ bi ểu di ễn dùng để mã hóa tri th ức d ướ i d ạng sao cho d ễ l ập trình v ới ngôn ng ữ l ập trình Prolog. 2
Ni dung Phép toán m ệnh đề Bi ểu di ễn s ự ki ện đơ n gi ản Bi ểu di ễn: isa và instance Các hàm và v ị t ừ kh ả tính toán Lu ật phân gi ải Phân gi ải m ệnh đề Đư a v ề clause form 3
Phép toán m nh đ Mệnh đề : là các câu kh ẳng đị nh v ề th ế gi ới Mệnh đề có th ể đúng (true) ho ặc sai (false) Mệnh đề đơ n gi ản: Đồ ng là m ột kim lo ại => Đúng Gỗ là m ột kim lo ại => Sai Hôm nay là th ứ Hai => Sai Ký hi ệu trong phép tính m ệnh đề : Ký hi ệu m ệnh đề : P, Q, R, S, Ký hi ệu chân lý: true, false Các phép toán logic: ∧∧∧ (h ội), ∨∨∨ (tuy ển), ¬¬¬ (ph ủ đị nh), ⇒⇒⇒ (kéo theo) , = (t ươ ng đươ ng) 4
Phép toán m nh đ Đị nh ngh ĩa câu trong phép tính m ệnh đề : Mỗi ký hi ệu m ệnh đề , ký hi ệu chân lý là m ột câu Ph ủ đị nh c ủa m ột câu là m ột câu Hội, tuy ển, kéo theo, t ươ ng đươ ng c ủa hai câu là m ột câu. Ký hi ệu ( ), [ ] đượ c dùng để nhóm các ký hi ệu vào các bi ểu th ức con. Một bi ểu th ức m ệnh đề đượ c g ọi là m ột câu (hay công th ức d ạng chu ẩn- WFF:Well -Formed Formula) ⇔ nó có th ể đượ c t ạo thành t ừ nh ững ký hi ệu h ợp l ệ thông qua m ột dãy các lu ật trên. Ví d ụ: ( (P ∧Q) ⇒ R) = ¬P ∨ ¬Q ∨ R 5
Phép toán m nh đ Mệnh đề t ươ ng đươ ng Dạng h ấp thu Dạng khác A ∧ (A ∨ B) = A A ⇒ B = ¬¬¬A ∨ B A ∨ (A ∧ B) = A ¬¬¬ (A ⇒ B) = A ∧¬¬¬ B A ∧ (¬¬¬A ∨ B) = A∧B A ⇒ B = A ∧¬¬¬ B⇒ FALSE A ∨ (¬¬¬A ∧ B) = A∨B Dạng De Morgan ¬¬¬ (A ∧ B) = ¬¬¬A ∨¬¬¬ B ¬¬¬ (A ∨ B) = ¬¬¬A ∧¬¬¬ B 6
Phép toán m nh đ Các lu ật suy di ễn Lu ật Modus Ponens (MP) Lu ật C ộng A, A ⇒ B ∴∴∴ B A ∴∴∴ AvB Lu ật Modus Tollens (MT) Lu ật tam đoạn lu ận tuy ển A⇒ B, ¬¬¬B ∴∴∴ ¬¬¬A Av B, ¬¬¬A ∴∴∴ B Lu ật H ội Lu ật tam đoạn lu ận gi ả thi ết A,B ∴∴∴ A^B A⇒ B,B ⇒ C∴∴∴ A⇒ C Lu ật đơ n gi ản A^B ∴∴∴ A 7
Bi u di n s ki n đơ n gi n: VD1 8
Bi u di n s ki n đơ n gi n: VD2 9
Bi u di n s ki n đơ n gi n Sử d ụng logic v ị t ừ c ấp 1 (PC) Ví d ụ 10
Bi u di n s ki n đơ n gi n Suy di ễn 11
Bi u di n s ki n đơ n gi n Bi ểu di ễn v ị t ừ cho các câu sau đây: Marcus was a man Macus was a Pompeian All Pompians were Romans Caesar was a ruler All Romans were either loyal to Caesar or hated hime Everyone is loyal to someone People only try to assassinate rulers they are not loyal to Marcus tried to assassinate Caesar 12
Bi u di n: Isa và instance Bi ểu di ễn instance: a1 là thanh viên c ủa A 13
Bi u di n: isa và instance 5 câu đầ u c ủa ví d ụ trên có th ể bi ểu di ễn: 1. man(Marcus) 2. Pompeian(Marcus) 3. ∀X: Pompeian(X) → Roman(X) 4. ruler(Caesar) 5. ∀ X: Roman(X) → loyalto(X, Caesar) v hate(X, Caesar) Ho ặc: 1.instance(Marcus, man) 2. instance(Marcus, Pompeian) 3. ∀ X: instance(X, Pompeian) → instance(X, Roman) 4. instance(Caesar, ruler) 5. ∀ X: instance(X, Roman) → loyalto(X, Caesar) v hate(X, Caesar) 14
Các hàm và v t kh tính toán Các tr ườ ng h ợp có th ể khai báo đượ c, nh ư: tryassassinate(Marcus, Ceasar). loyalto(Marcus, Caesar) Trong tr ườ ng h ợp nh ư quan h ệ trên các s ố, nh ư: 1 (3+2) → Không th ể ghi đủ : lt(q,1), lt(2,3); Gọi hàm để tính (3 + 2) → tính toán đượ c gt(7,3+2) và tr ả v ề tr ị (true) 15
Các hàm và v t kh tính toán Dùng hàm và v ị t ừ tính toán đượ c (VD): 1. Marcus was a man. man(Marcus) 2. Marcus was a Pompeian. Pompeian(Marcus) 3. Marcus was born in 40 A.D born(Marcus,40) 4. All men are mortal. ∀ X: man(X) → mortal(X) 16
Các hàm và v t kh tính toán Dùng hàm và v ị t ừ tính toán đượ c (VD) 5. All Pompeian died when the vocano erupted in 79 AD. erupted(vocano, 79) ^ ∀ X: [Pompeian(X) → died(X, 79)] 6. No mortal lives longer then 150 years. ∀ X: ∀ T1: ∀ T2 : mortal(X) ^ born(X, T1) ^ gt(T2 – T1, 150) → dead(X, T2) 7. It is now 1991 now = 1991 Question: Is Marcus alive ? Hay: alive(Marcus, now) OR: ¬alive(Marcus, now) 17
Các hàm và v t kh tính toán Dùng hàm và v ị t ừ tính toán đượ c (VD): → Cơ s ở tri th ức không ch ứa m ối quan h ệ gi ữa alive và dead → Bổ sung: 8. Alive means not dead. ∀ X: ∀ T: [alive(X,T) → ¬dead(X,T)] ^ [¬dead(X,T) → alive(X,T)] 9. Is someone dies, he is dead at all later times ∀ X: ∀ T1: ∀ T2: died(X,T1) ^ gt(T2, T1) → dead(X, T2) 18
Các hàm và v t kh tính toán 19
Lu t phân gi i Th ủ t ục ch ứng minh ch ỉ d ựa trên 1 phép toán – phân gi ải. Dạng ch ứng minh: ph ản ch ứng. Ch ứng minh P b ằng cách gi ả thi ết ¬P r ồi c ố g ắng đư a ra mâu thu ẩn. Yêu c ầu: các bi ểu th ức ph ải đượ c chu ẩn hoá tr ướ c ở d ạng clause (clause form) Clause Form = clause ^ clause ^ clause ^ Clause = term v term v term Ví d ụ clause: P v ¬Q v R. ¬P v Q v ¬R ¬Roman(X) v hate(X, Ceaser) Lu ật phân gi ải: Mệnh đề Vị t ừ 20
Lu t phân gi i Để ch ứng minh P t ừ t ập F c ủa các m ệnh đề : 1. Chuy ển F sang clause form 2. L ập ¬P, chuy ển ¬P sang clause form. Thêm vào các clause ở b ướ c 1 3. L ặp đế n khi g ặp mâu thu ẩn, ho ặc không th ể đi ti ếp đượ c nữa: 1. Ch ọn 2 clauses ở d ạng. a v C1 ¬a v C2 Với C1, C2 bi ểu th ức con c ủa 1 clause 2. Thêm vào t ập clauses dòng: (C1 – a) v (C2 – ¬a ) Dấu “–” ngh ĩa là lo ại b ỏ a kh ỏi C1 và ¬a kh ỏi C2 21
Lu t phân gi i: ví d 22
Lu t phân gi i: ví d Ch ứng minh 23
Lu t phân gi i: ví d Ví d ụ: Ch ứng minh hình th ức b ằng lu ật phân gi ải cho đoạn v ăn sau đây: “ Nam ho ặc là chuyên gia ho ặc là ng ườ i cá bi ệt. N ếu Nam là chuyên gia thì Nam có nhi ều báo cáo có ti ếng và đượ c đồ ng nghi ệp tin c ậy. N ếu Nam có nhi ều báo cáo có ti ếng thì h ộp th ư c ủa Nam có nhi ều th ư. N ếu Nam là ng ườ i cá bi ệt thì Nam không đượ c b ạn bè tôn tr ọng. Quan sát th ấy rằng, h ộp th ư c ủa Nam không có nhi ều th ư “. ch ứng mính: “Nam không đượ c b ạn bè tôn tr ọng.“ 24
Lu t phân gi i: ví d Các m ệnh đề : P1 = “Nam là chuyên gia” P2 = “Nam là ng ườ i cá bi ệt” P3 = “Nam có nhi ều báo cáo có ti ếng” P4 = “Nam đượ c đồ ng nghi ệp tin c ậy” P5 = “H ộp th ư c ủa Nam có nhi ều th ư” P6 = “Nam đượ c b ạn bè tôn tr ọng” Các câu: 1. (P1 ^ ¬P2) v (¬P1 ^ P2) 2. P1 → (P3 ^ P4) 3. P3 → P5 4. P2 → ¬P6 5. ¬P5 25
Lu t phân gi i: ví d 26
Lu t phân gi i: ví d Ch ứng minh 27
Đư a v claus form Câu sau đượ c dùng làm ví d ụ trong th ủ t ục đư a v ề clause form. “All Romans who know Marcus either hate Caesar or think that anyone who hates anyone is crazy” ∀ X: [roman(X) ^ know(X, Marcus)] → [hate(X, Ceasar) v (∀ Y: ∃ Z: hate(Y,Z) → thinkcrazy(X,Y))] 28
Đư a v claus form 1. Lo ại b ỏ → dùng t ươ ng đươ ng: a →b = ¬a v b Ví d ụ ∀ X: [roman(X) ^ know(X, Marcus)] → [hate(X, Ceasar) v (∀ Y: ∃ Z: hate(Y,Z) → thinkcrazy(X,Y))] ∀ X: ¬[roman(X) ^ know(X, Marcus)] v [hate(X, Ceasar) v (∀ Y: ∃ Z: hate(Y,Z) → thinkcrazy(X,Y))] 29
Đư a v claus form 2. Thu gi ảm t ầm v ực c ủa ¬ vào đế n m ức term. Dùng t ươ ng đươ ng: ¬(¬p) = p De Morgan: ¬(a v b) = ¬a ^ ¬b ¬(a ^ b) = ¬a v ¬b Tươ ng đươ ng l ượ ng t ừ: ¬ ∀ X: P(X) = ∃ X: P(X) ¬ ∃: P(X) = ∀ X: P(X) Áp dung cho ví d ụ tr ướ c ∀ X: [¬roman(X) v ¬know(X, Marcus)] v [hate(X,Ceasar) v (∀ Y: ∃ Z: ¬hate(Y,Z) v thinkcrazy(X,Y))] 30
Đư a v claus form 3. Chu ẩn hoá các bi ến để các l ượ ng t ừ ch ỉ ràng bu ộc 1 bi ến duy nh ất. Bi ến đổ i nh ư VD sau: ∀ X: P(X) v ∀ X: Q(X) = ∀ X: P(X) v ∀ Y: Q(Y) 4. Chuy ển l ượ ng t ừ v ề bên trái. Chú ý, không chuy ển th ứ t ự c ủa chúng Ví d ụ: ti ếp b ướ c 2. ∀ X: ∀ Y: ∃ Z: [¬roman(X) v ¬know(X, Marcus)] v [hate(X, Ceasar) v (¬hate(Y,Z) v thinkcrazy(X,Y))] 31
Đư a v claus form 5. Lo ại b ỏ l ượ ng t ừ t ồn t ại : S ử d ụng hàm skolem Hàm skolem: ∀ X: ∀ Y: ∃ Z : P(X,Y,Z) = ∀ X: ∀ Y: P(X,Y,f(X,Y)) Bi ến c ủa l ượ ng t ừ t ồn t ại đượ c thay là hàm theo nh ững bi ến của l ượ ng t ừ v ới m ọi tr ướ c nó Bỏ qua các l ượ ng t ừ (v ới m ọi) còn l ại ở b ướ c 5. xem nh ư mọi bi ến đề u b ị tác độ ng b ởi l ượ ng t ừ v ới m ọi ( ∀ ) Ví d ụ: ti ếp b ướ c 4 [¬roman(X) v ¬know(X, Marcus)] v [hate(X, Ceasar) v (¬hate(Y,Z) v thinkcrazy(X,Y))] 32
Đư a v claus form 7. Chuy ển h ội chu ẩn (Conjunctive Normal Form - CNF) Một chu ỗi các m ệnh đề k ết n ối nhau b ằng quan h ệ AND (^). Mỗi m ệnh đề có d ạng m ột tuy ển OR (v) c ủa các bi ến m ệnh đề . Dùng phép phân ph ố gi ữa v và ^ Dạng th ườ ng g ặp: (a ^ b) v c = (a v c) ^ (b v c) (a ^ b) v (c ^ d) = (a v c) ^ (a v d) ^ (b v c) ^ (b v d) Ví d ụ: ti ếp b ướ c 6 ¬roman(X) v ¬know(X, Marcus) v hate(X, Ceasar) v ¬hate(Y,Z) v thinkcrazy(X,Y) 33
Đư a v claus form 8. Tách riêng các clause trong CNF ở trên Nếu có clause form: (a v ¬b) ^ (¬a v c v d) ^ (a v ¬c v e) Thì đượ c tách riêng thành các clause: 1. (a v ¬b) 2. (¬a v c v d) 3. (a v ¬c v e) Đư a các l ượ ng t ừ v ề t ừng clause (∀ X: P(X) ^ Q(X) ) = ∀ X: P(X) ^ ∀ X: Q(X) 34
Đư a v claus form BT: đư a v ề clause form các câu sau: 1. ∀X A(X) v ∃ X B(X) → ∀XC(X) ^ ∃X D(X) 2. ∀X (p(X) v q(X)) → ∀X p(X) v ∀X q(X) 3. ∃X p(X) ^ ∃X q(X) → ∃X(p(X) ^ q(X)) 4. ∀X ∃Y p(X,Y) → ∀Y ∃X p(X,Y) 5. ∀ X (p(X, f(X)) → p(X,Y)) 35