Bài giảng : Logic part 4

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
Nội dung trích xuất từ tài liệu:
Bài giảng : Logic part 4Trang 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 40Trang 41: Sự phức tạp của bảng sự thậtNhữ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 vvớ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ỗiliê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 41Trang 42: Những định nghĩaNế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 α. 42LOGIC TRONG KHOA HỌC MÁY TÍNH LECTURE 2 (từ trang 4 đến trang 28) 43Trang 4: Cú pháp và ngữ nghĩaTậ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 chocá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. 44Trang 5: Định nghĩaNế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ọibiể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. 45Trang 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∨ BGiả 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ậntoán này để xác nhận mỗi khẳng định trên bằng cách nào? 46Trang 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∨ BGi ...