Bài giảng Trí tuệ nhân tạo: Chương 3 - PGS.TS. Lê Thanh Hương

Bài giảng "Trí tuệ nhân tạo - Chương 3: Kỹ thuật giải quyết vấn đề" cung cấp cho người học các kiến thức: Khoa học trí tuệ nhân tạo, phân loại vấn đề, các phương pháp biểu diễn vấn đề, giải quyết vấn đề,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Trí tuệ nhân tạo: Chương 3 - PGS.TS. Lê Thanh Hương3.6 Biểu diễn bằng logic hình thức vàcác phương pháp chứng minhVD1. Bài toán con khỉ - nải chuối• Tại(O,x): đối tượng O ở tại vị trí xChương 3Kỹ thuật giải quyết vấn đề(tiếp)Ban đầBđầu:tại(A,4) , tại(B,3) , tại(C,1), tại(D,2)• Trên(O1,O2): đối tượng O1 nằm trên O2Muốn:tại(B,2) , trên(C,B) , trên(A,C), trên(D,A)Lê Thanh HươngKhoa CNTT – ĐHBKHNADC11B23Logic mệnh đề (Propositional Logic)Hành động của khỉ:• tại(A,x) ⇒ tại (A,y)• tại(A,x) ∧ tại(O,x) ⇒ tại(A,y) ∧ tại(O,y)• tại(A,x) ∧ tại(O,x) ⇒ trên(A,O)• tại(A,x) ∧ tại(O1,x) ∧ tại(O2,x) ⇒trên(O1,O2)42Các toán tửCác phép toán logic• 1 mệnh đề p là 1 phát biểu chỉ có nhận giá trị đúng (true,T, 1) hoặc sai (false, F, 0)• Hội (∧(∧, and,and và)• Tuyển (∨, or, hoặc)• Phủ định (¬,∼,not, không)• liên kết với nhau tạo thành câu• Câu (well formed formulas – các công thức đúng ngữpháp)• KéoKé ththeo ((⇒))• Tương đương (⇔)Thứ tự ưu tiên: ¬ ∧ ∨ → ↔– T và F là câu– Các biến mệnh đề là câu: P, Q, R, S– Nếu φ và ψ là câu thì những biểu thức sau cũng là câu:(φ), ¬φ, φ∨ψ, φ∧ψ, φ→ψ, φ↔ψ• Các biểu thức logic mệnh đề được xây dựng trên các tênmệnh đề và các phép toán logic theo quy tắc cú phápnhất định3A∨B∧CA∨(B∧C)A∧B→C∨D(A∧B)→(C∨D)A→B∨C↔D(A→(B∨C))↔D41Ngữ nghĩaBảng chân lý• Ý nghĩa của một câu là giá trị chân lý của nó {T,F}. Ví dụP2,2P3,1P1,2,,,falsetruefalseMột số luật đánh giá giá trị chân lý:¬Sđúng nếuS saiS1 ∧ S2 đúng nếuS1 đúng vàS2 đúngS1 ∨ S2 đúng nếuếS1 đúng hoặc S2 đúng• Giá trị chân lý của một biểu thức được tính dựa trênbảngg chân lýý• Dễ thấy a⇒b ⇔ ¬a∨b ⇔ ¬b⇒¬a• ∀biểu thức logic mệnh đề đều có thể đưa về dạngbiểu thức tương đương chỉ chứa phép ∧,¬,∨¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (true ∨ false)= true ∧ true = true56Các phép biến đổi tương đươngCác phép biến đổi tương đươngHai câu có ý nghĩa tương đương nếu cùng giá trị đúng:Luật hấp thu:• (A ∨ (A ∧ B) ≡ Agiao hoán• (A ∧ (A ∨ B)) ≡ ACác luật về 0, 1:kết hợp• A∧0⇔0• A∨1⇔1• ¬1 ⇔ 0phủ định képtương phản• A∨0⇔A• A∧1⇔A• ¬0 ⇔ 1Luật bài trung:• ¬A ∨ A ⇔ 1de MorganLuật mâu thuẫn:phân phối• ¬A ∧ A ⇔ 0782Hợp giảiHợp giảiDạng kết nối chuẩn (Conjunctive Normal Form - CNF)E.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)• Luật hợp giải (Các câu cần được chuyển sangdạng kết nối chuẩn trước khi hợp giải)α∨β¬β ∨ γ• Luật hợp giải cho CNF:m1 ∨ … ∨ m nl1 ∨… ∨ lk,l1 ∨ … ∨ li-1 ∨ li+1 ∨ … ∨ lk ∨ m1 ∨ … ∨ mj-1 ∨ mj+1 ∨... ∨mnα∨γ• Chứng minh KL: thêm ¬KL vào CSTT để xemcó xung đột không• Áp dụng hợp giải đến khi xuất hiện mâuthuẫntrong đó li và mj bù nhauE.g., P1,3 ∨ P2,2, ¬P2,2P1,3910Chuyển đổi sang CNFVí dụB1,1 ⇔ (P1,2 ∨ P2,1)(A∨B)→(C→D)1. Loại bỏ phép ⇔, thay α ⇔ β bằngằ (α ⇒ β)∧(β ⇒ α).(B1,1 ⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1)1. Loại bỏ phép suy ra¬(A∨B)∨(¬C∨D)2. Loại bỏ phép ⇒, thay α ⇒ β bằng ¬α∨ β.(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬(P1,2 ∨ P2,1) ∨ B1,1)3 Đưa ¬ vào trong sử dụng luật de Morgan và phủ định kép:3.(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ ((¬P1,2 ∧ ¬P2,1) ∨ B1,1)4. Áp dụng luật phân phối đối với phép ∧ :(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬P1,2 ∨ B1,1) ∧ (¬P2,1 ∨ B1,1)112. Chuyển phủ định vào trong ngoặc( A B) ( C D)(¬A∧¬B)∨(¬C∨D)3. Phân phối(¬A∨¬C∨D)∧(¬B∨¬C∨D)123Thuật toán hợp giải củaRobinsonVí dụChuyển đổi các công thức sau về dạng kết nốichuẩn:Chứng minh bằng phản chứng: CSTT ∧¬KL không thoảmãn1. P ∨ (¬P ∧ Q ∧ R)2. (¬P ∧ Q) ∨ (P ∧ ¬Q)3. ¬(P ⇒ Q) ∨ (P ∨ Q)4. (P ⇒ Q) ⇒ R5. (P ⇒(Q ⇒ R)) ⇒ ((P ∧ S) ⇒ R)6. (P ∧ (Q ⇒ R)) ⇒ S7. P ∧ Q ⇒ R ∧ S13Thuật toán hợp giải của RobinsonChứng minh bằng phản chứng: CSTT ∧¬KL không thoả mãnGiả sử có GT1, GT2,…,GTn. Cần CM KL → phản chứngGT1…>