Bài giảng Trí tuệ nhân tạo - Chương 3: Kĩ thuật giải quyết vấn đề (Tiếp theo) - Lê Thanh Hương

1Chương 3 Kỹ thuật giải quyết vấn đề (tiếp) Lê Thanh Hương 1 Khoa CNTT – ĐHBKHN 3.6 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 B đầ • Tại(O,x): đối tượng O ở tại vị trí x an u: Muốn: 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,4) , tại(B,3) , tại(C,1), tại(D,2) tại(B,2) , trên(C,B), trên(A,C), trên(D,A) • Trên(O1,O2): đối tượng O1 nằm trên O2 21 2 3 4 C D B A • 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) Logic mệnh đề (Propositional 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) • 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) – T và F là câu – Các biến mệnh đề là câu: P, Q, R, S 3 – 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 Các toán tử • Hội (∧ and và) Ké th ( ) Các phép toán logic , , • Tuyển (∨, or, hoặc) • Phủ định (¬,∼,not, không) A∨B∧C A∨(B∧C) Thứ tự ưu tiên: ¬ ∧ ∨ → ↔ • o eo ⇒ • Tương đương (⇔) 4 A∧B→C∨D (A∧B)→(C∨D) A→B∨C↔D (A→(B∨C))↔D 2Ngữ nghĩa • Ý nghĩa của một câu là giá trị chân lý của nó {T,F}. Ví dụ P1,2 P2,2 P3,1 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 ế 5 S1 ∨ S2 đúng n u S1 đúng hoặc S2 đúng ¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (true ∨ false) = true ∧ true = true Bảng chân lý • Giá trị chân lý của một biểu thức được tính dựa trên bảng chân lý 6 • 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 ∧,¬,∨ 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: giao hoán kết hợp phủ định kép tương phản 7 de Morgan phân phối Các phép biến đổi tương đương Luật hấp thu: • (A ∨ (A ∧ B) ≡ A • (A ∧ (A ∨ B)) ≡ A Các luật về 0, 1: • A ∧ 0 ⇔ 0 • A ∨ 1 ⇔ 1 • ¬1 ⇔ 0 • A ∨ 0 ⇔ A • A ∧ 1 ⇔ A • ¬0 ⇔ 1 Luật bài trung: 8 • ¬A ∨A ⇔ 1 Luật mâu thuẫn: • ¬A ∧A ⇔ 0 3Hợp giải • Luật hợp giải (Các câu cần được chuyển sang dạng kết nối chuẩn trước khi hợp giải) βα ∨ ¬β ∨ γ α ∨ γ • Chứng minh KL: thêm ¬KL vào CSTT để xem có xung đột không 9 • Áp dụng hợp giải đến khi xuất hiện mâu thuẫn Hợp giải Dạng kết nối chuẩn (Conjunctive Normal Form - CNF) E.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D) • Luật hợp giải cho CNF: l1 ∨ ∨ lk, m1 ∨ ∨ mn l1 ∨ ∨ li-1 ∨ li+1 ∨ ∨ lk ∨ m1 ∨ ∨ mj-1 ∨ mj+1 ∨... ∨ mn trong đó l và m bù nhau 10 i j E.g., P1,3 ∨ P2,2, ¬P2,2 P1,3 Chuyển đổi sang CNF B1,1 ⇔ (P1,2 ∨ P2,1) ằ1. Loại bỏ phép ⇔, thay α ⇔ β b ng (α ⇒ β)∧(β ⇒ α). (B1,1⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1) 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: 11 . ¬ (¬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) Ví dụ (A∨B)→(C→D) 1. Loại bỏ phép suy ra ¬(A∨B)∨(¬C∨D) 2. Chuyển phủ định vào trong ngoặc ( A B) ( C D) 12 ¬ ∧¬ ∨ ¬ ∨ 3. Phân phối (¬A∨¬C∨D)∧(¬B∨¬C∨D) 4Ví dụ Chuyển đổi các công thức sau về dạng kết nối chuẩn: 1. P ∨ (¬P ∧ Q ∧ R) 2. (¬P ∧ Q) ∨ (P ∧ ¬Q) 3. ¬(P ⇒ Q) ∨ (P ∨ Q) 4. (P ⇒ Q) ⇒ R 13 5. (P ⇒(Q ⇒ R)) ⇒ ((P ∧ S) ⇒ R) 6. (P ∧ (Q ⇒ R)) ⇒ S 7. P ∧ Q ⇒ R ∧ S Thuật toán hợp giải của Robinson Chứng minh bằng phản chứng: CSTT ∧¬KL không thoả mãn 14 Thuật toán hợp giải của Robinson Chứng minh bằng phản chứng: CSTT ∧¬KL không thoả mãn Giả sử có GT1, GT2,,GTn. Cần CM KL → phản chứng GT1 >< GTn ¬KL Viết mỗi GTi, ¬KL trên 1 dòng Đưa GTi, ¬KL về dạng chuẩn CNF ( ) ( ) (*) 15 p1∨∨pn ∧ q1∨∨qn Tách mỗi dòng (*) thành các dòng con: p1∨∨pn q1∨∨qn Thuật toán hợp giải của Robinson Xét 1 cặp dòng u) ¬p∨q v) p∨r Hợp giải: w) q∨r Vô lý xuất hiện khi i) ¬t 16 ii) t ⇒ đpcm 5Ví dụ VD1: VD2: 1. a 2. a→b 3. b→(c→d) 4. c 1. a∧b→c 2. b∧c →d 3. a 4. b Chứng minh d 17 Chứng minh d Ví dụ VD3: 1. p VD4: 1. ((a∨b)∧c)→(c∧d) 2. p→q 3. q∧r∧s→t 4. p→u 5. v→w 6 u→v 2. a∧m∧d→f 3. m→b∧c 4. a→c 5. (a∧f)→(¬e∨g) 6 (m∧f)→g 18 . 7. v→t Cho r,s. CM t . Cho a,m. CM g Ví dụ 5 1. a1 ∨ a2 ⇒ a3 ∨ a4 2. a1 ⇒ a5 3. a2 ∧ a3 ⇒ a5 4. a2 ∧ a4 ⇒ a6 ∧ a7 5. a5 ⇒ a7 6. a1 ∧ a3 ⇒ a6 ∨ a7 ề 19 • Cho các mệnh đ a1, a2 đúng. • Đưa các biểu thức logic trên về dạng chuẩn • áp dụng phương pháp hợp giải của Robinson, chứng minh a7 đúng. Logic vị từ cấp 1 (First Order Logic – FOL) • Logic mệnh đề chỉ xử lý thông tin kiểu sự kiện đúng hoặc sai như “trời mưa” . • Với logic vị từ cấp 1, biến được dùng thay cho các đối tượng cụ thể. • FOL cho phép biểu diễn các đối tượng, thuộc tính của đối tượng, và quan hệ giữa các đối tượng. • Vị từ p(x,y) là một phát biểu chứa các biến x,y sao cho khi x,y nhận giá trị cụ thể thì p(x,y) nhận giá trị đúng hoặc sai 20 . • VD. Nếu p(x,y,z) nghĩa là x.y = z thì tính chất giao hoán của phép nhân x.y = y.x được biểu diễn dưới dạng ∀x,y p(x,y,z) ⇒ p(y,x,z) • Logic vị từ cấp 1 còn sử dụng thêm các toán tử ∃, ∀ 6Chuyển đổi câu sang dạng logic vị từ 21 1. Loại bỏ dấu suy ra α↔β⇒(α→β)∧(β→α) Các phép biến đổi tương đương α→β⇒¬α∨β 2. Chuyển phủ định vào trong ngoặc ¬(α∨β)⇒¬α∧¬β ¬(α∧β)⇒¬α∨¬β ¬¬α⇒α ∀x α⇒∃x α 22 ¬ , ,¬ ¬∃x,α⇒∀x,¬α 3. Đặt tên các biến khác nhau ∀x, ∃y,(¬P(x)∨∃x,Q(x,y))⇒∀x1,∃x2,(¬P(x1)∨∃x3,Q(x3,y2) Phép gán trị VD: Định lý đường trung bình: r1: trđ(U XY) ∧ trđ(V XZ)⇒ ss(UV YZ) , , , X U V A L I 23 Phép gán trị θ ={A/X,B/Z,D/Y,L/U,I/V}: • r1θ: trđ(L,AD) ∧ trđ(I,AB) ⇒ ss(LI,DB) Y Z D B Hợp giải Robinson cho logic vị từ 1. Viết mỗi GTi, ¬KL trên 1 dòng 2. Đưa GTi, ¬KL về dạng chuẩn CNF ∀x1∀x2∀xn [p1()∨∨pn()] ∧ [q1()∨∨qm()] (*) 3 Tách mỗi dòng (*) thành các dòng con:. ∀x1∀x2∀xn [p1()∨∨pn()] ∀x1∀x2∀xn [q1()∨∨qm()] tất cả đều với ∀ 4. Hợp giải: u) ¬p(x1,x2,,xn) ∨ q() ⇒ w) q() ∨ r() với phép gán trị 24 v) p(y1,y2,,yn) ∨ r() 5. Vô lý xảy ra khi i) ¬p(x1,x2,,xn) ii) p(y1,y2,,yn) với phép gán trị { } n n n n y z x z y z x z ,,...,, 1 1 1 1=θ { } n n n n y z x z y z x z ,,...,, 1 1 1 1=θ 7Ví dụ về bước 4 • Sử dụng phép gán trị nào để hợp giải P(a,x,b), và ¬P(y,z,z) ⎭⎬ ⎫ ⎩⎨ ⎧ x b z b y a ,,Phép gán trị θ = 25 • P(a,b,b) • ¬P(a,b,b) Ví dụ về bước 4 (tiếp) • Sử dụng phép gán trị nào để hợp giải P(a,x,x,b), và ¬P(y,y,z,b) 26 Ví dụ về bước 4 (tiếp) • Cho các sự kiện p(a,b), p(c,d), q(d,c,c) đúng • Cho luật p(x,y) ∧ q(y,x,x) ⇒ r(x,y) • Sử dụng các phép gán trị với luật trên, hãy đưa ra các sự kiện mới đúng. • Gợi ý: Thử ới ( ) ( b) h ặ ( ) ( d) 27 – v p x,y ≡ p a, o c p x,y ≡ p c, Ví dụ về hợp giải Hợp giải 1 và 3 )()( )()( RP xQxPx ∀ →∀ )()(1 xQxP ∨ )()(.5 xSxP ∨¬ Hợp giải 2 và 5 )()(.6 xSxR ∨ Chuyển về dạng chuẩn )()( )()( xSxRx xSxQx xxx →∀ →∀ →¬ 28 )()(.4 )()(.3 )()(.2 . xSxR xSxQ xRxP ∨¬ ∨¬ ∨ ¬ Hợp giải 4 và 6 )(.7 xS 8Bài toán con khỉ - nải chuối • tại(C,1) • tại(B,3) • tại(A,4) • tại(D,2) • 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) 1 2 3 4 C D B A 29 • , ∧ , ⇒ , • tại(A,x) ∧ tại(O1,x) ∧ tại(O2,x) ⇒ trên(O1,O2) KL: tại(B,2) ∧ trên(C,B) ∧ trên(A,C) ∧ trên(D,A) ¬KL: ¬ tại(B,2) ∨ ¬ trên(C,B) ∨ ¬ trên(A,C) ∨ ¬ trên(D,A) Bài tập • Cho tập các phát biểu: – John owns a dog – Anyone who owns a dog is a lover of animals – Lovers of animals do not kill animals • Chứng minh: – John does not kill animals. 30 Bài tập • Nếu xem một ai đó lừa dối người khác là kẻ bịp bợm và bất kỳ ai đồng tình với kẻ bịp bợm cũng là kẻ bịp bợm. Trong tập thể có một người nhút nhát đồng tình với kẻ lừa dối thì chắc chắn có 1 tên bịp bợm tính tình nhút nhát. 31 Nhận xét • Thuật giải Robinson vẫn vấp phải sự bùng nổ tổ hợp. Có thể áp dụng các heuristics: – Chiến lược ưu tiên các biểu thức đơn – Chiến lược đơn giản hóa các biểu thức – Chiến lược giảm số lần hợp giải – Chiến lược sắp thứ tự các hợp giải – Chiến lược tập tựa • Thuật giải Robinson được áp dụng trong CM định lý 32 tự động. 2 nhược điểm: – con người không tư duy theo cách này – chúng ta bị mất ngữ nghĩa và nội dung thông tin khi chuyển về dạng câu CNF 93.7 Một số phương pháp GQVĐ khác • Phương pháp thử và sai (test & set) • Phương pháp giải quyết bài toán tổng quát (General Problem Solving - GPS) • Phương pháp thỏa mãn ràng buộc (Constraint S ti fi ti M th d) 33 a s ca on e o Lê Thanh Hương – Khoa CNTT - ĐHBKHN 3.7.1 Phương pháp thử và sai (test & set) • Xuất phát từ n0 : Mở = {n0}; Đóng = ∅ ầ ố• Lan d n xu ng • Bí quyết: tại mỗi thời điểm, chọn n ∈ Mở để xét: • Mở = queue: d(n) min • Mở = stack: d(n) ? • TKCT: g(n) = c(n0,n) min n0 34 • TKCT*: f(n) = g(n) + h(n) min • Thử và sai: n ← get random(Mở) Đích Đóng (đã) Γ(n) n Lê Thanh Hương – Khoa CNTT - ĐHBKHN 3.7.2 Phương pháp GPS Về lý thuyết tốt nhất, trên thực tế không tốt lắm TKCT*: Lấy n ∈ Mở: f(n) = g(n) + h(n) min GPS: • Với ∀n ∈ Mở, xác định sự khác biệt giữa n và Đích: Δ = {δ1, , δm} • Chọn sự khác biệt quan trọng nhất δi. • Chọn biện pháp Oj phù hợp để giảm sự khác biệt δj bằng cách: – Xác định tập các phép biến đổi (toán tử) trong không gian O={O1, , On} – Xây dựng ma trân M với các cột là các toán tử, các hàng là 35 các sự khác biệt: M = (mij), i=1÷m, j = 1÷n mij = 1 nếu Oj làm giảm δi 0 nếu ngược lại Lê Thanh Hương – Khoa CNTT - ĐHBKHN 3.7.3 Phương pháp thỏa mãn ràng buộc • Mục đích: Tìm các trạng thái bài toán sao cho thỏa mãn tập ràng buộc nào đó • Quá trình tìm lời giải gồm 2 phần: – Tìm kiếm trong KGBT các ràng buộc – Tìm kiếm trong KGBT ban đầu Nội dung: Thực hiện 1 → 5 cho đến khi tìm được lời giải đầy đủ hoặc khi tất cả các đường đều đã duyệt nhưng không cho kết quả. 1. Cho 1 đỉnh n ∈ MO 2. Áp dụng các luật suy dẫn với các ràng buộc vào đỉnh đã chọn để sinh ra tất cả các ràng buộc mới có thể có 3 Nế tập các ràng b ộc mới có mâ th ẫn thông báo đ ờng đi hiện 36 . u u u u → ư tại đi vào ngõ cụt 4. Nếu tập ràng buộc mô tả lời giải đầy đủ của bài toán → dừng, thông báo “thành công”. Ngược lại sang bước 5. 5. AD các luật trong KGTT, tạo các lời giải bộ phận phù hợp với tập các ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tìm kiếm. Lê Thanh Hương – Khoa CNTT - ĐHBKHN