Bài giảng Luận lý toán học - Chương 2: Luận lý mệnh đề - Nguyễn Thanh Sơn (Phần 2)

82 trang hapham 1860

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Luận lý toán học - Chương 2: Luận lý mệnh đề - Nguyễn Thanh Sơn (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_luan_ly_toan_hoc_chuong_2_luan_ly_menh_de_nguyen_t.pdf

Nội dung text: Bài giảng Luận lý toán học - Chương 2: Luận lý mệnh đề - Nguyễn Thanh Sơn (Phần 2)

III. Ngữ nghĩa của luận lý mệnh đề Chương 2 ntsơn
Gán thực trị[*] • Môi trường (Environments) Gán thực trị là gán giá trị T (đúng) hoặc F (sai) cho mỗi biến mệnh đề. Những nhà khoa học máy tính gọi việc gán giá trị cho các biến là một môi trường. [*] Sept. 10, 2007 Copyright © Albert R. Meyer, 2007. All rights reserved. lec 2M.17 @Nguyễn Thanh Sơn ntsơn
Gán thực trị Thí dụ : công thức P → (Q ∨ R) Môi trường ν gán các biến P, Q, R : ν(P) = T, ν(Q)= T, ν(R) = F. Môi trường µ gán các biến P, Q, R : µ(P) = F, µ(Q)= T, µ(R) = F. @Nguyễn Thanh Sơn ntsơn
Diễn dịch • Diễn dịch của một công thức là thế giới thực cùng với cách nhúng từng yếu tố của công thức vào thế giới thực đó. • Nói cách khác diễn dịch là “gán” cho công thức một ý nghĩa của thế giới thực mà công thức được nhúng vào. @Nguyễn Thanh Sơn ntsơn
Diễn dịch • Có tác giả định nghĩa diễn dịch là cách đánh giá công thức và được đặc trưng bằng hàm đánh giá. • Một số tài liệu định nghĩa khái niệm diễn dịch của một lớp các công thức thay vì của một công thức. @Nguyễn Thanh Sơn ntsơn
Diễn dịch • Diễn dịch trong LLMĐ có hữu hạn trường hợp đánh giá. A sai, B đúng A sai, B sai (A ∧ B) → ¬A A sai, B sai A đúng, B đúng A đúng, B sai • Số trường hợp tương ứng với với số dòng của bảng thực trị. @Nguyễn Thanh Sơn ntsơn
Diễn dịch • Có thể đặc trưng diễn dịch của một CT bằng 1 hàm đánh giá ν trên các CTN có trong công thức. Thí dụ : Qui ước CT đúng có giá trị 1 và sai là 0. Công thức (P ∧ Q) → R có diễn dịch I được đặc trưng bằng hàm đánh giá ν như sau : ν(P) = 1, ν(Q) = 0, ν(R) = 1. • Để tiện cho việc trình bày, còn sử dụng ký hiệu νF thay cho ν(F). @Nguyễn Thanh Sơn ntsơn
Thực trị của một công thức • Nếu νA = 1, νB = 0 và νC = 0 thì ν((A→B) ∧ (C ∨¬A)) là đúng hay sai ?. Nếu νA = 0, νB = 1 và νC = 0 thì ν((¬A ∨ B) → ¬C) là đúng hay sai ?. Nếu νA = 0, νB = 1, νC = 0 và νD = 1 thì ν(((A ∨ C) ∧ B) → ¬D) là đúng hay sai.  Cần phải xác định qui tắc đánh giá của các toán tử : ∨, ∧, ¬, →. @Nguyễn Thanh Sơn ntsơn
Bảng thực trị • P, Q là các công thức nguyên. P Q ¬P P∨Q P∧Q P→Q 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 • Tất cả diễn dịch của một công thức trong LLMĐ tướng ứng với các dòng của bảng thực trị. @Nguyễn Thanh Sơn ntsơn
Bảng thực trị • P → Q, tại sao đ → đ là đ, đ → s là s, s → đ là đ, s → s là đ ???. Thí dụ : P = Trời mưa, Q = Vũ mang dù. Tình trạng 1 : Trời mưa và Vũ mang dù. Tình trạng 2 : Trời mưa và Vũ không mang dù. Tình trạng 3 : Trời không mưa và Vũ mang dù. Tình trạng 4 : Trời khg mưa và Vũ khg mangdù. Nguyên tắc không vi phạm. @Nguyễn Thanh Sơn ntsơn
Bảng thực trị • Một cách định nghĩa khác, bảng thực trị là một hàm trên tập 2 phần tử đúng, sai ({đ, s}). • Các toán tử luận lý là các hàm : ¬ : {đ, s} → {đ, s} ∧ : {đ, s} × {đ, s} → {đ, s} ∨ : {đ, s} × {đ, s} → {đ, s} → : {đ, s} × {đ, s} → {đ, s} @Nguyễn Thanh Sơn ntsơn
Thực trị của một công thức Thí dụ : Tính thực trị của công thức (X → (¬Y∨Z)) ∧ ¬X X Y Z ¬Y∨Z X→(¬Y∨Z) CT 1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 1 @Nguyễn Thanh Sơn ntsơn
Thủ tục số học @Nguyễn Thanh Sơn ntsơn
Thực trị của một công thức Thí dụ : tính thực trị của công thức (X → (¬Y ∨ Z)) ∧ ¬X ν((X → (¬Y ∨ Z)) ∧ ¬X) = ν(X → (¬Y ∨ Z))ν(¬X) = (1 + νX + νXν(¬Y ∨ Z))ν(¬X) = (1 + νX + νX.(ν(¬Y) + νZ + ν(¬Y)νZ))ν(¬X) = (1 + νX + νXν(¬Y) + νXνZ + νXν(¬Y)νZ)ν(¬X) = ν(¬X) + ν(¬X)νX + ν(¬X)νXν(¬Y) + ν(¬X)νXνZ + ν(¬X)νXν(¬Y)νZ = ν(¬X) + 0 + 0.ν(¬Y) + 0.νZ + 0.ν(¬Y)νZ = ν(¬X) = 1 + νX. @Nguyễn Thanh Sơn ntsơn
Thủ tục số học • Một phó sản của phương pháp số học là loại bỏ khỏi những công thức nguyên không ảnh hưởng đến việc tính thực trị. @Nguyễn Thanh Sơn ntsơn
Cây phân tích • Đánh giá công thức nhờ cây phân tích. Thí dụ : Đánh giá công thức (X → (¬Y ∨ Z)) ∧ ¬X, với X, Y, Z lần lượt có giá trs ị đ, s, đ. ∧ s đ → ¬ đ đ đ X ∨ X đ ¬ Z đ s Y @Nguyễn Thanh Sơn ntsơn
Phân loại công thức • I là diễn dịch của công thức X. X hằng đúng ↔ (∀I) νX = 1. X hằng sai ↔ (∀I) νX = 0. X khả đúng ↔ (∃I) νX = 1. X khả sai ↔ (∃I) νX = 0. @Nguyễn Thanh Sơn ntsơn
Phân loại công thức Nhận xét : – Phủ định của một công thức hằng đúng là công thức hằng sai. @Nguyễn Thanh Sơn ntsơn
Công thức tương đương • Công thức X và Y tương đương nếu đồng bộ trong việc đánh giá thực trị đối với mọi diễn dịch. Lấy diễn dịch I của X và Y. Nếu X đúng trong I thì Y cũng đúng trong I và ngược lại. Nếu X sai trong I thì Y cũng sai trong I và ngược lại. Ký hiệu X = Y. • Hai CT tươngđương cócùng số CTN hay không? @Nguyễn Thanh Sơn ntsơn
Mô hình • Mô hình I của công thức F là diễn dịch I của F và νF = 1 trong I. Chú ý : Diễn dịch = interpretation, valuation (tiếng Anh). Mô hình = model (tiếng Anh). Một số tài liệu dùng từ model cho khái niệm diễn dịch. @Nguyễn Thanh Sơn ntsơn
Các công thức tương đương 1. ¬(¬F) = F 2. F ↔ G = (F → G) ∧ (G → F) 3. F → G = ¬F ∨ G 4. F → G = ¬G → ¬F 5. ¬(F ∨ G) = (¬F) ∧ (¬G) (DeMorgan) 6. ¬(F ∧ G) = (¬F) ∨ (¬G) (DeMorgan) @Nguyễn Thanh Sơn ntsơn
Hằng đúng • Tất cả các công thức sau là hằng đúng ngoại trừ công thức 1 là hằng sai. 1. (F ∧ ¬F) hằng sai 2. (F ∨ ¬F) 3. F → (F ∨ G) 4. (F ∧ G) → F 5. ((F→ G) ∧ F) → G 6. ((F→ G) ∧ ¬G) → ¬F @Nguyễn Thanh Sơn ntsơn
Hằng đúng 7. ((F→G) ∧ (G→H)) → (F→H) (tính truyền) 8. ((F→G) ∧ (F→¬G)) → ¬F (phản chứng) 9. (F→G) → ((F ∨ H)→(G ∨ H)) 10. (F→G) → ((F ∧ H) → (G ∧ H)) 11. @Nguyễn Thanh Sơn ntsơn
Hằng đúng • Chứng minh ((F→ G) ∧ F) → G hằng đúng Lấy diễn dịch I, nếu F đúng trong I, nếu G đúng trong I, CT đúng trong I, nếu G sai trong I , CT đúng trong I, nếu F sai trong I, nếu G đúng trong I , CT đúng trong I, nếu G sai trong I , CT đúng trong I, Vậy CT hằng đúng. @Nguyễn Thanh Sơn ntsơn
Lưỡng nguyên • Lưỡng nguyên (literal) là CTN hoặc phủ định CTN. Thí dụ : A, B, C là các công thức nguyên. A, B, C, ¬A, ¬B, ¬C là các lưỡng nguyên. @Nguyễn Thanh Sơn ntsơn
Diễn dịch • Diễn dịch được cho dưới dạng tập hợp các lưỡng nguyên. Thay vì viết νF1 = δ, , νFn = δ (δ = 1 hoăc δ = 0) thì viết là {signF1, , signFn}. Nếu δ là 1 thì signFi là Fi. Nếu δ là 0 thì signFi là ¬Fi. @Nguyễn Thanh Sơn ntsơn
Diễn dịch Thí dụ : F = (A → ¬B) → (B ∨ ¬C) Diễn dịch I = {A, B, C} nghĩa là νA = 1, νB = 1, νC = 1. Diễn dịch J = {A, ¬B, ¬C} nghĩa là νA = 1, νB = 0, νC = 0. Diễn dịch K = {¬A, ¬B, ¬C} nghĩa là νA = 0, νB = 0, νC = 0. @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF • Conjunctive normal form (CNF) có dạng : (P1∨ ∨Pn)1 ∧ ∧ (Q1∨ ∨Qm)p, với n, m, p ≥ 1, và Pi, Qi là các lưỡng nguyên. Thí dụ : F = (¬P ∨ R) ∧ (Q ∨ ¬S ∨ T) ∧ Q. G = P ∧ Q ∧ (¬R) H = (P ∨ R ∨ ¬S) @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF • Các bước chuyển về dạng CNF Thí dụ : F = (A → ¬B) → (B ∨ ¬A) = ¬(A → ¬B) ∨ (B ∨ ¬A) = ¬(¬A ∨ ¬B) ∨ (B ∨ ¬A) = (A ∧ B) ∨ (B ∨ ¬A) = (A ∨ (B ∨ ¬A)) ∧ (B ∨ (B ∨ ¬A)) = (A ∨ B ∨ ¬A) ∧ (B ∨ B ∨ ¬A) = (B ∨ ¬A) @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF • CNF có thể được xây dựng từ bảng thực trị. Thí dụ : F = (A ∨ B) → (A ∧ B) A B F 1 1 1 1 0 0 (¬A ∨ B) 0 1 0 (A ∨ ¬B) 0 0 1 có CNF là F = (¬A ∨ B) ∧ (A ∨ ¬B) @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF Thí dụ : Công thức F có bảng thực trị : A B C F 1 1 1 1 1 1 0 0 (¬A ∨ ¬B ∨ C) 1 0 1 1 1 0 0 0 (¬A ∨ B ∨ C) 0 1 1 1 0 1 0 0 (A ∨ ¬B ∨ C) 0 0 1 1 0 0 0 1 có CNF là F = (¬A ∨ ¬B ∨ C) ∧ (¬A ∨ B ∨ C) ∧ (A ∨ ¬B ∨ C) @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF • Nhận xét :  Mọi công thức có thể chuyển về dạng CNF.  Dạng CNF không duy nhất. @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF • Nhận xét :  A, B, C, là các CTN. Các Fi tương đương : F1 = A, F2 = A ∧ (A ∨ B), F3 = A ∧ (A ∨ B) ∧ (A ∨ C), F4 = A ∧ (A ∨ B) ∧ (A ∨ C) ∧ (A ∨ D).  ν(F1) = ν(F2) = ν(F3) = ν(F4). ν(F2) = νA (νA + νB + νAνB) = νA. @Nguyễn Thanh Sơn ntsơn
Mệnh đề • Mỗi khối (P1 ∨ ∨ Pn)i của CNF được gọi là 1 mệnh đề. Thí dụ : F = (¬P ∨ R) ∧ (Q ∨ ¬S ∨ T) ∧ Q F có 3 mệnh đề : (¬P ∨ R), (Q ∨ ¬S ∨ T) và mệnh đề Q. H = (P ∨ R ∨ ¬S) có 1 mệnh đề là chính nó. @Nguyễn Thanh Sơn ntsơn
Mệnh đề • Mệnh đề có 1 lưỡng nguyên được gọi là mệnh đề đơn vị. Thí dụ : F = (¬P ∨ R) ∧ (Q ∨ ¬S ∨ T) ∧ Q F có Q là mệnh đề đơn vị Q . @Nguyễn Thanh Sơn ntsơn
Mệnh đề • Mệnh đề rỗng là mệnh đề không có lưỡng nguyên nào. • Nhận xét : Với mọi công thức X, X ∧ hđ = X (hđ, công thức hằng đúng). X ∨ hs = X (hs, công thức hằng sai).  Mệnh đề rỗng là công thức hằng sai. @Nguyễn Thanh Sơn ntsơn
Clausal form[15] • Dùng tập hợp để biểu diễn CNF. • Một mệnh đề được biểu diễn thành tập hợp các lưỡng nguyên. Thí dụ : mệnh đề (Q ∨ ¬S ∨ T) được biểu diễn là {Q, ¬S, T} • CNF được biểu diễn như tập hợp các mệnh đề. Thí dụ : F = (¬P ∨ R) ∧ (Q ∨ ¬S ∨ T) ∧ Q được biểu diễn là {{¬P, R}, {Q, ¬S, T}, {Q}} Biểu diễn này được gọi là clausal form. @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn hội - DNF • Disjunctive normal form (DNF) đối ngẫu với CNF. Thí dụ : F = (¬P ∧ R) ∨ (Q ∧ ¬S ∧ T) ∨ Q. G = (P ∧ Q ∧ (¬R)) H = P ∨ R ∨ ¬S @Nguyễn Thanh Sơn ntsơn
Bài toán SAT • Một vấn đề quan trọng trong logic nói chung là diễn dịch nào làm cho công thức có giá trị đúng. • Bài toán SAT (satisability problem) của luận lý mệnh đề được phát biểu một cách đơn giản theo ngôn ngữ bảng thực trị : Làm thế nào gán giá trị cho CTN trong công thức để công thức có giá trị đúng. [15] • Nói cách khác là công thức có khả đúng hay không. @Nguyễn Thanh Sơn ntsơn
Bài toán SAT • Vì “X khả đúng ↔ ¬X không hằng đúng” nên bài toán SAT trở thành bài toán kiểm tra ¬X không hằng đúng. • Nếu ¬X ờ dạng chuẩn giao thì ¬X hằng đúng khi các mệnh đề của CNF phài hằng đúng. • Một mệnh đề hằng đúng khi có 2 lưỡng nguyên trái dấu. @Nguyễn Thanh Sơn ntsơn
Bài toán SAT • Tóm lại bài toán SAT (X khả đúng) gồm các bước : 1. Chuyển ¬X thành dạng chuẩn giao. 2. Kiểm tra mỗi mệnh đề không chứa 2 lưỡng nguyên trái dấu : a) Nếu có mệnh đề không chứa 2 lưỡng nguyên trái dấu thì X khả đúng. b) Ngược lại X hằng đúng. @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn giao - CNF • CT (dạng CNF) là hằng đúng nếu tất cả mệnh đề chứa Ť hoặc có 1 cặp lưỡng nguyên đổi dấu. Ngược lại, là khả sai (falsiable). • CT (dạng DNF) là hằng sai nếu tất cả thành phần giao chứa ⊥ hoặc có 1 cặp lưỡng nguyên đổi dấu. Ngược lại, là khả đúng (SATisfiable). Nhận xét : Biến đổi về dạng DNF (CNF) tốn kém cả về thời gian và không gian. @Nguyễn Thanh Sơn ntsơn
Dạng NNF[*] • Công thức ở dạng NNF(negation normal form) khi công thức không chứa toán tử → : 1. Thay “→” dùng (X → Y) = (¬X ∨ Y). 2. Khai triển toán tử ¬ dùng ¬¬X = X, dùng ¬(X ∨ Y) = (¬X ∧ ¬Y) dùng ¬(X ∧ Y) = (¬X ∨ ¬Y). [*] Logic and Proof - Computer Science Tripos Part IB Michaelmas Term Lawrence C Paulson - Computer Laboratory University of Cambridge lcp@cl.cam.ac.uk @Nguyễn Thanh Sơn ntsơn
Dạng NNF Thí dụ : F = (A → ¬B) → (B ∨ ¬A) F = ¬(A → ¬B) ∨ (B ∨ ¬A) (thay →) F = ¬(¬A ∨ ¬B) ∨ (B ∨ ¬A) (thay →) F = (A ∧ B) ∨ (B ∨ ¬A) (khai triển ¬) [*] Logic and Proof - Computer Science Tripos Part IB Michaelmas Term Lawrence C Paulson - Computer Laboratory University of Cambridge lcp@cl.cam.ac.uk @Nguyễn Thanh Sơn ntsơn
Từ NNF đến CNF[*] • Đẩy ∨ vào trong, dùng F ∨ (G ∧ H) = (F ∨ G) ∧ (F ∨ H) • Đơn giản hóa : – Xóa mệnhđề chứa 2 lưỡngnguyên trái dấu. eg : (F ∨ G ∨ ¬F) ∧ (H ∨ K) = H ∨ K. – Xóa mệnh đề chứa mệnh đề khác. eg : (H ∨ K ∨ ¬F) ∧ (H ∨ K) = H ∨ K. – Thay (F ∨ G) ∧ (¬F ∨ G) bằng G. [*] Logic and Proof - Computer Science Tripos Part IB Michaelmas Term Lawrence C Paulson - Computer Laboratory University of Cambridge lcp@cl.cam.ac.uk @Nguyễn Thanh Sơn ntsơn
Thuật toán CNF • Function CNF (F) Begin case F là nguyên từ : return F F = F1 ∧ F2 : return CNF (F1) ∧ CNF (F2) F = F1 ∨ F2 : return Phb (CNF (F1), CNF (F2)) endcase End [*] Logic and Proof - Computer Science Tripos Part IB Michaelmas Term Lawrence C Paulson - Computer Laboratory University of Cambridge lcp@cl.cam.ac.uk @Nguyễn Thanh Sơn ntsơn
Thuật toán CNF • Function PhB (F1, F2) Begin case F1 = F11∧F12 : return PhB (F11,F2) ∧ Phb (F12,F2) F2 = F21∧F22 : return PhB (F1,F21) ∧ Phb (F1,F22) otherwise (không có toán tử ∧) : return F1 ∨ F2 endcase End @Nguyễn Thanh Sơn ntsơn
Thuật toán NNF • Function NNF (F) Begin case F là nguyên từ : return F F = ¬¬F1 : return NNF (F1) F = F1 ∧ F2 : return NNF (F1) ∧ NNF (F2) F = F1 ∨ F2 : return NNF (F1) ∨ NNF (F2) F = ¬(F1 ∧ F2) : return NNF (¬F1) ∧ NNF (¬F2) F = ¬(F1 ∨ F2) : return NNF (¬F1) ∨ NNF (¬F2) endcase End @Nguyễn Thanh Sơn ntsơn
Thuật toán NO_ARROW • Function NO_ARROW (F) Begin case F là nguyên từ : return F F = ¬F1 : return ¬(NO_ARROW (F1)) F = F1 ∧ F2 : return NO_ARROW (F1) ∧ NO_ARROW (F2) F = F1 ∨ F2 : return NO_ARROW (F1) ∨ NO_ARROW (F2) F = F1 →F2 :return ¬NO_ARROW(F1) ∨ NO_ARROW (F2) endcase End @Nguyễn Thanh Sơn ntsơn
Dạng CNF Thí dụ : F = (¬A ∧ B → A ∧ (C → B) F1 = NO_ARROW(F) = ¬(¬A ∧ B) ∨ (A ∧ (¬C ∨ B)) F2 = NNF(F1) = (A ∨ ¬B) ∨ (A ∧ (¬C ∨ B)) F3 = CNF(F2) = (A ∨ ¬B ∨ A) ∧ (A ∨ ¬B ∨ ¬C ∨ B) F3 =CNF(NNF(NO_ARROW(F))) @Nguyễn Thanh Sơn ntsơn
Dạng CNF Thí dụ : F = (¬A ∧ B → A ∧ (C → B) CNF(NNF(NO_ARROW(F))) = (A ∨ ¬B ∨ A) ∧ (A ∨ ¬B ∨ ¬C ∨ B) Tuy nhiên, (A ∨ ¬B) cũng là một dạng CNF của F. Kết quả của CNF(NNF(NO_ARROW(F))) không chắc là tối ưu cho việc giải bài toán SAT. @Nguyễn Thanh Sơn ntsơn
Horn clause • Mệnh đề Horn là mệnh đề chỉ có 1 lưỡng nguyên dương (positive literal). Thí dụ : (A) (A ∨ ¬B) (¬C ∨ D ∨ ¬E) • Dạng Horn : giao của các mệnh đề Horn. Thí dụ : (A ∨ ¬B) ∧ (¬C ∨ D ∨ ¬E) @Nguyễn Thanh Sơn ntsơn
Horn clause • Dạng Horn là giao các cấu trúc điều kiện (có hậu quả là một công thức nguyên và nguyên nhân là giao các công thức nguyên). Thí dụ : (A ∨ ¬B) ∧ (¬C ∨ D ∨ ¬E) thường được viết dưới dạng (B → A) ∧ ((C ∧ E) → D) @Nguyễn Thanh Sơn ntsơn
Horn clause • Dạng Horn được định nghĩa bằng văn phạm Backus Naur form : F ::= ⊥ | Ť | A G ::= F | F ∧ G H ::= G → F K ::= H | H ∧ K Chú thích : ⊥ là công thức hằng sai Ť là công thức hằng đúng A là công thức nguyên @Nguyễn Thanh Sơn ntsơn
Horn clause Thí dụ : (A → B) ∧ (A → ⊥) ∧ ((C ∧ E) → D) ((A ∧ B ∧ C ∧ E) → D) ∧ (Ť → A) Có thể loại trừ 2 dạng sau : ⊥ → A và (A ∧ B) → Ť vì luôn luôn đúng, @Nguyễn Thanh Sơn ntsơn
Horn clause & SAT • Function HORN (F) Begin Đánh dấu (đd) tất cả Ť có trong F. while có ((A1 ∧ ∧ An) → A) của F sao cho các Ai bị đd và A chưa bị đd, khi đó đd mọi A của F endwhile if ⊥ bị đd then F hằng sai else F khả đúng End @Nguyễn Thanh Sơn ntsơn
Horn clause & SAT • Thí dụ : HORN ((A → ⊥) ∧ (Ť → A)) Begin (A → ⊥) ∧ (Ť* → A) (Ť* → A) : (A* → ⊥) ∧ (Ť* → A*) (A* → ⊥) : (A* → ⊥*) ∧ (Ť* → A*) End ⊥ bị đánh dấu. Vậy công thức F hằng sai. @Nguyễn Thanh Sơn ntsơn
Horn clause & SAT • Thí dụ : F = ((A → B) ∧ (Ť → A) ∧ ((A ∧ B ∧ C) → D)) HORN (F) Begin (A → B) ∧ (Ť* → A) ∧ ((A ∧ B ∧ C) → D) (A* → B) ∧ (Ť* → A*) ∧ ((A* ∧ B ∧ C) → D) (A* → B*) ∧ (Ť* → A*) ∧ ((A* ∧ B* ∧ C) → D) End vậy công thức F khả đúng. @Nguyễn Thanh Sơn ntsơn
Horn clause & SAT • Thí dụ : HORN ((A → B) ∧ ((C ∧ E) → D) ∧ (Ť → A) ∧ ((A ∧ B ∧ C ∧ E) → D)) Begin (A → B) ∧ ((C ∧ E) → D) ∧ (Ť* → A) ∧ ((A ∧ B ∧ C ∧ E) → D) (A* → B*) ∧ ((C ∧ E) → D) ∧ (Ť* → A*) ∧ ((A* ∧ B* ∧ C ∧ E) → D) End vậy công thức khả đúng. @Nguyễn Thanh Sơn ntsơn
Hệ quả luận lý • Nếu mọi mô hình của F cũng là mô hình của H thì H được gọi là hệ quả luận lý của F. Ký hiệu F ╞═ H. • F là KB, được gọi là tiền đề và H được gọi là kết luận. • Logical Consequence = Entailment = Hệ quả luận lý (HQLL). @Nguyễn Thanh Sơn ntsơn
Hệ quả luận lý • Để chứng minh H là hệ quả luận lý của F : – Liệt kê tất cả diễn dịch. – Chọn các diễn dịch là mô hình của F. – Kiểm tra xem các mô hình này có còn là mô hình của H hay không. Hệ quả luận lý F ╞═ H thỏa thỏa Tập các Diễn dịch Tập con Tập các Diễn dịch @Nguyễn Thanh Sơn ntsơn
Hệ quả luận lý Thí dụ : {A, B} ╞═ A ∨ B {A, B} ╞═ A ∧ B {A, B} ╞═ A → B {A, A ∨ B} ╞‌═ A → B {A ∨ B, A ∧ B} ╞═ A {A ∨ B, A ∧ B} ╞═ B {A ∨ B, A ∧ B} ╞═ A → B {B, A → B} ╞═ A ∨ B @Nguyễn Thanh Sơn ntsơn
Hệ quả luận lý • Kiểm tra X → Y, X ╞═ Y. X Y X → Y X ╞═ Y 1 1 1 1 1 1 0 0 1 Không là mô hình của KB 0 1 1 0 Không là mô hình của KB 0 0 1 0 Không là mô hình của KB @Nguyễn Thanh Sơn ntsơn
Ký hiệu hằng đúng • Ký hiệu công thức H là hằng đúng : ╞═ H Ký hiệu ╞═ H có nghĩa là ∅ ╞═ H. Hệ thống { F1, , Fn }╞═ H ↔ { F1, , Fn } ∪ {CTHằngđúng}╞═ H ↔ F1, ∧ ∧ , Fn ∧ CTHằngđúng ╞═ H Do đó khi { F1, , Fn } = ∅ thì CTHằngđúng╞═ H. @Nguyễn Thanh Sơn ntsơn
Công thức hằng đúng • Nếu F ╞═ H thì công thức (F → H) hằng đúng. • Một công thức hằng đúng : F ╞═ H ↔ ╞═ (F → H) F ╞═ H ↔ ╞═ ¬( F ∧ ¬H) ( F1, , Fn ╞═ H ) ↔ (F2, , Fn ╞═ F1 → H) ( F ╞═ H và H ╞═ K ) → (F ╞═ K) (truyền) @Nguyễn Thanh Sơn ntsơn
Ký hiệu ╞═ • Một số tác giả ký hiệu M ╞═ F, trong đó F là một công thức và M là một mô hình của F. @Nguyễn Thanh Sơn ntsơn
Bài tập Chương 2 : Luận lý mệnh đề Chương 2 ntsơn
Lập bảng thực trị Cho các công thức sau : 1. (¬P ∨ Q) ∧ (¬(P ∧ ¬Q)) 2. (P → Q) → (¬Q → ¬P) 3. (P → Q) → (Q → P) 4. P ∨ (P → Q) 5. (P ∧ (Q → P)) → P 6. P ∨ (Q → ¬P) 7. (P ∨ ¬Q) ∧ (¬P ∨ Q) ∧ (¬(P → Q)) @Nguyễn Thanh Sơn ntsơn
Tương quan giữa các toán tử So sánh các công thức sau : 1. ¬(P → (¬Q)) và (P ∧ Q) 2. (¬P → Q) và (P ∨ Q) Nhận xét gì về sự liên hệ của các toán tử ? @Nguyễn Thanh Sơn ntsơn
Tương quan giữa các toán tử Viết ra các công thức sau chỉ dùng → và ¬ : 1. (P ∨ Q) ∧ (Q → P) 2. (¬P ∨ Q) ∧ (¬(P ∧ ¬Q)) 3. P ∨ (P → Q) 4. (P ∧ (Q → P)) → P 5. P ∨ (Q → ¬P) 6. (P ∨ ¬Q) ∧ (¬P ∨ Q) ∧ (¬(P → Q)) @Nguyễn Thanh Sơn ntsơn
Dùng thủ tục số học Tính các công thức : 1. (¬P ∨ Q) ∧ (¬(P ∧ ¬Q)) 2. (P → Q) → (¬Q → ¬P) 3. (P → Q) → (Q → P) 4. P ∨ (P → Q) 5. (P ∧ (Q → P)) → P 6. P ∨ (Q → ¬P) 7. (P ∨ ¬Q) ∧ (¬P ∨ Q) ∧ (¬(P → Q)) @Nguyễn Thanh Sơn ntsơn
Sự tương đương Chứng minh sự tương đương của các công thức : 1. (P → Q) → (P ∧ Q) = (¬P → Q) ∧ (Q → P) 2. P ∧ Q ∧ (¬P ∨ ¬Q) = ¬P ∧ ¬Q ∧ (P ∨ Q) 3. (P → Q) ∧ (P → R) = (P → (Q ∧ R)) 4. P ∧ (P → (P ∧ Q)) = ¬P ∨ ¬Q ∨ (P ∧ Q) @Nguyễn Thanh Sơn ntsơn
Hằng đúng - Hằng sai Xác định tính hằng đúng, hằng sai của các công thức : 1. ¬(¬S) → S 2. ¬(S ∨ T) ∨ ¬T 3. (S→T)→ (¬T→ ¬S) 4. P ∨ (P → Q) 5. (P ∧ (Q → P)) → P 6. ¬P ∧ (¬(P → Q)) 7. ((A ∨ B) ∧ (¬A ∨ C)) → (B ∨ C). @Nguyễn Thanh Sơn ntsơn
Mô hình Tìm một mô hình cho mỗi công thức : 1. ¬(¬S) → S 2. ¬(S ∨ T) ∨ ¬T 3. (S→T)→ (¬T→ ¬S) 4. P ∨ (P → Q) 5. (P ∧ (Q → P)) → P 6. ¬P ∧ (¬(P → Q)) 7. ((A ∨ B) ∧ (¬A ∨ C)) → (B ∨ C). @Nguyễn Thanh Sơn ntsơn
Mô hình Diễn dịch nào : I1 = {S} I2 = {S, ¬T} I3 = {A, ¬B, C} I4 = {S, ¬T, A, ¬B, C, P, ¬Q} là mô hình của các công thức sau : 1. ¬(¬S) → S 2. ¬(S∨T) ∨ ¬T 3. P ∨ (P → Q) 4. (P → Q) → (¬Q → ¬P) 5. ((A ∨ B) ∧ (¬A ∨ C)) → (B ∨ C). @Nguyễn Thanh Sơn ntsơn
Dạng chuẩn CNF Chuyển thành dạng CNF 1. ¬(P → Q) 2. ¬(P ∨ ¬Q) ∧ (P ∨ Q) 3. (¬P ∧ Q) → R 4. ¬(P ∧ Q) ∧ (P ∨ Q) 5. (P → Q) → R 6. P → ((Q ∧ R) → S) 7. P ∨ (¬P ∧ Q ∧ R) 8. ¬(P → Q) ∨ (P ∨ Q) 9. (¬P ∧ Q) ∨ (P ∧ ¬Q). @Nguyễn Thanh Sơn ntsơn
Hằng đúng - Hằng sai Chứng minh các công thức sau đây là hằng đúng, hằng sai, hay khả đúng khả sai : 1. ¬(¬S) → S 2. ¬(S∨T) ∨¬T 3. (S→T)→(¬T→ ¬S) @Nguyễn Thanh Sơn ntsơn
Mô hình Tìm một mô hình I cho công thức F. F = ((A∨B) ∧ ¬B) → A Mở rộng I để nó cũng là mô hình của G. G = ((A∧C) ∨ ¬C) → A. @Nguyễn Thanh Sơn ntsơn
Hệ qủa luận lý Chứng minh ¬K là hệ quả luận lý của hệ thống {F1, F2, F3, F4} : F1 = J → P ∨ T, F2 = K ∨ Q → J, F3 = T → A, F4 = ¬P ∧ ¬A. @Nguyễn Thanh Sơn ntsơn
Hệ qủa luận lý Công thức nào là hệ quả luận lý của hệ thống {A, B, A→ C } 1. A∨ B. 2. A ∧ B. 3. B → C. 4. (A ∧ B) ∨ C. @Nguyễn Thanh Sơn ntsơn
Hằng đúng Công thức nào sau đây là hằng đúng : 1. (x → x) 2. ¬(x ↔ x) 3. (((P → Q) ∧ (¬P → Q)) → Q) 4. (¬A → (B → A)) 5. ((A ∨ B) → (¬B → A)) 6. ((¬P ∧ Q) ∧ (Q → P)) 7. (((X → Y) → X) → Y). @Nguyễn Thanh Sơn ntsơn
Hết slide @Nguyễn Thanh Sơn ntsơn