Bài giảng : Logic part 4

Chia sẻ: Ouiour Isihf | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

119
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trang 14: Hàm Boolean Cho k≥0, một hàm Boolean k ngôi là một hàm từ {0,1}k→{0,1}. Một hàm Boolean là bất cứ hàm nào như vậy có k ngôi với k nào đó. Mỗi wff α xác định tương ứng một hàm Boolean Bα. Ví dụ, nếu α=A1∧A2 thì Bα là một hàm Boolean hai ngôi với giá trị nhận được cho bởi bảng sau: X1 1 1 0 0 X2 1 0

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng : Logic part 4

Trang 40: Bảng sự thật: Đó là cách khác để miêu tả ngữ nghĩa nó là hình thức kém hơn nhưng xảy ra cụ thể hơn. α∧β α β α α  1 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 β α ∨β β Α→β α α α β α↔β 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 40
Trang 41: Sự phức tạp của bảng sự thật Những bảng sự thật có thế được sử dụng để tính toán tất cả các trường hợp giá trị của v với mỗi một wff: chúng ta kết hợp một cột với từng kí hiệu mệnh đề và một cột với mỗi liên từ mệnh đề. Có từng dòng cho mỗi trường hợp giá trị sự thật đến các liên từ mệnh đề. ∨ ∧ A1 A2 A3 (A1 (A2 A3))  1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 41
Trang 42: Những định nghĩa Nếu α là một wff, thì một phép gán v thoả mãn α nếu v (α)=1. Một wff α là thoả mãn được nếu có tồn tại một phép gán v nào đó thoả mãn α. 42
LOGIC TRONG KHOA HỌC MÁY TÍNH LECTURE 2 (từ trang 4 đến trang 28) 43
Trang 4: Cú pháp và ngữ nghĩa Tập công thức xây dựng đúng W:  U= tất cả các biểu thức  B={A1,A2,A3,…-  F={ ℰ  , ℰ∧,ℰ∨,ℰ→,ℰ↔} Cho phép gán v: B→{0,1} với các kí hiệu mệnh đề, ta có thể xây dựng một hàm v cho các công thức trong W như sau:  Với mỗi kí hiệu mệnh đề Ai, v (Ai)=v(Ai)  v ( ℰ  (α))=1- v (α)  v ( ℰ∧(α,β))=min( v (α), v (β))  v ( ℰ∨(α,β))=max( v (α), v (β))  v ( ℰ (α,β))=max(1- v (α), v (β)) →  v ( ℰ↔(α,β))=1-| v (α)- v (β)| Định lí đệ quy và thuyết đọc được duy nhất đảm bảo rằng v là xác định đúng. 44
Trang 5: Định nghĩa Nếu α là một wff, thì một phép gán v thoả mãn α nếu v (α)=1. Một wff α là thoả mãn được nếu có tồn tại một phép gán v nào đó thoả mãn α. Giả sử Σ là một tập wff’s. Thì Σ hằng kéo theo α, Σ ⊨ α nếu mọi phép gán thoả mãn mọi biểu thức trong Σ cũng thoả mãn α. Những trường cụ thể:  Nếu ∅ ⊨ α, thì ta nói α là một hằng hay α là hằng đúng và viết ⊨ α  Nếu Σ là không thoả mãn được, thì Σ ⊨ α với mọi công thức wff α.  Nếu α⊨ β (viết tắt của , α-⊨ β) và β⊨ α, thì α và β là hằng tương đương  Σ ⊨ α nếu và chỉ nếu ∧ (Σ)→ α là hằng đúng. 45
Trang 6: Ví dụ  (A∨ B)∧ (  A∨  B) là thoả mãn được, nhưng không là hằng đúng  (A∨ B)∧ (  A∨  B)∧(A↔B) là không thoả mãn được  {A,A→B}⊨ B (A∧ (A→B)∧(  B))  {A,  A}⊨ (A∧  A) (A∧(  A)∧  (A∧  A))   (A∧B) là hằng tương đương với  A∨  B Giả sử bạn có thuật toán SAT lấy một công thức wff α như đại lượng vào và trả lại giá trị đúng nếu α là thoả mãn được và sai trong trường hợp ngược lại. Bạn sử dụng thuận toán này để xác nhận mỗi khẳng định trên bằng cách nào? 46
Trang 7: Ví dụ  (A∨ B)∧ (  A∨  B) là thoả mãn được, nhưng không là hằng đúng  (A∨ B)∧ (  A∨  B)∧(A↔B) là không thoả mãn được  {A,A→B}⊨ B (A∧ (A→B)∧(  B))  {A,  A}⊨ (A∧  A) (A∧(  A)∧  (A∧  A))   (A∧B) là hằng tương đương với  A∨  B Giả sử bạn có một thuật toán kiểm tra tính hằng đúng với việc trả về giá trị đúng khi α là hằng đúng và sai khi ngược lại. Ta sẽ xác định những yêu cầu của thuật toán này như thế nào? Thoả mãn được và hằng đúng là hai khái niệm song hành: α là không thoả mãn được khi và chỉ  α là hằng đúng. 47
Trang 8: xác định thoả mãn được bằng bảng sự thật: Một thuật toán cho thoả mãn được: Để kiểm tra α là thoả mãn được, hình thức bảng sự thật với α. Nếu có một dòng với 1 xuất hiện như giá trị của α, thì α là thoả mãn được. Trái lại, α là không thoả mãn được. Một thuật toán cho hằng kéo theo: để kiểm tra , α1,…, αn}⊨ β, kiểm tra tính thoả mãn của (α1∧….∧αn)∧(  β). Nếu nó không thoả mãn được, thì , α1,…, αn}⊨ β. Trái lại, không xảy ra , α1,…, αn}⊨ β. 48
Trang 9: xác định thoả mãn được bằng bảng sự thật: Ví dụ A∧((B∨  A)∧(C∨  B)) ∧ ∨ ∧ ∨ A B C A ((B A) (C B))   0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 49
Trang 10: xác định thoả mãn được bằng bảng sự thật: Độ phức tạp của thuật toán này là gì? 2n với n là số kí hiệu mệnh đề đơn. Bạn có nghĩ có con đường nhanh hơn hẳn cho bài toán này? Bài tới, ta sẽ bàn một số ứng dụng và kĩ thuật tốt nhất được biết đến cho thuật toán SAT. 50
Trang 11: Một số hằng Có luật hoán vị và kết hợp cho ∧, ∨, ↔ Luật phân phối:  (A∧(B∨C))↔((A∧B)∨(A∧C))  (A∨(B∧C))↔((A∨B)∧(A∨C)) Luật phủ định  A↔A    (A→B)↔ A∧  B   (A↔B)↔(  A∧B)∨(A∧  B) Luật De Morgan:   (A∧B)↔(  A∨  B)   (A∨B)↔(  A∧  B) 51
Trang 12: Thêm một số hằng… Luật kéo theo:  (A→B)↔(  A∨B) Luật loại trừ:  A∨  A Luật mâu thuẫn:   (A∧  A) Luật phản đảo:  (A→B)↔(  B→  A) Luật xuất:  ((A∧B)→C)↔(A→(B→C)) 52