intTypePromotion=1

Bài giảng : Logic part 5

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

0
86
lượt xem
19
download

Bài giảng : Logic part 5

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

Trang 13: Liên từ mệnh đề: Ta đã có 5 liên từ:  , ∧, ∨, →, ↔. Chúng ta có cần cải tiến bằng việc có nhiều hơn? Ta sẽ mất gì với việc có ít đi? Ví dụ: Liên từ 3 ngôi # ℰ#(α,β,µ)=(# αβµ) ℰ#(α,β,µ)=1 khi và chỉ khi cả ba v (α), v ( β) và v (µ) bằng 1. Liên từ mới này đem lại gì cho chúng ta? Khẳng định: Ngôn ngữ mở rộng đạt được bằng việc thêm các kí hiệu mới có cùng sức mạnh biểu diễn như ngôn ngữ gốc. Ta...

Chủ đề:
Lưu

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

  1. Trang 13: Liên từ mệnh đề: Ta đã có 5 liên từ:  , ∧, ∨, →, ↔. Chúng ta có cần cải tiến bằng việc có nhiều hơn? Ta sẽ mất gì với việc có ít đi? Ví dụ: Liên từ 3 ngôi # ℰ#(α,β,µ)=(# αβµ) ℰ#(α,β,µ)=1 khi và chỉ khi cả ba v (α), v ( β) và v (µ) bằng 1. Liên từ mới này đem lại gì cho chúng ta? Khẳng định: Ngôn ngữ mở rộng đạt được bằng việc thêm các kí hiệu mới có cùng sức mạnh biểu diễn như ngôn ngữ gốc. Ta sẽ chứng minh khẳng định này như thế nào? 53
  2. 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 X2 Bα(X1, X2) 1 1 1 1 0 0 0 1 0 0 0 0 54
  3. Trang 15: Những hàm Boolean nhận được Tổng quát, giả sử rằng α là một wff trong nó có các kí hiệu mệnh đề bao gồm ở trong A1- n ,…, An. Chúng ta xác định một hàm Boolean n ngôi B . Hàm Boolean này thực hiện bởi α như sau: n B (X1,…,Xn)= giá trị thật sự của α khi A1,…, An nhận các giá trị là X1,…,Xn. Nói cách khác, n B (X1,…,Xn)= v (α) với v(Ai)=Xi. n Chú ý rằng hàm B được xác định bởi cả công thức α và lựa chọn của n. Cụ thể, α không cần phải bao gồm tất cả các kí hiệu trong A1,…, An. 55
  4. Trang 16: Ví dụ B n n I Ai i  N B 1 A  K BA 2  A2 1  A B A 2  A2 1  C BA 2  A2 1  E BA 2  A2 1 Từ những hàm này, ta có thể cấu trúc nên những hàm khác bằng việc đặt hàm: ( X 1 , X 2)  ( A( N ( I 1 ( X 1 , X 2)), N ( I 2 ( X 1 , X 2))) 2 2 2 BA A2  1 Khẳng định: mọi hàm Boolean có thể đạt được bằng việc soạn từ các hàm I, N, K, A, C và E. Ta sẽ giải thích tại sao khẳng định này đúng một cách ngắn gọn. 56
  5. Trang 17: Biểu thức và hàm Boolean Định lí: Cho α, β là wff’s với dãy kí hiệu mệnh đề của chúng thuộc A1,…, An.  với mọi X ∈{0,1}n B  B n n (a) α⊨β khi và chỉ khi (b) α là hằng tương đương với β khi và chỉ khi B  Bn n  (c) ⊨ β khi và chỉ khia miền xác định B  {1} n Chứng minh: (a) α⊨β khi và chỉ khi mọi phép gán thoả mãn α cũng thoả mãn β Khi và chỉ khi với mọi phép gán v, v (α)=1 kéo theo v (β)=1    B ( X )  1 n kéo theo B ( X )  1 n Khi và chỉ khi với mọi véctơ X n cơ sở, nếu    ( X )  B ( X ) n n Khi và chỉ khi với mọi véctơ n cơ sở B X (b) dẫn đến từ (a) và định lí: X=Y khi và chỉ khi X≤Y và Y≤X. (c) dẫn đến từ (a) và định nghĩa hằng đúng. Bằng việc đổi cách tiếp cận từ công thức sang hàm Boolean,ta thấy những công thức wff là hằng tương đương là đồng nhất. 57
  6. Trang 18: Tính đầy đủ của các liên từ mệnh đề Định lí: Cho G là một hàm Boolean n ngôi, n≥1. Có tồn tại một wff α để G= B , với α thực hiện n hàm G. Chứng minh: Nếu miền xác định của G là {0}, thì cho α=A1∧  A1. Rõ ràng: G= B . n Ngược lại, G=1 tại một số điểm. Giả sử có k điểm xảy ra G=1: G(X11, X12,…, X1n)=1 G(X21, X22,…, X2n)=1 ….. G(Xk1, Xk2,…, Xkn)=1 Cho: X 1  Aj   ij   ij A j X 0  ij γi=βi1∧…...∧βin α= γ1∨γ2∨…∨γk Thì α thực hiện G. 58
  7. Trang 19: Tính đầy đủ của những liên từ mệnh đề: Chứng minh tiếp tục…  ( X )  v ( ) n Ta biết rằng với v(Ai)=Xi. B   Từ α= γ1∨γ2∨…∨γk, dẫn đến B ( X )  max( B ( X )) n n   i   Nhưng bởi kiến trúc trên, khi và chỉ khi X =. (X ) 1 n B i   Vậy B ( X )  1 khi và chỉ khi n là một trong những điểm khiến cho G bằng 1. X Định lí này chứng minh rằng mọi hàm Boolean có thể được thực hiện bởi một wff. Thực sự, mọi hàm Boolean có thể được thực hiện bởi một wff chỉ sử dụng những liên từ {  , , }. Ta nói rằng tập những liên từ này là đầy đủ.   Công thức thực hiện không phải là duy nhất. Công thức xây dựng kiểu trên được gọi là dạng chuẩn tắc tuyển (DNF). Một công thức ở trong công thức có dạng DNF nếu nó là một công thức độc lập, mỗi công thức này bao gồm những literal phụ thuộc nhau, với một literal hoặc là kí hiệu mệnh đề hoặc phủ định của nó. Vậy, tất yếu rằng mọi wff, có tồn tại một hằng tương đương là một wff ở dạng chuẩn tắc tuyển (DNF). 59
  8. Trang 20: Tính đầy đủ của những liên từ mệnh đề: Ví dụ: Cho G là hàm Boolean 3 ngội xác định như sau: G(0,0,0)=0 G(0,0,1)=1 G(0,1,0)=1 G(0,1,1)=0 G(1,0,0)=1 G(1,0,1)=0 G(1,1,0)=0 G(1,1,1)=1 Có 4 điểm tại đó G nhận giá trị đúng, nên một công thức dạng DNF thực hiện G là: (  A1∧  A2∧A3)∨(  A1∧A2∧  A3)∨( A1∧  A2∧  A3)∨ (A1∧A2∧A3) Chú ý rằng công thức khác thực hiện hàm G là A1↔A2↔A3. Vậy, việc them những liên từ cho một tập đầy đủ có thể làm cho nó được thực hiện ngắn gọn hơn. 60
  9. Trang 21: Tính đầy đủ của những liên từ mệnh đề: Nhớ lại định nghĩa của chúng ta về một số hàm Boolean cơ bản: B n n I  Ai i  N  BA 1  K BA A 2  1 2  A B A 2  A2 1 Do {  , , } là tập đầy đủ, nên không khó nhận ra rằng mọi hàm Boolean có thể được cấu   trúc lên chí sử dụng các hàm Boolean I, N, K và A. Thực ra, ta có thể làm tốt hơn. Nó có thể thể hiện bằng {  , } hoặc {  , } là đầy đủ .   Tại sao? A∧B↔ (  A∨  B)  A∨B↔ (  A∧  B)  Sử dụng sự đồng nhất này, tính đầy đủ đó có thể được dễ dàng chứng minh bởi quy nạp. 61
  10. Trang 22: Những liên từ không đầy đủ Để chứng minh rằng một tập những liên từ nào đó là không đầy đủ, ta tìm một giả thiết để nó đúng với tất cả các wff xây dựng nên từ những liên từ này, nhưng lại không đúng với một hàm Boolean nào đó. Ví dụ: { ,  } là không đủ.  Chứng minh: Cho α là một công thức wff chỉ sử dụng 2 liên từ trên, và v là một phép gán thoả mãn v(Ai)=1 với mọi Ai. Ta chứng minh bằng quy nạp rằng v (α)=1. Trường hợp cơ sở: v (α)=v(Ai)=1. Trường hợp quy nạp: v (β∧γ)=min( v (β), v (γ))=min(1,1)=1 v (β  γ)=max( v (β), v (γ))=max(1,1)=1 Vậy, v (α)=1 với tất cả công thức wff α xây dựng từ { ,  }. v (Ai )  0 , mà không có công  thức nào chỉ xây bằng 2 liên từ trên là hằng tương đương với  Ai. 62
  11. Trang 23: Những liên từ mệnh đề khác n Cho mỗi số n, có hàm Boolean n ngôi khác nhau B(X1,…,Xn) 22 Tại sao? Có 2n điểm là đại lượng vào khác nhau ứng với một hàm và có 2 khả năng cho giá trị ra n với mỗi điểm nhập vào. Nên 2 2 cũng là số khả năng có thể cho tất cả các công thức mệnh đề n ngôi. Những liên từ không ngôi: Có 2 hàm Boolean không ngôi: hằng 0 và 1. Ta có thể cấu trúc chúng tương ứng thành liên từ không ngôi ⊤ và ⊥ với nghĩa là v (⊤)=0 và v (⊥)=1 với bất kể phép gán v nào. Những liên từ một ngôi: Có 4 hàm 1 ngôi, nhưng những hàm này bao gồm hai hàm hằng đã đề cập ở trên và hàm đồng nhất . Vậy, chỉ có chú ý liên từ phủ định:  . Những liên từ hai ngôi: Có 16 hàm 2 ngôi. Chúng được liệt kê ở bảng sau. Định nghĩa của 6 hàm đầu tiên tương ứng với những liên từ 0 ngôi và một ngôi. 63
  12. Trang 24: Kí hiệu Tương đương Giải thích ⊥ hằng 0 ⊤ hằng 1 A ngôi đầu tiên B ngôi thứ hai A phủ định của ngôi đầu tiên B phủ định của ngôi thứ hai ∧ A∧B và ∨ A∨B h o ặc  A→B điều kiện ↔ A↔B điều kiện hai chiều  B→A điều kiện đảo ⊕ (A∧  B)∨(  A∧B) loại trừ  (A∨B) ⬇ nor (A∧B) | nand   A∧B < nhỏ hơn A∧  B > lớn hơn 64
  13. Trang 25: Compactness Nhớ lại rằng một wff α là thoả mãn được nếu tồn tại một phép gán v đề v (α)=1. Một tâp Σ của các công thức wff là thoả mãn được nếu tồn tại phép gán v đề v (α)=1 với mọi α∈Σ. Một tập Σ là thoả mãn được hữu hạn nếu và chỉ nếu mọi tập con hữu hạn của Σ là thoả mãn được. Định lí Compactness: Một tập wff là thoả mãn được khi và chỉ khi nó thoả mãn được hữu hạn. Chứng minh: Hướng đi chứng minh mọi tập con của một tập thoả mãn được là thoả mãn được thật rõ ràng. Ta chứng minh hướng đi khác, giả sử rằng Σ là một tập thoả mãn được hữu hạn. Chúng ta chứng minh Σ là tập thoả mãn được. 65
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2