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

3.6 Biểu diễn bằng logic hình thức và<br /> các phương pháp chứng minh<br /> VD1. Bài toán con khỉ - nải chuối<br /> • Tại(O,x): đối tượng O ở tại vị trí x<br /> <br /> Chương 3<br /> Kỹ thuật giải quyết vấn đề<br /> (tiếp)<br /> <br /> Ban đầ<br /> B<br /> đầu:<br /> tại(A,4) , tại(B,3) , tại(C,1), tại(D,2)<br /> • Trên(O1,O2): đối tượng O1 nằm trên O2<br /> Muốn:<br /> tại(B,2) , trên(C,B) , trên(A,C), trên(D,A)<br /> <br /> Lê Thanh Hương<br /> Khoa CNTT – ĐHBKHN<br /> <br /> A<br /> D<br /> C<br /> <br /> 1<br /> <br /> 1<br /> <br /> B<br /> 2<br /> <br /> 3<br /> <br /> Logic mệnh đề (Propositional Logic)<br /> <br /> Hành động của khỉ:<br /> • tại(A,x) ⇒ tại (A,y)<br /> • tại(A,x) ∧ tại(O,x) ⇒ tại(A,y) ∧ tại(O,y)<br /> • tại(A,x) ∧ tại(O,x) ⇒ trên(A,O)<br /> • tại(A,x) ∧ tại(O1,x) ∧ tại(O2,x) ⇒<br /> trên(O1,O2)<br /> <br /> 4<br /> <br /> 2<br /> <br /> Các toán tử<br /> Các phép toán logic<br /> <br /> • 1 mệnh đề p là 1 phát biểu chỉ có nhận giá trị đúng (true,<br /> T, 1) hoặc sai (false, F, 0)<br /> <br /> • Hội (∧<br /> (∧, and,<br /> and và)<br /> • Tuyển (∨, or, hoặc)<br /> • Phủ định (¬,∼,not, không)<br /> <br /> • liên kết với nhau tạo thành câu<br /> • Câu (well formed formulas – các công thức đúng ngữ<br /> pháp)<br /> <br /> • Kéo<br /> Ké th<br /> theo ((⇒))<br /> • Tương đương (⇔)<br /> <br /> Thứ tự ưu tiên: ¬ ∧ ∨ → ↔<br /> <br /> – T và F là câu<br /> – Các biến mệnh đề là câu: P, Q, R, S<br /> – Nếu φ và ψ là câu thì những biểu thức sau cũng là câu:<br /> (φ), ¬φ, φ∨ψ, φ∧ψ, φ→ψ, φ↔ψ<br /> • Các biểu thức logic mệnh đề được xây dựng trên các tên<br /> mệnh đề và các phép toán logic theo quy tắc cú pháp<br /> nhất định<br /> 3<br /> <br /> A∨B∧C<br /> <br /> A∨(B∧C)<br /> <br /> A∧B→C∨D<br /> <br /> (A∧B)→(C∨D)<br /> <br /> A→B∨C↔D<br /> <br /> (A→(B∨C))↔D<br /> 4<br /> <br /> 1<br /> <br /> Ngữ nghĩa<br /> <br /> Bảng chân lý<br /> <br /> • Ý nghĩa của một câu là giá trị chân lý của nó {T,F}. Ví dụ<br /> P2,2<br /> P3,1<br /> P1,2<br /> ,<br /> ,<br /> ,<br /> false<br /> true<br /> false<br /> Một số luật đánh giá giá trị chân lý:<br /> ¬S<br /> đúng nếu<br /> S sai<br /> S1 ∧ S2 đúng nếu<br /> S1 đúng và<br /> S2 đúng<br /> S1 ∨ S2 đúng nếu<br /> ế<br /> S1 đúng hoặc S2 đúng<br /> <br /> • Giá trị chân lý của một biểu thức được tính dựa trên<br /> bảng<br /> g chân lý<br /> ý<br /> <br /> • Dễ thấy a⇒b ⇔ ¬a∨b ⇔ ¬b⇒¬a<br /> • ∀biểu thức logic mệnh đề đều có thể đưa về dạng<br /> biểu thức tương đương chỉ chứa phép ∧,¬,∨<br /> <br /> ¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (true ∨ false)<br /> = true ∧ true = true<br /> 5<br /> <br /> 6<br /> <br /> Các phép biến đổi tương đương<br /> <br /> Các phép biến đổi tương đương<br /> Hai câu có ý nghĩa tương đương nếu cùng giá trị đúng:<br /> <br /> Luật hấp thu:<br /> • (A ∨ (A ∧ B) ≡ A<br /> <br /> giao hoán<br /> <br /> • (A ∧ (A ∨ B)) ≡ A<br /> <br /> Các luật về 0, 1:<br /> <br /> kết hợp<br /> <br /> • A∧0⇔0<br /> • A∨1⇔1<br /> • ¬1 ⇔ 0<br /> <br /> phủ định kép<br /> tương phản<br /> <br /> • A∨0⇔A<br /> • A∧1⇔A<br /> • ¬0 ⇔ 1<br /> <br /> Luật bài trung:<br /> • ¬A ∨ A ⇔ 1<br /> <br /> de Morgan<br /> <br /> Luật mâu thuẫn:<br /> <br /> phân phối<br /> <br /> • ¬A ∧ A ⇔ 0<br /> 7<br /> <br /> 8<br /> <br /> 2<br /> <br /> Hợp giải<br /> <br /> Hợp giải<br /> <br /> Dạng kết nối chuẩn (Conjunctive Normal Form - CNF)<br /> E.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)<br /> <br /> • Luật hợp giải (Các câu cần được chuyển sang<br /> dạng kết nối chuẩn trước khi hợp giải)<br /> <br /> α∨β<br /> ¬β ∨ γ<br /> <br /> • Luật hợp giải cho CNF:<br /> m1 ∨ … ∨ m n<br /> l1 ∨… ∨ lk,<br /> l1 ∨ … ∨ li-1 ∨ li+1 ∨ … ∨ lk ∨ m1 ∨ … ∨ mj-1 ∨ mj+1 ∨... ∨<br /> mn<br /> <br /> α∨γ<br /> • Chứng minh KL: thêm ¬KL vào CSTT để xem<br /> có xung đột không<br /> • Áp dụng hợp giải đến khi xuất hiện mâu<br /> thuẫn<br /> <br /> trong đó li và mj bù nhau<br /> E.g., P1,3 ∨ P2,2, ¬P2,2<br /> P1,3<br /> 9<br /> <br /> 10<br /> <br /> Chuyển đổi sang CNF<br /> <br /> Ví dụ<br /> <br /> B1,1 ⇔ (P1,2 ∨ P2,1)<br /> <br /> (A∨B)→(C→D)<br /> <br /> 1. Loại bỏ phép ⇔, thay α ⇔ β bằng<br /> ằ (α ⇒ β)∧(β ⇒ α).<br /> (B1,1 ⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1)<br /> <br /> 1. Loại bỏ phép suy ra<br /> ¬(A∨B)∨(¬C∨D)<br /> <br /> 2. Loại bỏ phép ⇒, thay α ⇒ β bằng ¬α∨ β.<br /> (¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬(P1,2 ∨ P2,1) ∨ B1,1)<br /> 3 Đưa ¬ vào trong sử dụng luật de Morgan và phủ định kép:<br /> 3.<br /> (¬B1,1 ∨ P1,2 ∨ P2,1) ∧ ((¬P1,2 ∧ ¬P2,1) ∨ B1,1)<br /> 4. Áp dụng luật phân phối đối với phép ∧ :<br /> (¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬P1,2 ∨ B1,1) ∧ (¬P2,1 ∨ B1,1)<br /> 11<br /> <br /> 2. Chuyển phủ định vào trong ngoặc<br /> ( A B) ( C D)<br /> (¬A∧¬B)∨(¬C∨D)<br /> 3. Phân phối<br /> (¬A∨¬C∨D)∧(¬B∨¬C∨D)<br /> 12<br /> <br /> 3<br /> <br /> Thuật toán hợp giải của<br /> Robinson<br /> <br /> Ví dụ<br /> Chuyển đổi các công thức sau về dạng kết nối<br /> chuẩn:<br /> <br /> Chứng minh bằng phản chứng: CSTT ∧¬KL không thoả<br /> mãn<br /> <br /> 1. P ∨ (¬P ∧ Q ∧ R)<br /> 2. (¬P ∧ Q) ∨ (P ∧ ¬Q)<br /> 3. ¬(P ⇒ Q) ∨ (P ∨ Q)<br /> 4. (P ⇒ Q) ⇒ R<br /> 5. (P ⇒(Q ⇒ R)) ⇒ ((P ∧ S) ⇒ R)<br /> 6. (P ∧ (Q ⇒ R)) ⇒ S<br /> 7. P ∧ Q ⇒ R ∧ S<br /> 13<br /> <br /> Thuật toán hợp giải của Robinson<br /> Chứng minh bằng phản chứng: CSTT ∧¬KL không thoả mãn<br /> Giả sử có GT1, GT2,…,GTn. Cần CM KL → phản chứng<br /> GT1<br /> …<br /> ><<br /> GTn<br /> ¬KL<br /> Viết mỗi GTi, ¬KL trên 1 dòng<br /> Đưa GTi, ¬KL về dạng chuẩn CNF<br /> ( 1∨…∨pn) ∧ (q<br /> (p<br /> ( 1∨…∨qn) (*)<br /> Tách mỗi dòng (*) thành các dòng con:<br /> p1∨…∨pn<br /> q1∨…∨qn<br /> 15<br /> <br /> 14<br /> <br /> Thuật toán hợp giải của Robinson<br /> Xét 1 cặp dòng<br /> u) ¬p∨q<br /> v) p∨r<br /> <br /> Hợp giải:<br /> w) q∨r<br /> <br /> Vô lý xuất hiện khi<br /> i) ¬t<br /> ii) t<br /> <br /> ⇒ đpcm<br /> 16<br /> <br /> 4<br /> <br /> Ví dụ<br /> <br /> Ví dụ<br /> VD1:<br /> 1. a<br /> 2. a→b<br /> 3. b→(c→d)<br /> 4. c<br /> Chứng minh d<br /> <br /> VD3:<br /> 1. p<br /> 2. p→q<br /> 3. q∧r∧s→t<br /> 4. p→u<br /> 5. v→w<br /> 6 u→v<br /> 6.<br /> 7. v→t<br /> <br /> VD2:<br /> 1. a∧b→c<br /> 2. b∧c →d<br /> 3. a<br /> 4. b<br /> Chứng minh d<br /> <br /> VD4:<br /> ((a∨b)∧c)→(c∧d)<br /> ) ) (<br /> )<br /> 1. ((<br /> 2. a∧m∧d→f<br /> 3. m→b∧c<br /> 4. a→c<br /> 5. (a∧f)→(¬e∨g)<br /> 6 (m∧f)→g<br /> 6.<br /> Cho a,m. CM g<br /> <br /> Cho r,s. CM t<br /> 17<br /> <br /> Logic vị từ cấp 1<br /> (First Order Logic – FOL)<br /> <br /> Ví dụ 5<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> 6.<br /> <br /> 18<br /> <br /> a1 ∨ a2 ⇒ a3 ∨ a4<br /> a1 ⇒ a5<br /> a2 ∧ a3 ⇒ a5<br /> a2 ∧ a4 ⇒ a6 ∧ a7<br /> a5 ⇒ a7<br /> a1 ∧ a3 ⇒ a6 ∨ a7<br /> <br /> • Cho các mệnh đề<br /> ề a1, a2 đúng.<br /> • Đưa các biểu thức logic trên về dạng chuẩn<br /> • áp dụng phương pháp hợp giải của Robinson, chứng<br /> minh a7 đúng.<br /> 19<br /> <br /> • Logic mệnh đề chỉ xử lý thông tin kiểu sự kiện đúng hoặc sai<br /> như “trời<br /> trời mưa”<br /> mưa .<br /> • Với logic vị từ cấp 1, biến được dùng thay cho các đối tượng<br /> cụ thể.<br /> • FOL cho phép biểu diễn các đối tượng, thuộc tính của đối<br /> tượng, và quan hệ giữa các đối tượng.<br /> • Vị từ p(x,…y) là một phát biểu chứa các biến x,…y sao cho<br /> khi x,…y nhận giá trị cụ thể thì p(x,…y) nhận giá trị đúng hoặc<br /> sai<br /> sai.<br /> • VD. Nếu p(x,y,z) nghĩa là x.y = z thì tính chất giao hoán của<br /> phép nhân x.y = y.x được biểu diễn dưới dạng<br /> ∀x,y p(x,y,z) ⇒ p(y,x,z)<br /> • Logic vị từ cấp 1 còn sử dụng thêm các toán tử ∃, ∀<br /> 20<br /> <br /> 5<br /> <br />