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 đề,. . | Biểu diễn bằng logic hình thức và các phương pháp chứng minh VD1. Bài toán con khỉ - nải chuối • Tại(O,x): đối tượng O ở tại vị trí x Chương 3 Kỹ 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 O2 Muốn: tại(B,2) , trên(C,B) , trên(A,C), trên(D,A) Lê Thanh Hương Khoa CNTT – ĐHBKHN A D C 1 1 B 2 3 Logic 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) 4 2 Cá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éo Ké th theo ((⇒)) • 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ên mệnh đề và các phép toán logic theo quy tắc cú pháp nhất định 3 A∨B∧C A∨(B∧C) A∧B→C∨D (A∧B)→(C∨D) A→B∨C↔D (A→(B∨C))↔D 4 1 Ngữ nghĩa Bả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,2 P3,1 P1,2 , , , false true false Một số luật đánh giá giá trị chân lý: ¬S đúng nếu S sai S1 ∧ S2 đúng nếu S1 đúng và S2 đúng S1 ∨ 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ên bảng g 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ạng biểu thức tương đương chỉ chứa phép ∧,¬,∨ ¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (true ∨ false) = true ∧ true = true 5 6 Các phép biến đổi tương đương Các phép biến đổi tương đương Hai câu có ý nghĩa tương đương nếu cùng giá trị đúng: Luật hấp thu: • (A ∨ (A ∧ B) ≡ A giao hoán • (A ∧ (A ∨ B)) ≡ A Các
