Đưa về claus form 7. Chuyển hội chuẩn ( Conjunctive Normal Form – CNF ) Một chuỗi những mệnh đề liên kết nhau bằng quan hệ AND ( ^ ). Mỗi mệnh đề có dạng một tuyển OR ( v ) của những 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 ) Đưa về claus form 8. Tách riêng những 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 những clause : 1. ( a v ¬ b ) 2. ( ¬ a v c v d ) 3. ( a v ¬ c v e ) 34 Đưa những lượng từ về từng clause ( ∀ X : P. ( X ) ^ Q ( X ) ) = ∀ X : P. ( X ) ^ ∀ X : Q. ( X )
35 trang
| Chia sẻ : thucuc2301
| Lượt xem: 637
| Lượt tải : 0
Bạn đang xem trước 20 trang tài liệu Giáo trình Trí tuệ nhân tạo – Chương 5: Sử dụng logic mệnh đề và vị từ – Nguyễn Văn Hòa, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 biểu lộ dưới dạng lớp của những 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 những biểu thức logic này. Luật suy diễn và thủ tục chứng tỏ tri thức được lập luận trên cơ sở toán học logic với những nhu yếu đặt ra của bài toán. Với chiêu thức trình diễn này phân phối ý tưởng sáng tạo để tiếp cận với ngôn từ lập trình Prolog trong nghành trí tuệ nhân tạo. 2 Biểu diễn tri thức nhờ logic vị từ còn được gọi là một ngôn từ trình 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 từ lập trình Prolog. Nội dung Phép toán mệnh đề Biểu diễn sự kiện đơn thuầ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 đề 3 Đưa về clause form Phép toán mệnh đề Mệnh đề : là những câu chứng minh và khẳng định về quốc tế Mệnh đề hoàn toàn có thể đúng ( true ) hoặc sai ( false ) Mệnh đề đơn thuần : Đồng là một sắt kẽm kim loại => Đúng Gỗ là một sắt kẽm 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, … 4 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 tự ) 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 tự của hai câu là một câu. Ký hiệu ( ), [ ] được dùng để nhóm những ký hiệu vào những 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ó 5 thể được tạo thành từ những ký hiệu hợp lệ trải qua một dãy những luật trên. Ví dụ : ( ( P ∧ Q ) ⇒ R ) = ¬ P ∨ ¬ Q ∨ R Phép toán mệnh đề Mệnh đề tương tự Dạng hấp thu Dạng khác A ∧ ( A ∨ B ) = A A ∨ ( A ∧ B ) = A A ∧ ( ¬ A ∨ B ) = A ∧ B A ∨ ( ¬ A ∧ B ) = A ∨ B Dạng De Morgan A ⇒ B = ¬ A ∨ B ¬ ( A ⇒ B ) = A ∧ ¬ B A ⇒ B = A ∧ ¬ B ⇒ FALSE 6 ¬ ( A ∧ B ) = ¬ A ∨ ¬ B ¬ ( A ∨ B ) = ¬ A ∧ ¬ B Phép toán mệnh đề Các luật suy diễn Luật Modus Ponens ( MP ) A, A ⇒ B ∴ B Luật Modus Tollens ( MT ) A ⇒ B, ¬ B ∴ ¬ A Luật Hội Luật Cộng A ∴ AvB Luật tam đoạn luận tuyển Av B, ¬ A ∴ B Luật tam đoạn luận giả thiết 7 A, B ∴ A ^ B Luật đơn giản A ^ B ∴ A A ⇒ B, B ⇒ C ∴ A ⇒ C Biểu diễn sự kiện đơn thuần : VD1 8 Biểu diễn sự kiện đơn thuần : VD2 9 Biểu diễn sự kiện đơn thuần Sử dụng logic vị từ cấp 1 ( PC ) Ví dụ 10 Biểu diễn sự kiện đơn thuần Suy diễn 11 Biểu diễn sự kiện đơn thuần Biểu diễn vị từ cho những 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 12 People only try to assassinate rulers they are not loyal to Marcus tried to assassinate Caesar 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 hoàn toàn có thể màn 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 ) ∀ 14 3. X : instance ( X, Pompeian ) → instance ( X, Roman ) 4. instance ( Caesar, ruler ) 5. ∀ X : instance ( X, Roman ) → loyalto ( X, Caesar ) v hate ( X, Caesar ) Các hàm và vị từ khả tính toán Các trường hợp hoàn toàn có thể khai báo được, như : tryassassinate ( Marcus, Ceasar ). loyalto ( Marcus, Caesar ) Trong trường hợp như quan hệ trên những số, như : 1 < 2 2 <3 7 > ( 3 + 2 ) 15 → Không thể ghi đủ : lt ( q, 1 ), lt ( 2,3 ) ; Gọi hàm để tính ( 3 + 2 ) → giám sát được gt ( 7,3 + 2 ) và trả về trị ( true ) Các hàm và vị từ khả tính toán Dùng hàm và vị từ đo lường và thống kê đượ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 ) 16 4. All men are mortal. ∀ X : man ( X ) → mortal ( X ) Các hàm và vị từ khả tính toán Dùng hàm và vị từ thống kê giám sát đượ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 ? 17 Hay : alive ( Marcus, now ) OR : ¬ alive ( Marcus, now ) Các hàm và vị từ khả tính toán Dùng hàm và vị từ giám sát đượ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 18 ∀ X : ∀ T1 : ∀ T2 : died ( X, T1 ) ^ gt ( T2, T1 ) → dead ( X, T2 ) Các hàm và vị từ khả tính toán 19 Luật phân giải Thủ tục chứng tỏ chỉ dựa trên 1 phép toán – phân giải. Dạng chứng tỏ : phản chứng. Chứng minh P. bằng cách giả thiết ¬ P rồi nỗ lực đưa ra mâu thuẩn. Yêu cầu : những biểu thức phải được chuẩn hóa 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 20 ¬ Roman ( X ) v hate ( X, Ceaser ) Luật phân giải : Mệnh đề Vị từ Luật phân giải Để chứng tỏ P. từ tập F của những mệnh đề : 1. Chuyển F sang clause form 2. Lập ¬ P, chuyển ¬ P sang clause form. Thêm vào những clause ở bước 1 3. Lặp đến khi gặp mâu thuẩn, hoặc không hề đi tiếp được nữa : 1. Chọn 2 clauses ở dạng. a v C1 ¬ a v C2 21 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à vô hiệu a khỏi C1 và ¬ a khỏi C2 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 viên hoặc là người riêng biệt. Nếu Nam là chuyên viên thì Nam có nhiều báo cáo giải trình có tiếng và được đồng nghiệp an toàn và đáng tin cậy. Nếu Nam có nhiều báo cáo giải trình có tiếng thì hộp thư của Nam có nhiều thư. Nếu Nam là người riêng biệt thì Nam không được bè bạn tôn trọng. Quan sát thấy rằng, hộp thư của Nam không có nhiều thư “. 24 chứng mính : “ Nam không được bè bạn tôn trọng. “ Luật phân giải : ví dụ Các mệnh đề : P1 = “ Nam là chuyên viên ” P2 = “ Nam là người riêng biệt ” P3 = “ Nam có nhiều báo cáo giải trình có tiếng ” P4 = “ Nam được đồng nghiệp đáng tin cậy ” P5 = “ Hộp thư của Nam có nhiều thư ” P6 = “ Nam được bè bạn tôn trọng ” Các câu : 1. ( P1 ^ ¬ P2 ) v ( ¬ P1 ^ P2 ) 25 2. P1 → ( P3 ^ P4 ) 3. P3 → P5 4. P2 → ¬ P6 5. ¬ P5 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 tự : 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 29 [ hate ( X, Ceasar ) v ( ∀ Y : ∃ Z : hate ( Y, Z ) → thinkcrazy ( X, Y ) ) ] Đưa về claus form 2. Thu giảm tầm vực của ¬ vào đến mức term. Dùng tương tự : ¬ ( ¬ 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 30 ∀ X : [ ¬ roman ( X ) v ¬ know ( X, Marcus ) ] v [ hate ( X, Ceasar ) v ( ∀ Y : ∃ Z : ¬ hate ( Y, Z ) v thinkcrazy ( X, Y ) ) ] Đưa về claus form 3. Chuẩn hóa những biến để những 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. 31 ∀ X : ∀ Y : ∃ Z : [ ¬ roman ( X ) v ¬ know ( X, Marcus ) ] v [ hate ( X, Ceasar ) v ( ¬ hate ( Y, Z ) v thinkcrazy ( X, Y ) ) ] Đưa về claus form 5. Loại bỏ lượng từ sống sót : 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ừ sống sót được thay là hàm theo những biến của lượng từ với mọi trước nó Bỏ qua những 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 ảnh hưởng bởi lượng từ với mọi ( ∀ ) Ví dụ : tiếp bước 4 32 [ ¬ roman ( X ) v ¬ know ( X, Marcus ) ] v [ hate ( X, Ceasar ) v ( ¬ hate ( Y, Z ) v thinkcrazy ( X, Y ) ) ] Đưa về claus form 7. Chuyển hội chuẩn ( Conjunctive Normal Form – CNF ) Một chuỗi những mệnh đề liên kết nhau bằng quan hệ AND ( ^ ). Mỗi mệnh đề có dạng một tuyển OR ( v ) của những 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 ) 33 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 ) Đưa về claus form 8. Tách riêng những 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 những clause : 1. ( a v ¬ b ) 2. ( ¬ a v c v d ) 3. ( a v ¬ c v e ) 34 Đưa những lượng từ về từng clause ( ∀ X : P. ( X ) ^ Q ( X ) ) = ∀ X : P. ( X ) ^ ∀ X : Q. ( X ) Đưa về claus form BT : đưa về clause form những 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
