›
›

Bài giảng Logic mệnh đề

pdf 49 trang phuongnguyen 4680
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Logic mệnh đề", để 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:

  • pdfbai_giang_logic_menh_de.pdf

Nội dung text: Bài giảng Logic mệnh đề

  1. CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ 1.1. Các khái niệm cơ bản 1.2. Lý thuyết tổ hợp 1.3. Hai nguyên lý cơ bản 1.4. Lý thuyết số và các hệ đếm 1.5. Bài tập
  2. 1.1. CÁC KHÁI NIỆM CƠ BẢN 1. Logic mệnh đề. 2. Logic vị từ. 3. Các phương pháp chứng minh. 4. Tập hợp và hàm. 5. Ma trận và giải thuật.
  3. LOGIC MỆNH ĐỀ a) Mệnh đề, mệnh đề cĩ điều kiện và sự tương đương logic. b) Dạng chuẩn tắc hội và chuẩn tắc tuyển của cơng thức. c) Các phương pháp kiểm tra tính hằng đúng, hằng sai của cơng thức.
  4. MỆNH ĐỀ (1/3) Mệnh đề là câu cĩ giá trị hoặc đúng hoặc sai; nhưng khơng thể vừa đúng vừa sai hoặc khơng thể khẳng định tính đúng, sai của nĩ. Ví dụ 1: "6 là một số chẵn” “Hà Nội là thủ đơ của Việt Nam” “3+2 = 6” Ví dụ 2: Những câu khơng là mệnh đề “x là một số chẵn” “Kinh tế Mỹ khi nào phục hồi” “Trật tự”
  5. MỆNH ĐỀ (2/3) Mệnh đề khơng chứa các liên từ "và", "hoặc", "khơng", "nếu thì " được gọi là mệnh đề nguyên thủy hay mệnh đề sơ cấp. Mệnh đề khơng phải là mệnh đề sơ cấp được gọi là mệnh đề phức hợp. Ví dụ 3: 1) "6 là một số chẵn” 2) “Tơi là tổng thống Mỹ” 3) “Nếu trời nắng thì tơi đi chơi” 4) “Hà Nội là thủ đơ của Việt Nam và Thành phố HCM là trung tâm kinh tế lớn nhất Việt Nam” 5) “Người đi xe máy khơng vượt đèn đỏ nếu anh ta thấy cơng an trừ khi anh ta quá liều” 1), 2) là mệnh đề sơ cấp. 3), 4), 5), 6) là các mệnh đề phức hợp
  6. MỆNH ĐỀ( 3/3) Các mệnh đề sơ cấp được ký hiệu là X, Y, Z ; cĩ thể chứa chỉ số, được gọi là biến mệnh đề. Trong logic mệnh đề, giá trị chân lý đúng ký hiệu là 1, giá trị chân lý sai ký hiệu là 0. Bảng chân lý biểu diễn mối quan hệ giữa những giá trị chân lý của các biến mệnh đề
  7. CÁC PHÉP TOÁN TRÊN MỆNH ĐỀ 1. Phép phủ định 2. Phép hoặc (tuyển, cộng logic) 3. Phép và (hội, nhân logic) 4. Phép xor (tuyển loại) 5. Phép kéo theo 6. Phép tương đương
  8. 1. PHÉP PHỦ ĐỊNH Phủ định của một mệnh đề là một mệnh đề nhận giá trị đúng nếu X sai, và sai nếu X đúng. Ký hiệu X hoặc ¬X. X X 0 1 1 0 Ví dụ 4: X = “Hơm nay là chủ nhật” Phủ định X = “Hơm nay khơng là chủ nhật”
  9. 2. PHÉP HOẶC( TUYỂN, CỘNG LOGIC) Cho X và Y là hai mệnh đề, khi đó “X hoặc Y” là một mệnh đề chỉ nhận giá trị sai khi cả X và Y đều sai. Ký hiệu XY X Y X  Y 0 0 0 1 0 1 0 1 1 1 1 1 Ví dụ 5: X = “n là một số chẵn“ ; Y = “n là một số chia hết cho 3" X  Y = “7 là một số chẵn hoặc chia hết cho 3”
  10. 3. PHÉP VÀ (HỘI, NHÂN LOGIC) Cho X và Y là hai mệnh đề, khi đó “X và Y” là một mệnh đề chỉ nhận giá trị đúng nếu cả X và Y đều đúng. Kí hiệu X  Y X Y X  Y 0 0 0 1 0 0 0 1 0 1 1 1 Ví dụ 6: X = “n là một số chẵn“ ; Y = “n là một số chia hết cho 3" X  Y = “n là một số chẵn và chia hết cho 3”
  11. 4. PHÉP XOR (TUYỂN LOẠI) Cho X và Y là hai mệnh đề, “X XOR Y” là một mệnh đề chỉ nhận giá trị đúng nếu chỉ một trong hai mệnh đề đã cho đúng. Kí hiệu XY X Y X  Y 0 0 0 1 0 1 0 1 1 1 1 0 Ví dụ 7: X=“ n là một số chẵn”, Y=“m là một số lẻ” Trong trường hợp này ta có thể định nghĩa XY = “n+m là một số chẵn”.
  12. 5. PHÉP KÉO THEO: Cho X và Y là hai mệnh đề, “X kéo theo Y” ( “nếu X thì Y” ) là một mệnh đề chỉ nhận giá trị sai nếu X đúng, Y sai. Kí hiệu X Y. X Y X Y 0 0 1 1 0 0 0 1 1 1 1 1 Ví dụ 8: X=“n là một số chẵn”, Y=“n là một số chia hết cho 2”, X Y = “n là một số chẵn ” suy ra “n chia hết cho 2”.
  13. 6. PHÉP TƯƠNG ĐƯƠNG Cho X và Y là hai mệnh đề, “X tương đương Y” là một mệnh đề nhận giá trị đúng nếu cả hai mệnh đề đã cho cùng đúng, hoặc cùng sai. Kí hiệu X  Y. X Y X  Y 0 0 1 1 0 0 0 1 0 1 1 1 Ví dụ 9: X=“n là một số chẵn”, Y=“n là một số chia hết cho 2”, X  Y = ” n là một số chẵn” khi và chỉ khi ” n là một số chia hết cho 2”
  14. CƠNG THỨC LOGIC TRONG MỆNH ĐỀ Mỗi biến mệnh đề X, Y, Z (cĩ thể cĩ chỉ số) là một cơng thức. A, B là hai cơng thức, khi đó dãy ký hiệu  (A  B)  (A  B)  (A B)  (A) cũng là một cơng thức. Ví dụ 10: X, Y, X  Y, X (X  Y) là một cơng thức.
  15. CƠNG THỨC ĐỜNG NHẤT ĐÚNG Cơng thức A được gọi là cơng thức đồng nhất đúng khi và chỉ khi A luơn luơn nhận giá trị đúng với mọi bộ giá trị đúng, sai của các biến mệnh đề cĩ mặt trong A. Ký hiệu A≡1 Cơng thức A≡1 cịn được gọi là hằng đúng. Ví dụ 11: X  Y → Y ≡ 1 X Y X Y X  Y → Y 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1
  16. CƠNG THỨC ĐỜNG NHẤT SAI Cơng thức A được gọi là cơng thức đồng nhất sai khi và chỉ khi A luơn luơn nhận giá trị sai với mọi bộ giá trị đúng, sai của các biến mệnh đề cĩ mặt trong A. Ký hiệu A≡0 Nếu A là hằng đúng thì ¬A là cơng thức đồng nhất sai Ví dụ 12: X  ¬X ≡ 0 X ¬X X  ¬X 1 0 0 0 1 0
  17. CƠNG THỨC THỰC HIỆN ĐƯỢC Cơng thức A được gọi là cơng thức thực hiện được khi và chỉ khi cĩ tồn tại một bộ giá trị đúng, sai của các biến mệnh cĩ mặt trong A để A nhận giá trị đúng. Ví dụ 13:  Các cơng thức tuyển, hội của hai mệnh đề; cơng thức hằng đúng là các cơng thức thực hiện được.  Cơng thức hằng sai là cơng thức khơng thực hiện được.
  18. CƠNG THỨC ĐỜNG NHẤT BẰNG NHAU Hai cơng thức A và B được gọi là cơng thức đồng nhất bằng nhau khi và chỉ khi A và B cùng nhận giá trị đúng, sai như nhau đối với mọi bộ giá trị đúng, sai của các biến mệnh đề cĩ mặt trong A và B. Ta nĩi, A và B là tương đương. Ký hiệu A≡B hoặc A  B Ví dụ 14:  p và ¬ (¬p) là hai cơng thức tương đương
  19. MỘT SỚ LUẬT ĐỜNG NHẤT ĐÚNG 1. A (B A) 1. Đây là hệ 2. (A (B C)) ((A B) (A C)) 1. 3. (A  B) A 1. tiên đề 4. (A  B) B 1. được sử 5. (A B) ((A C) (A (B  C))) 1. dụng để 6. A (A  B) 1. nghiên 7. B (A  B) 1. cứu các 8. (A C) ((B C) ((A  B) C)) 1. tính chất 9. (A B) B A 1. tổng quát 10. A A 1. của logic 11. A A 1. mệnh đề.
  20. LUẬT ĐỚI NGẪU Giả sử A là một cơng thức chỉ chứa các phép tốn ,  , ¬ mà khơng chứa phép →. Trong A đổi chỗ  và  cho nhau ta được cơng thức mới A*. A* gọi là cơng thức đối ngẫu của A. Định lý 1: Luật đối ngẫu của cơng thức: Giả sử A(X1, X2, , Xn) là cơng thức khơng cĩ phép →. Khi đó ta cĩ: * A X1, X 2 , , X n  A X1, X 2 , , X n Ví dụ 15: A(X,Y) = XY; A*(X,Y) = XY → XY ≡ ¬(¬X¬Y)
  21. LUẬT THAY THẾ VÀ LUẬT KẾT LUẬN Định lý 2: Luật thay thế: Nếu A(X)≡1 thì A(E) ≡1 với E là cơng thức bất kỳ. Ví dụ 16: A(X) = X → ¬¬ X ≡ 1 A(Y  Z) = (Y  Z)→ ¬¬( Y  Z) ≡ 1 Định lý 3: Luật kết luận: Nếu A ≡ 1 và A→B ≡1 thì B ≡1.
  22. MỘT SỚLU ẬT TƯƠNG ĐƯƠNG T Tên luật Cơng thức T 1 Luật phủ định kép AA 2 Luật giao hốn đối với phép tuyển ABBA  3 Luật giao hốn đối với phép hội ABBA  4 Luật kết hợp đối với phép tuyển ABCABCABC      5 Luật kết hợp đối với phép hội ABCABCABC      6 Luật De Morgan đối với phép tuyển ABAB  7 Luật De Morgan đối với phép hội ABAB 
  23. MỘT SỚLU ẬT TƯƠNG ĐƯƠNG TT Tên luật Cơng thức 8 Luật phân bố giữa phép tuyển với phép hội ABCABAC     9 Luật phân bố giữa phép hội với phép tuyển ABCABAC     Luật hấp thụ giữa phép tuyển đối với phép 10 AABA  hội Luật hấp thụ giữa phép hội đối với phép 11 AABA  tuyển 12 Luật khử phép kéo theo ABAB  13 Luật lũy đẳng đối với phép tuyển AAA 14 Luật lũy đẳng đối với phép hội AAA
  24. MỘT SỚLU ẬT TƯƠNG ĐƯƠNG TT Tên luật Cơng thức 15 Luật trung hịa đối với hằng sai AA 0 16 Luật trung hịa đối với hằng đúng AA 1 17 Luật thống trị đối với hằng đúng A 11 18 Luật thống trị đối với hằng sai A 00 19 Luật phần tử bù đối với phép tuyển AA 1 20 Luật phần tử bù đối với phép hội AA 0
  25. LOGIC MỆNH ĐỀ a) Mệnh đề, mệnh đề cĩ điều kiện và sự tương đương logic. b) Dạng chuẩn tắc hội và chuẩn tắc tuyển của cơng thức. c) Các phương pháp kiểm tra tính hằng đúng, hằng sai của cơng thức.
  26. TUYỂN SƠ CẤP VÀ HỘI SƠ CẤP1 ( /2) Tuyển sơ cấp (TSC) là tuyển của các biến mệnh đề hoặc phủ định của chúng Ví dụ 17: A  B  C, A  B  ¬C là các tuyển sơ cấp. (A  B)  C khơng phải là tuyển sơ cấp Hội sơ cấp (HSC) là hội của các biến mệnh đề hoặc phủ định của chúng Ví dụ 18: A  B Chú ý: theo luật lũy đẳng, mỗi biến mệnh đề vừa là TSC, vừa là HSC. Định lý 4: Điều kiện cần và đủ để TSC (HSC) đồng nhất đúng (đồng nhất sai) là trong TSC (HSC) cĩ chứa một biến đồng thời với phủ định của biến đó.
  27. DẠNG CHUẨN TẮC HỘI VÀ CHUẨN TẮC TUYỂN CỦA CƠNG THỨC Dạng chuẩn tắc hội (DCTH) là hội của các tuyển sơ cấp (TSC): DCTH  TSC 1  TSC 2   TSC n n 1 Dạng chuẩn tắc tuyển (DCTT) là tuyển của các hội sơ cấp (HSC): DCTT  HSC 1  HSC 2   HSC n n 1 Ta nĩi cơng thức A cĩ DCTH (DCTT) là B khi và chỉ khi A≡B với: B  TSC 1  TSC 2   TSC n B  HSC 1  HSC 2   HSC n
  28. MỘT SỚ TÍNH CHẤT Định lý 5: Mọi cơng thức A trong logic mệnh đề đều cĩ dạng chuẩn tắc hội và dạng chuẩn tắc tuyển. Định lý 6: Điều kiện cần và đủ để cơng thức A≡1 (A≡0) là trong DCTH của A (trong dạng DCTT của A) mỗi TSC (mỗi HSC) cĩ chứa một biến mệnh đề cùng với phủ định của nĩ
  29. LOGIC MỆNH ĐỀ a) Mệnh đề, mệnh đề cĩ điều kiện và sự tương đương logic. b) Dạng chuẩn tắc hội và chuẩn tắc tuyển của cơng thức. c) Các phương pháp kiểm tra tính hằng đúng, hằng sai của cơng thức.
  30. CÁC PHƯƠNG PHÁP KIỂM TRA TÍNH HẰNG ĐÚNG, HẰNG SAI CỦA CƠNG THỨC 1. Phương pháp lập bảng 2. Phương pháp biển đổi tương đương 3. Phương pháp suy diễn 4. Phương pháp phản chứng
  31. PHƯƠNG PHÁP LẬP BẢNG Giả sử A(X1, X2, , Xn) là cơng thức của n biến X1, X2, , Xn. Để tìm giá trị chân lý của A đối với mỗi bộ giá trị đúng, sai của n biến, ta lập bảng gồm 2n hàng, với cột đầu tiên là cột các giá trị chân lý của các biến X1, X2, , Xn , các cột tiếp theo dùng để tính giá trị chân lý của các cơng thức con trong cơng thức A(X1, X2, , Xn) và cột cuối cùng tính giá trị chân lý của A(X1, X2, , Xn) X1 X2 Xn A1 A(X1, X2, , Xn) Nếu cột cuối cùng chứa tồn số 1 0 0 0 A(0,0, ,0) thì A là ct hằng đúng. 1 0 0 A(1,0, ,0) Nếu cột cuối cùng chứa tồn số 0 thì A là ct hằng sai. 0 1 1 A(0,1, ,1) Nếu cột cuối cùng cĩ cả 0 lẫn 1 1 1 1 A(1,1, ,1) thì A là ct thực hiện được.
  32. VÍ DỤ Ví dụ 19: Kiểm tra xem các cơng thức dưới đây là hằng đúng, hằng sai hay thực hiện được : 1. (X Λ Y) → X 2. [(X→Y) Λ (Y→Z)] →(X→Z) KT cơng thức 1. X Y X Λ Y (X Λ Y) → X 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1
  33. VÍ DỤ KT cơng thức 2:[(X→Y) Λ (Y→Z)] →(X→Z) (X→Y) Λ Cơng X Y Z X→Y Y→Z X→Z (Y→Z) thức 2 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1
  34. PHƯƠNG PHÁP BIẾN ĐỞI TƯƠNG ĐƯƠNG 1. Tìm dạng chuẩn tắc hội (tuyển) của cơng thức A. 2. Sử dụng định lý 4 để kt tính hằng đúng hằng sai. (Điều kiện cần và đủ để cơng thức A≡1 (A≡0) là trong DCTH (DCTT) của A mỗi TSC (mỗi HSC) cĩ chứa một biến mệnh đề cùng với phủ định của nĩ) a. Nếu trong DCTH của A, mỗi TSC chứa X và ¬X thì A ≡1. b. Nếu trong DCTT của A, mỗi HSC chứa X và ¬X thì A ≡0. c. Ngược lại, A là thực hiện được.
  35. THUẬT TOÁN TÌM DCTH (DCTT) CỦA CT  Bước 1: Trong A ta khử phép kéo theo (nếu cĩ) bằng cách áp dụng luật khử phép kéo theo (X Y  X  Y ) ta được A≡A1 (A1 khơng cịn phép kéo theo).  Bước 2: Trong A1 ta đưa phép tốn phủ định về trực tiếp liên quan tới từng biến mệnh đề ta được A2 bằng cách áp dụng luật De Morgan ( A  B  A  B hay A  B  A  B )  Bước 3: Đưa A2 về DCTH (DCTT) bằng luật phân bố: X  Y  Z  X  Y  X  Z hoặc X  Y  Z  X Y  X  Z Ta được A2 ≡ A3 (hoặc ≡ A4), với A3  DCTH  TSC 1  TSC 2   TSC n A4  DCTT  HSC 1  HSC 2   HSC m
  36. VÍ DỤ Ví dụ 20: Chứng minh tính hằng sai của cơng thức: AXYXYX     AXYXYX      XYXXYX      DCTT 0
  37. VÍ DỤ Ví dụ 21: Chứng minh tính hằng đúng của cơng thức sau: A  X Y X Z X Y Z AXYXZXYZ XYXZXYZ     XYXZXYZ      khử phép kéo theo  XYXZXYZ         XYXZXYZ       đưa phủ định về trực tiếp từng biến  XXYXZXYZ         YXZXYZ      SD luật phân phối  YXZXYXZYYXZZ   DCTH 1
  38. PHƯƠNG PHÁP SUY DIỄN Mơ hình suy diễn. • Một trong những phương pháp dùng để chứng minh một mệnh đề tốn học là đúng, thường có dạng lý luận với dẫn xuất sau: Nếu A1 và A2 và và An thì B • Dạng lý luận này được xem là hợp lý nếu cơng thức (A1Λ A1Λ ΛAn)→B≡1 (hằng đúng) A1 • Mơ hình suy diễn cơng thức trên có dạng: A2 An  B
  39. CÁC QUY TẮC SUY DIỄN CƠ BẢN TT Tên quy tắc Cơng thức cơ sở Mơ hình suy diễn A 1 Luật cộng A A B 1  A B A 2 Luật rút gọn A B A 1 B  A A Luật Modus Pones 3 A A B B 1 A B – khẳng định  B A B Luật Modus Tollens 4 B – phủ định A B  B A 1  A
  40. CÁC QUY TẮC SUY DIỄN CƠ BẢN TT Tên quy tắc Cơng thức cơ sở Mơ hình suy diễn A  B Luật tam đoạn 5 A B  A B 1 A luận tuyển  B A B 6 Luật bắc cầu A B  B C A C 1 B C  A C A1 A AAAB    1 Luật mâu 12 n 7 An thuẫn AAAB12  n  0  1 An B B 0 A B Luật từng 8 A B  D B A D B 1 D B trường hợp  A D B
  41. QUAN HỆ GIỮA CÁC CƠNG THỨC CƠ SỞ VỚI MƠ HÌNH SUY DIỄN CỦA NĨ Cơng thức cơ sở (A1Λ A2Λ ΛAn)→B hằng đúng khi và chỉ khi mơ hình suy diễn của nĩ là đúng. A1 A2 Mơ hình suy diễn của cơng thức cơ sở: An  B
  42. VÍ DỤ Ví dụ 22: Kiểm tra tính hằng đúng của cơng thức: X  A B  AC  C  D B  D B AB A B A B AC A  C A A  C CD C  D A  C C C  D BD D C C 0 1  B  D 0 0 0 0 0 Luật mâu thuẫn [7] Luật Luật tam Modus đoạn Tollens [4] luận và luật tam tuyển [5] đoạn luận tuyển [5]
  43. VÍ DỤ Ví dụ 23: Kiểm tra tính hằng đúng của cơng thức: XABACBCC    AB AC AB BC ABC C 1 C C C Luật mâu Luật từng Luật Modus thuẫn [7] trường hợp Pones – khẳng [8] định [3]
  44. PHƯƠNG PHÁP PHẢN CHỨNG Để chứng minh tính hằng đúng của một cơng thức, ta giả sử tồn tai một bộ giá trị của các biến mệnh đề sao cho cơng thức đó nhận giá trị chân lý 0, sau đó lập luận dựa trên tính chất của các phép tốn logic để chỉ ra tồn tại mẫu thuẫn. Ví dụ 24: chứng minh tính hằng đúng của cơng thức sau: A  X Y X Z X Y Z Giả sử tồn tại một bộ giá trị của X, Y, Z sau cho A = 0: XY 1 (1) XYXZ 1 XYXZ 0 XZ 0 (2) XYZ 0 XYZ 1 XYZ 1 (3) (3) ZX 00 XZYZYXY1; 0 1 0 0(mẫu thuẫn với (1)).
  45. CHỨNG MINH 2 CT ĐỜNG NHẤT BẰNG NHAU Phương pháp: 1. Lập bảng giá trị chân lý (Giả sử A, B là 2 CT của n biến X1, X2, , Xn. Để tìm giá trị chân lý của A, B đối với mỗi bộ giá trị đúng, sai của n biến, ta lập bảng gồm n 2 hàng, với cột đầu tiên là cột các giá trị chân lý của các biến X1, X2, , Xn , các cột tiếp theo dùng để tính giá trị chân lý của các cơng thức con trong cơng thức A, B và 2 cột cuối cùng tính giá trị chân lý của A, B. Nếu giá trị ở 2 cột này tương ứng giống nhau thì A  B). 2. Biến đổi tương đương (2 CT tương đương cĩ DCTT, DCTH giống nhau).
  46. VÍ DỤ Ví dụ 25: CM 2 cơng thức sau đồng nhất bằng nhau: AXYZ BYXZ Cách 1: Lập bảng chân lý X Y Z Y→Z X→Z X Y Z Y X Z 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 X Y Z  Y X Z
  47. VÍ DỤ Ví dụ 25(tiếp): CM 2 cơng thức sau đồng nhất bằng nhau: AXYZ BYXZ Cách 2: Biến đổi tương đương (Đưa cả hai CT về DCTT hoặc DCTH) XYZXYZ   YXZYXZ   XYZ   YXZ   XYZ   YXZ   XYZ   X Y Z  Y X Z
  48. BÀI TẬP 1. Chứng minh tính hằng đúng của các cơng thức sau bằng 2 phương pháp lập bảng và biến đổi tương đương: AXYX  BXYXZYZZ ()()()    CXYXZXYZ 2. Chứng minh các cơng thức sau đồng nhất bằng nhau bằng 2 phương pháp lập bảng và biến đổi tương đương X Y Z  X Y Z X Y  X Z  X Y  Z X Y  X Y  X  0
  49. BÀI TẬP 3. Sử dụng mơ hình suy diễn chứng minh tính hằng đúng của các cơng thức sau: AXYXY  () BXYXY  ()  4. Tìm cơng thức đối ngẫu của các cơng thức sau: A XYZ    BXYZZ   