›
›

Bài giảng môn Toán rời rạc - Chương 1: Cơ Sở Logic

ppt 78 trang Đức Chiến 03/01/2024 1450
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Toán rời rạc - Chương 1: Cơ Sở Logic", để 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:

  • pptbai_giang_mon_toan_roi_rac_chuong_1_co_so_logic.ppt

Nội dung text: Bài giảng môn Toán rời rạc - Chương 1: Cơ Sở Logic

  1. ChươngChương 1:1: CơCơ SởSở LogicLogic Author:Author: NguyNguyễnễn ViếtViết HưngHưng Editor:Editor: TrTrầnần SơnSơn HảiHải 1/9/2024 1 of 78
  2. Tài liệu tham khảo • Tốn rời rạc, Gs.Ts Nguyễn Hữu Anh • Michael P.Frank ‘s slides • Nguyễn Viết Hưng ‘s slides • Tốn rời rạc, Ts. Trần Ngọc Hội 1/9/2024 2 of 78
  3. CƠ SỞ LOGIC Logic tốn học là một cơng cụ để làm việc với những phát biểu tổng hợp phức tạp. Nĩ bao gồm : • Một ngơn ngữ để thể hiện. • Một ký hiệu ngắn gọn để viết. • Một phương pháp luận giải thích khách quan vì sao chúng đúng hay sai. • Nĩ là cơ sở để thể hiện cĩ những chứng minh hình thức trong tất cả các ngành của tốn học. 1/9/2024 3 of 78
  4. Propositional Logic Propositional Logic is the logic of compound statements built from simpler statements using so-called Boolean connectives. Some applications in computer science: George Boole (1815-1864) • Design of digital electronic circuits. • Expressing conditions in programs. • Queries to databases & search engines. Chrysippus of Soli 1/9/2024 4 of 78 (ca. 281 B.C. – 205 B.C.)
  5. Mệnh đề và chân trị • Khái niệm về mệnh đề: – Mệnh đề tốn học là khái niệm cơ bản của tốn học khơng được định nghĩa mà chỉ được mơ tả. • Mệnh đề tốn học(gọi tắt là mệnh đề) là một khẳng định cĩ giá trị chân lý xác định(đúng hoặc sai, nhưng khơng thể vừa đúng vừa sai). 1/9/2024 5 of 78
  6. Mệnh đề và chân trị • Ví dụ: – “Số 123 chia hết cho 3” là 1 mệnh đề đúng – “Thành phố Hồ Chí Minh là thủ đơ của nước Việt Nam” là một mệnh đề sai. – “Bạn cĩ khỏe khơng ? ” khơng phải là một mệnh đề tốn học vì đây là một câu hỏi khơng thể phản ánh một điều đúng hay một điều sai 1/9/2024 6 of 78
  7. Mệnh đề và chân trị • Kiểm tra xem các khẳng định sau cĩ là mệnh đề khơng? Nếu cĩ, đĩ là mệnh đề đúng hay sai? – Mơn Tốn rời rạc là mơn bắt buộc chung cho ngành tin học. – 97 là số nguyên tố. – N là số nguyên tố 1/9/2024 7 of 78
  8. Mệnh đề và chân trị • Ký hiệu mệnh đề : – Người ta thường dùng các ký hiệu : P, Q, R, • Chú ý: Mệnh đề phức hợp là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết của chúng lại bằng các liên từ(và, hay, nếu thì ) hoặc trạng từ “khơng” – Ví dụ : Nếu trời tốt thì tơi đi dạo. 1/9/2024 8 of 78
  9. Mệnh đề và chân trị • Chân trị của mệnh đề: – Theo khái niệm, một mệnh đề chỉ cĩ thể đúng hoặc sai, khơng thể đồng thời vừa đúng vừa sai. Khi mệnh đề p đúng ta nĩi P cĩ chân trị đúng, ngược lại ta nĩi P cĩ chân trị sai. – Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1(hay Đ,T) và 0(hay S,F) 1/9/2024 9 of 78
  10. Phép tính mệnh đề • Mục đích của phép tính mệnh đề: – Nghiên cứu chân trị của một mệnh đề phức hợp từ chân trị của các mệnh đề đơn giản hơn và các phép nối những mệnh đề này biểu hiện qua liên từ hoặc trạng từ “khơng” 1/9/2024 10 of 78
  11. Some Popular Boolean Operators Formal Name Nicknam Arity Symbol e Negation operator NOT Unary ¬ Conjunction operator AND Binary  Disjunction operator OR Binary  Exclusive-OR XOR Binary  operator Implication operator IMPLIES Binary Biconditional IFF Binary ↔ operator 1/9/2024 11 of 78
  12. Phép tính mệnh đề 1/9/2024 12 of 78
  13. Phép tính mệnh đề 1/9/2024 13 of 78
  14. Phép tính mệnh đề • Phép nối liền(phép hội; phép giao): – Mệnh đề nối liền của hai mệnh đề P, Q được kí hiệu bởi P  Q (đọc là “P và Q”), là mệnh đề được định bởi : – P  Q đúng khi và chỉ khi P và Q đồng thời đúng 1/9/2024 14 of 78
  15. Phép tính mệnh đề • Ví dụ: Mệnh đề “Hơm nay, cơ ấy đẹp và thơng minh ” chỉ được xem là mệnh đề đúng khi cả hai điều kiện “cơ ấy đẹp” và “cơ ấy thơng minh” đều xảy ra. Ngược lại, chỉ 1 trong 2 điều kiện trên sai thì mệnh đề trên sẽ sai. 1/9/2024 15 of 78
  16. PhépPhép tínhtính mệnhmệnh đềđề • Mệnh đề “Hơm nay, An giúp mẹ lau nhà và rửa chén” chỉ đúng khi hơm nay An giúp mẹ cả hai cơng việc lau nhà và rửa chén. Ngược lại, nếu hơm nay An chỉ giúp mẹ một trong hai cơng việc trên, hoặc khơng giúp mẹ cả hai thì mệnh đề trên sai. 1/9/2024 16 of 78
  17. Phép tính mệnh đề 1/9/2024 17 of 78
  18. Phép tính mệnh đề • Phép nối rời(phép tuyển; phép hợp) – Mệnh đề nối rời của hai mệnh đề P, Q được kí hiệu bởi P  Q (đọc là “P hay Q”), là mệnh đề được định bởi : – P  Q sai khi và chỉ khi P và Q đồng thời sai 1/9/2024 18 of 78
  19. Phép tính mệnh đề • Ví dụ: Mệnh đề “Tơi đang chơi bĩng đá hay bĩng rổ”. – Mệnh đề này chỉ sai khi tơi vừa khơng đang chơi bĩng đá cũng như vừa khơng đang chơi bĩng rổ. – Ngược lại, tơi chơi bĩng đá hay đang chơi bĩng rổ hay đang chơi cả hai thì mệnh đề trên đúng. 1/9/2024 19 of 78
  20. Phép tính mệnh đề 1/9/2024 20 of 78
  21. Phép tính mệnh đề • Chú ý : – Cần phân biệt “hay” và “hoặc”. – Đưa ra phép tốn để thể hiện trường hợp loại trừ – Ký hiệu : – P Q sai P và Q đồng thời cùng đúng hoặc cùng sai. 1/9/2024 21 of 78
  22. Phép tính mệnh đề • Phép kéo theo: – Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí hiệu bởi P Q(đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”) là mệnh đề được định bởi: – P Q sai P đúng và Q sai 1/9/2024 22 of 78
  23. Phép tính mệnh đề • Ví dụ: Xét mệnh đề sau : “Nếu bạn đẹp trai thì bạn cĩ nhiều bạn gái” Ta cĩ các trường hợp sau: • bạn đẹp trai và cĩ nhiều bạn gái : Mệnh đề rõ ràng đúng • bạn đẹp trai và khơng cĩ nhiều bạn gái : Mệnh đề rõ ràng sai • bạn khơng đẹp trai mà vẫn cĩ nhiều bạn gái : Mệnh đề vẫn đúng • bạn khơng đẹp trai và khơng cĩ nhiều bạn gái : Mệnh đề vẫn đúng 1/9/2024 23 of 78
  24. Phép tính mệnh đề • Mệnh đề “Chiều nay, nếu rảnh tơi sẽ ghé thăm bạn” chỉ sai khi chiều nay tơi rảnh nhưng tơi khơng ghé thăm bạn. • Ngược lại, nếu chiều nay tơi bận thì dù tơi cĩ ghé thăm bạn hay khơng, mệnh đề trên vẫn đúng. Ngồi ra, tất nhiên nếu chiều nay tơi cĩ ghé thăm bạn thì mệnh đề trên đúng (dù tơi cĩ rảnh hay khơng!). 1/9/2024 24 of 78
  25. Phép tính mệnh đề • Chú ý: – Liên hệ phép kéo theo và cú pháp If P then Q trong ngơn ngữ lập trình • P,Q là 2 mệnh đề P là mệnh đề, Q là dãy dịng lệnh – Ngơn ngữ hằng ngày, cĩ sự nhầm lẫn giữa phép kéo theo và phép kéo theo hai chiều. • “Giáo viên khoa Tốn dạy nghiêm túc” 1/9/2024 25 of 78
  26. Phép tính mệnh đề 1/9/2024 26 of 78
  27. Phép tính mệnh đề • Phép kéo theo hai chiều: – Mệnh đề P kéo theo Q và ngược lại của hai mệnh đề P và Q, ký hiệu bởi P  Q (đọc là “P nếu và chỉ nếu Q” hay P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của Q”), là mệnh đề được định bởi: P  Q đúng khivà chỉ khi P và Q cĩ cùng chân trị, 1/9/2024 27 of 78
  28. Phép tính mệnh đề 1/9/2024 28 of 78
  29. Phép tính mệnh đề 1/9/2024 29 of 78
  30. The biconditional operator The biconditional p  q states that p is true if and only if (IFF) q is true. p = “Bush wins the 2004 election.” q = “Bush will be president for all of 2005.” p  q = “If, and only if, Bush wins the 2004 election, Bush will be president for all of 2005.” I’m still here! 1/9/2024 30 of 78 2004 2005
  31. Biconditional Truth Table • p  q means that p and q have the same truth value. • Note this truth table is the exact opposite of ’s! – p  q means ¬(p  q) • p  q does not imply p and q are true, or cause each other. 1/9/2024 31 of 78
  32. Tĩm lại • Ta cĩ bảng chân trị của một số phép tốn mệnh đề như sau: 1/9/2024 32 of 78
  33. Một số ký hiệu tương đương 1/9/2024 33 of 78
  34. Câu Hỏi và Ơn Tập P Q P và P hay P kéo P nếu P Khơn Q Q theo và chỉ hoặc g P Q nếu Q Q (loại trừ) P Q Ký Ký Ký Ký Ký Ký hiệu? hiệu? hiệu? hiệu? hiệu? hiệu? 1 1 ? ? ? ? ? ? 1 0 ? ? ? ? ? ? 0 1 ? ? ? ? ? ? 0 0 ? ? ? ? ? ? 1/9/2024 34 of 78
  35. 1/9/2024 35 of 78
  36. Dạng mệnh đề • Một dạng mệnh đề là một biểu thức được cấu tạo từ: – Các hằng mệnh đề, tức là các mệnh đề đã xét ở trên. – Các biến mệnh đề, tức là các biến lấy giá trị là các mệnh đề, thơng qua các phép tốn mệnh đề đã xét ở mục trên theo một trình tự nhất định nào đĩ, thường được chỉ rõ bởi các dấu ngoặc. 1/9/2024 36 of 78
  37. Dạng mệnh đề • Với E là một dạng mệnh đề các biến mệnh đề p, q, r ứng với mỗi giá trị cụ thể P, Q, R (là các mệnh đề) của p, q, r thì ta cĩ duy nhất một mệnh đề E(P, Q, R). Ta viết E = E(p, q, r). • Bảng chân trị là bảng ghi tất cả các trường hợp chân trị cĩ thể xảy ra đối với dạng mệnh đề E theo chân trị của các biến mệnh đề p, q, r. Nếu cĩ n biến, bảng này sẽ cĩ 2n dịng, chưa kể dịng tiêu đề. 1/9/2024 37 of 78
  38. 1/9/2024 38 of 78
  39. Dạng mệnh đề 1/9/2024 39 of 78
  40. Chứng minh bằng bảng chân trị CMR: pq (p  q). F T T T F T T F F T T F T F T T F F F T 1/9/2024 40 of 78
  41. Dạng mệnh đề Các luật logic : Với p, q, r là các biến mệnh đề, 1 là một hằng đúng và 0 là một hằng sai, ta cĩ các tương đương logic sau đây: 1) Luật lũy đẳng p  p p và p  p p 1/9/2024 41 of 78
  42. DạngDạng mệnhmệnh đềđề 1/9/2024 42 of 78
  43. 1/9/2024 43 of 78
  44. 1/9/2024 44 of 78
  45. 1/9/2024 45 of 78
  46. 1/9/2024 46 of 78
  47. Dạng mệnh đề 16) Luật về phép kéo theo: p q p  q 17) Luật rút gọn: p q p 1(*) p (p q) p q (p  q) q p q p (p  q) 1(*) 1/9/2024 47 of 78
  48. Dạng mệnh đề • Chứng minh dạng mệnh đề ta cĩ các cách sau: – Lập bảng chân trị. – Sử dụng phép thay thế. 1/9/2024 48 of 78
  49. Dạng mệnh đề 1. Quy tắc thay thế thứ 1: Trong dạng mệnh đề E, nếu ta thay thế biểu thức con F bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được vẫn cịn tương đương logic với E. p v (q r) p v (q  r) vì (q r q  r) 1/9/2024 49 of 78
  50. Dạng mệnh đề 2. Quy tắc thay thế thứ 2: Giả sử dạng mệnh đề E(p,q,r ) là một hằng đúng. Nếu ta thay thế những nơi p xuất hiện trong E bởi một F(p’,q’,r’) thì dạng mệnh đề nhận được theo các biến q,r ,p’,q’,r’, vẫn cịn là 1 hằng đúng. Ví dụ: p  p 1, thay p bởi q V (r s) ta được (q V (r s)) V (q V (r s)) 1 1/9/2024 50 of 78
  51. 1/9/2024 51 of 78
  52. 1/9/2024 52 of 78
  53. 1/9/2024 53 of 78
  54. Qui Tắc Suy Diễn • Trong các chứng minh tốn học,xuất phát từ một số khẳng định đúng p, q, r (tiên đề), ta áp dụng các qui tắc suy diễn để suy ra chân lí của một mệnh đề h mà ta gọi là kết luận. • Nĩi cách khác, dùng các qui tắc suy diễn để chứng minh: ( p  q  r  ) h là một khẳng định đúng. 1/9/2024 54 of 78
  55. Qui Tắc Suy Diễn Khẳng định (1) cĩ dạng: ((tiên đề 1)  (tiên đề 2)  ) kết luận Do đĩ nếu chứng minh được dạng mệnh đề trên là một hằng đúng thì khẳng định (1) chắc chắn là đúng. Ta thường mơ hình hĩa (2): tiên đề (1) tiên đề (2)  kết luận Aristotle 1/9/2024 (ca. 384-32255 B.C.) of 78
  56. Aristotle 1/9/2024 (ca. 384-32256 B.C.) of 78
  57. Qui Tắc Suy Diễn • QUI TẮC MODUS PONENS(Phương pháp khẳng định) Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ 1/9/2024 57 of 78
  58. •Nếu An học chăm thì An học tốt. •Mà An học chăm Suy ra An học tốt •Hình vuơng là hình bình hành •Mà hình bình hành cĩ hai đường chéo cắt nhau tại trung điểm mỗi đường. Suy ra hình vuơng cĩ hai đường chéo cắt nhau tại trung điểm mỗi đường Aristotle 1/9/2024 (ca. 384-32258 B.C.) of 78
  59. Qui Tắc Suy Diễn • QUI TẮC TAM ĐOẠN LUẬN(Syllogism) Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ Aristotle 1/9/2024 (ca. 384-32259 B.C.) of 78
  60. •Hai tam giác vuơng cĩ cạnh huyền và 1 cặp gĩc nhọn bằng nhau thì chúng ta cĩ một cạnh bằng nhau kèm giữa hai gĩc bằng nhau. •Nếu hai tam giác cĩ cạnh bằng nhau kèm giữa hai gĩc bằng nhau thì chúng bằng nhau Suy ra hai tam giác vuơng cĩ cạnh huyền và 1 cặp gĩc nhọn bằng nhau thì bằng nhau. •Một con ngựa rẻ là một con ngựa hiếm •Cái gì hiếm thì đắt Suy ra một con ngựa rẻ thì đắt () 1/9/2024 60 of 78
  61. Qui Tắc Suy Diễn • QUI TẮC MODUS TOLLENS PHƯƠNG PHÁP PHỦ ĐỊNH Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ Aristotle 1/9/2024 (ca. 384-32261 B.C.) of 78
  62. • Xét chứng minh • Ta suy luận Aristotle 1/9/2024 (ca. 384-32262 B.C.) of 78
  63. Qui Tắc Suy Diễn • QUI TẮC TAM ĐOẠN LUẬN RỜI Qui tắc này được thể hiện bằng hằng đúng: Ý nghĩa của qui tắc: nếu trong hai trường hợp cĩ thể xảy ra, chúng ta biết cĩ một trường hợp sai thì chắc chắn trường hợp cịn lại sẽ đúng 1/9/2024 63 of 78
  64. Qui Tắc Suy Diễn • QUI TẮC MÂU THUẪN CHỨNG MINH BẰNG PHẢN CHỨNG Ta cĩ tương đương logic • Ta cần chứng minh vế trái cũng là một hằng đúng hay nĩi cách khác chứng minh khi thêm phủ định của q vào các tiền đề ta được một mâu thuẫn. 1/9/2024 64 of 78
  65. VÍ DỤ • Hãy chứng minh: • Cm bằng phản chứng. 1/9/2024 Aristotle65 of 78 (ca. 384-322 B.C.)
  66. Qui Tắc Suy Diễn • CHỨNG MINH THEO TRƯỜNG HỢP Dựa trên hằng đúng: • Ý nghĩa: nếu từ p và q cĩ thể suy ra r thì từ dạng p hay q cũng cĩ thể suy ra r. 1/9/2024 66 of 78
  67. VÍ DỤ • Chứng minh rằng: Aristotle 1/9/2024 (ca. 384-32267 B.C.) of 78
  68. Một số luật thêm • p Rule of Addition(Phép thêm)  pq • pq Phép đơn giản nối liền •  p • p Luật về phép nối q  pq 1/9/2024 Aristotle68 of 78 (ca. 384-322 B.C.)
  69. VÍ DỤ TỔNG HỢP 1. Nếu nghệ sĩ Trương • p:Nghệ sĩ Trương Ba trình Ba khơng trình diễn diễn. hay số vé bán ra ít hơn • q:số vé bán ra ít hơn 100. 100 thì đêm diễn sẽ bi • r:đêm diễn bị hủy bỏ. hủy bỏ và ơng bầu sẽ rất buồn. • s: ơng bầu buồn. 2. Nếu đêm diễn bị hủy • t:trả lại vé cho người xem bỏ thì vé phải trả lại cho người xem. 3. Nhưng vé đã khơng trả lại cho người xem. Vậy cĩ kết luân gì? 1/9/2024 69 of 78
  70. Qui Tắc Suy Diễn • PHẢN VÍ DỤ Để chứng minh một phép suy luận là sai hay khơng là một hằng đúng. Ta chỉ cần chỉ ra một phản ví dụ. 1/9/2024 70 of 78
  71. VÍ DỤ • Ơng Minh nĩi rằng nếu • p:ơng Minh được tăng khơng được tăng lương thì lương. ơng ta sẽ nghỉ việc. Mặt • q: ơng Minh nghỉ việc. khác, nếu ơng ấy nghỉ việc và vợ ơng ấy bị mất việc thì • r:vợ ơng Minh mất việc. phải bán xe.Biết rằng nếu • s:gia đình phải bán xe. vợ ơng Minh hay đi làm trễ • t:vợ ơng hay đi làm trể. thì trước sau gì cũng sẽ bị mất việc và cuối cùng ơng Minh đã được tăng lương. s=0 • Suy ra nếu ơng Minh khơng t=1 bán xe thì vợ ơng ta đã p=1 khơng đi làm trễ q=0 r=1 1/9/2024 71 of 78
  72. Qui Tắc Suy Diễn 1/9/2024 72 of 78
  73. 1/9/2024 73 of 78
  74. Qui Tắc Suy Diễn 1/9/2024 74 of 78
  75. QuiQui TắcTắc SuySuy DiễnDiễn 1/9/2024 75 of 78
  76. Qui Tắc Suy Diễn 1/9/2024 76 of 78
  77. Qui Tắc Suy Diễn 1/9/2024 77 of 78
  78. à 1/9/2024 78 of 78