Bài giảng Toán rời rạc - Phần I: Mệnh đề - Nguyễn Viết Đông

Nội dung text: Bài giảng Toán rời rạc - Phần I: Mệnh đề - Nguyễn Viết Đông

1. 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 Phần I.Mệnh đề • Nguyễn Viết Hưng „s slides • Tốn rời rạc, TS. Trần Ngọc Hội Biên soạn : TS.Nguyễn Viết Đơng 1 2 Mệnh đề và chân trị Mệnh đề và chân trị • Khái niệm về mệnh đề: • Ví dụ: Mệnh đề tốn học là khái niệm cơ bản của tốn – “Số 123 chia hết cho 3” là 1 mệnh đề đúng học khơng được định nghĩa mà chỉ được mơ tả. – “Thành phố Hồ Chí Minh là thủ đơ của nước Việt Mệnh đề tốn học(gọi tắt là mệnh đề) là một Nam” là một mệnh đề sai. khẳng định cĩ giá trị chân lý xác định(đúng – “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 hoặc sai, nhưng khơng thể vừa đúng vừa sai). ánh một điều đúng hay một điều sai 3 4 1
2. Mệnh đề và chân trị Mệnh đề và chân trị • Kiểm tra xem các khẳng định sau cĩ là mệnh • Ký hiệu mệnh đề : đề khơng? Nếu cĩ, đĩ là mệnh đề đúng hay Người ta thường dùng các ký hiệu : P, Q, R, sai? • Chú ý: Mệnh đề phức hợp là mệnh đề được – Mơn Tốn rời rạc là mơn bắt buộc chung cho xây dựng từ các mệnh đề khác nhờ liên kết ngành Tin học. chúng lại bằng các liên từ(và, hay, nếu thì ) – 97 là số nguyên tố. hoặc trạng từ “khơng” – N là số nguyên tố. – Ví dụ : Nếu trời tốt thì tơi đi dạo. 5 6 Mệnh đề và chân trị Phép tính mệnh đề • Chân trị của mệnh đề: • Mục đích của phép tính mệnh đề: Một mệnh đề chỉ cĩ thể đúng hoặc sai, khơng thể Nghiên cứu chân trị của một mệnh đề phức hợp từ đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng chân trị của các mệnh đề đơn giản hơn và các phép ta nĩi P cĩ chân trị đúng, ngược lại ta nĩi P cĩ nối những mệnh đề này biểu hiện qua liên từ hoặc chân trị sai. trạng từ “khơng” Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1hay Đ(đúng),T(true) và 0 hay S(sai),F(false) 7 8 2
3. Some Popular Boolean Phép tính mệnh đề Operators Formal Name Nickname Arity Symbol Phủ định của mệnh đề Negation operator NOT Unary ¬ Conjunction operator AND Binary  Disjunction operator OR Binary  Exclusive-OR operator XOR Binary  Implication operator IMPLIES Binary Biconditional operator IFF Binary ↔ Phép tính mệnh đề Phép tính mệnh đề The unary negation operator “¬” (NOT) transforms a prop. into its logical negation. p E.g. If p = “I have brown hair.” p then ¬p = “I do not have brown hair.” T F F T 11 3
4. Phép tính mệnh đề Phép tính mệnh đề • Phép nối liền(phép hội; phép giao): • Ví dụ: Mệnh đề “Hơm nay, cơ ấy đẹp và thơng Mệnh đề nối liền của hai mệnh đề P, Q được kí hiệu minh ” chỉ được xem là mệnh đề đúng khi cả bởi P  Q (đọc là “P và Q”), là mệnh đề được định hai điều kiện “cơ ấy đẹp” và “cơ ấy thơng bởi : minh” đều xảy ra. Ngược lại, chỉ 1 trong 2 P  Q đúng khi và chỉ khi P và Q đồng thời đúng điều kiện trên sai thì mệnh đề trên sẽ sai. 13 14 Phép tính mệnh đề The Conjunction Operator • Mệnh đề “Hôm nay, An giúp mẹ lau nhà và The binary conjunction operator “” (AND) rửa chén” chỉ đúng khi hôm nay An giúp mẹ combines two propositions to form cả hai công việc lau nhà và rửa chén. Ngược their logical conjunction. lại, nếu hôm nay An chỉ giúp mẹ một trong ND E.g. If p=“I will have salad for lunch.” and q=“I hai công việc trên, hoặc không giúp mẹ cả hai thì mệnh đề trên sai. will have steak for dinner.”, then pq=“I will have salad for lunch and I will have steak for dinner.” Remember: “” points up like an “A”, and it means “ND” 15 16 4
5. Conjunction Truth Table Phép tính mệnh đề • Note that a p q pq conjunction F F F p1  p2   pn F T F of n propositions T F F n will have 2 rows T T T in its truth table. • Also: ¬ and  operations together are suffi- cient to express any Boolean truth table! Operand columns 17 18 Phép tính mệnh đề Phép tính mệnh đề • Phép nối rời(phép tuyển; phép hợp) • Ví dụ: Mệnh đề “Tơi đang chơi bĩng đá hay Mệnh đề nối rời của hai mệnh đề P, Q được kí hiệu bĩng rổ”. bởi P  Q (đọc là “P hay Q”), là mệnh đề được định Mệnh đề này chỉ sai khi tơi vừa khơng đang chơi bởi : bĩng đá cũng như vừa khơng đang chơi bĩng rổ. P  Q sai khi và chỉ khi P và Q đồng thời sai 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. 19 20 5
6. The Disjunction Operator Disjunction Truth Table The binary disjunction operator “” (OR) combines two propositions to form their • Note that pq means p q pq logical disjunction. that p is true, or q is F F F true, or both are true! p=“My car has a bad engine.” F T T Note • So, this operation is difference q=“My car has a bad carburetor.”  T F T from AND also called inclusive or, T T T pq=“Either my car has a bad engine, or because it includes the my car has a bad carburetor.” After the downward- possibility that both p and q are true. pointing “axe” of “” Meaning is like “and/or” in English. splits the wood, you • “¬” and “” together are also universal. can take 1 piece OR the other, or both.21 22 Phép tính mệnh đề 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. 23 6
7. The Exclusive Or Operator Exclusive-Or Truth Table The binary exclusive-or operator “” (XOR) combines two propositions to form their • Note that pq means p q pq logical “exclusive or” (exjunction?). that p is true, or q is true, but not both! F F F p = “I will earn an A in this course,” F T T • This operation is q = “I will drop this course,” T F T called exclusive or, p  q = “I will either earn an A for this course, or T T F Note because it excludes the difference I will drop it (but not both!)” possibility that both p and q are true. from OR. • “¬” and “” together are not universal. 25 26 Phép tính mệnh đề Phép tính mệnh đề • Phép kéo theo: • Ví dụ: Xét mệnh đề sau : Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí “Nếu tơi đẹp trai thì tơi cĩ nhiều bạn gái” Ta cĩ các trường hợp sau: hiệu bởi P Q(đọc là “P kéo theo Q” hay “Nếu P • Tơi đẹp trai và cĩ nhiều bạn gái : Mệnh đề rõ ràng đúng thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều • Tơi đẹp trai và khơng cĩ nhiều bạn gái : Mệnh đề rõ kiện cần của P”) là mệnh đề được định bởi: ràng sai P Q sai khi và chỉ khi P đúng mà Q sai . • Tơi khơng đẹp trai mà vẫn cĩ nhiều bạn gái : Mệnh đề vẫn đúng • Tơi khơng đẹp trai và khơng cĩ nhiều bạn gái : Mệnh đề vẫn đúng 27 28 7
8. Phép tính mệnh đề The Implication Operator • Mệnh đề “Chiều nay, nếu rảnh tôi sẽ ghé The implication p q states that p implies q. thăm bạn” chỉ sai khi chiều nay tôi rảnh antecedent consequent nhưng tôi không ghé thăm bạn. I.e., If p is true, then q is true; but if p is not true, • Ngược lại, nếu chiều nay tôi bận thì dù tôi có then q could be either true or false. ghé thăm bạn hay không, mệnh đề trên vẫn E.g., let p = “You study hard.” đúng. Ngoài ra, tất nhiên nếu chiều nay tôi q = “You will get a good grade.” có ghé thăm bạn thì mệnh đề trên đúng (dù p q = “If you study hard, then you will get a tôi có rảnh hay không!). good grade.” (else, it could go either way) 29 30 Implication Truth Table Examples of Implications • p q is false only when p is true but q is not true. p q p q • “If this lecture ends, then the sun will rise tomorrow.” True or False? • p q does not say F F T • “If Tuesday is a day of the week, then I am that p causes q! F T T The only a penguin.” True or False? • p q does not require T F F False that p or q are ever true! T T T case! • “If 1+1=6, then Bush is president.” True or False? • E.g. “(1=0) pigs can fly” is TRUE! • “If the moon is made of green cheese, then I am richer than Bill Gates.” True or False? 31 32 8
9. Phép tính mệnh đề 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 đề xác định bởi: P  Q đúng khi và chỉ khi P và Q cĩ cùng chân trị 33 34 Phép tính mệnh đề Phép tính mệnh đề 35 36 9
10. Biconditional Truth Table The biconditional operator • p  q means that p and q The biconditional p  q states that p is true if and have the same truth value. p q only if (IFF) q is true. p  q • Note this truth table is the p = “Bush wins the 2004 election.” F F T exact opposite of ‟s! q = “Bush will be president for all of 2005.” F T F – p  q means ¬(p  q) p  q = “If, and only if, Bush wins the 2004 T F F election, Bush will be president for all of 2005.” • p  q does not imply T T T I’m still p and q are true, or cause each other. here! 38 2004 2005 Boolean Operations Summary Some Alternative Notations • We have seen 1 unary operator and 5 binary operators . Their truth tables are below. Name: not and or xor implies iff Propositional logic:      p q p pq pq pq p q pq Boolean algebra: p pq +  F F T F F F T T C/C++/Java (wordwise): ! && || != == F T T F T T T F C/C++/Java (bitwise): ~ & | ^ Logic gates: T F F F T T F F T T F T T F T T 39 10
11. Dạng mệnh đề Dạng mệnh đề • Dạng mệnh đề là một biểu thức được cấu tạo • Với E là một dạng mệnh đề các biến mệnh đề p, q, r từ: ứng với mỗi giá trị cụ thể P, Q, R (là các mệnh đề) - Các hằng mệnh đề, tức là các mệnh đề đã xét ở của p, q, r thì ta cĩ duy nhất một mệnh đề E(P, Q, R). trên. Ta viết E = E(p, q, r). - Các biến mệnh đề, tức là các biến lấy giá trị là • Bảng chân trị là bảng ghi tất cả các trường hợp chân các mệnh đề, thông qua các phép toán mệnh đề trị cĩ thể xảy ra đối với dạng mệnh đề E theo chân trị đã xét ở mục trên theo một trình tự nhất định nào của các biến mệnh đề p, q, r. Nếu cĩ n biến, bảng này đó, thường được chỉ rõ bởi các dấu ngoặc. sẽ cĩ 2n dịng, chưa kể dịng tiêu đề. 41 42 Dạng mệnh đề Tautologies and Contradictions A tautology is a compound proposition that is true no matter what the truth values of its atomic propositions are! Ex. p  p [What is its truth table?] A contradiction is a compound proposition that is false no matter what! Ex. p  p [Truth table?] Other compound props. are contingencies. 43 44 11
12. Proving Equivalence Logical Equivalence via Truth Tables Compound proposition p is logically equivalent Ex. Prove that pq (p  q). to compound proposition q, written p q, IFF the compound proposition pq is a tautology. p q pq p q p  q (p  q) Compound propositions p and q are logically F F F T T T F equivalent to each other IFF p and q contain F T T T F F T the same truth values as each other in all rows T F T F T F T of their truth tables. T T T F F F T 45 46 Dạng mệnh đề Dạng mệnh đề 1. Quy tắc thay thế thứ 1 Các luật logic : Với p, q, r là các biến mệnh Trong dạng mệnh đề E, nếu ta thay thế biểu thức đề, 1 là một hằng đúng và 0 là một hằng sai, ta con F bởi một dạng mệnh đề tương đương logic cĩ các tương đương logic sau đây: thì dạng mệnh đề thu được vẫn cịn tương đương logic với E. 1) Luật luỹ đẳng 2. Quy tắc thay thế thứ 2 p  p p 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‟) p  p p 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. 47 48 12
13. Dạng mệnh đề 49 50 51 52 13
14. Dạng mệnh đề 16) Luật rút gọn: p q p 1 p (p q) p q (p  q) q p q p (p  q) 1 53 54 Equivalence Laws - Examples More Equivalence Laws • Identity: pT p pF p • Distributive: p(qr) (pq)(pr) • Domination: pT T pF F p(qr) (pq)(pr) • Idempotent: pp p pp p • De Morgan’s: • Double negation: p p (pq) p  q (pq) p  q • Commutative: pq qp pq qp • Trivial tautology/contradiction: Augustus • Associative: (pq)r p(qr) p  p T p  p F De Morgan (pq)r p(qr) (1806-1871) 55 14
15. Defining Operators via Equivalences An Example Problem Using equivalences, we can define operators in • Check using a symbolic derivation whether terms of other operators. (p  q) (p  r) p  q  r. • Exclusive or: pq (pq)(pq) (p  q) (p  r) [Expand definition of ] (p  q)  (p  r) pq (pq)(qp) [Defn. of ] (p  q)  ((p  r)  (p  r)) • Implies: p q p  q [DeMorgan’s Law] • Biconditional: pq (p q)  (q p) (p  q)  ((p  r)  (p  r)) pq (pq) [associative law] cont. 57 58 Example Continued End of Long Example (p  q)  ((p  r)  (p  r)) [ commutes] q  (p  (p  r))         (q p) ((p r) (p r)) [ associative] [DeMorgan’s] q  (p  (p  r)) q  (p  ((p  r)  (p  r))) [distrib.  over ] q  (((p  (p  r))  (p  (p  r))) [Assoc.] q  ((p  p)  r) [assoc.] q  (((p  p)  r)  (p  (p  r))) [Idempotent] q  (p  r) [trivail taut.] q  ((T  r)  (p  (p  r))) [Assoc.] (q  p)  r [domination] q  (T  (p  (p  r))) [Commut.] p  q  r [identity] q  (p  (p  r)) cont. Q.E.D. (quod erat demonstrandum) (Which was to be shown.) 59 60 15
16. Dạng mệnh đề Ví dụ • Để chứng minh một dạng mệnh đề là hằng đúng, hằng sai, các dạng mệnh đề là tương Cho p, q, r là các biến mệnh đề. Chứng minh đương lơgic, dạng mệnh đề này là hệ quả rằng: logic của dạng mệnh đề kia, ta cĩ các cách sau: (p r)  (q r) (p q) r (1) - Lập bảng chân trị. Chúng ta cĩ thể chứng minh (1) bằng hai cách. Cách 1: Lập bảng chân trị . - Sử dụng phép thay thế. 61 62 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  ) cĩ hệ quả logic là h . 63 64 16
17. Qui Tắc Suy Diễn Qui Tắc Suy Diễn Ta thường mơ hình hĩa phép suy luận đĩ dưới dạng: p • QUI TẮC MODUS PONENS(Phƣơng pháp khẳng định) q Qui tắc này được thể hiện bằng hằng đúng: r . p q  p q : Hoặc dưới dạng sơ đồ ___ pq h p q 65 •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 Qui Tắc Suy Diễn • QUI TẮC TAM ĐOẠN LUẬN(Syllogism) •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 Qui tắc này được thể hiện bằng hằng đúng: điểm mỗi đường. Suy ra hình vuơng cĩ hai đường chéo cắt nhau tại trung p q  q r p r điểm mỗi đường Hoặc dưới dạng sơ đồ pq qr  pr 67 17
18. Qui Tắc Suy Diễn •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. • QUI TẮC MODUS TOLLENS •Nếu hai tam giác cĩ cạnh bằng nhau kèm giữa hai gĩc PHƢƠNG PHÁP PHỦ ĐỊNH 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 Qui tắc này được thể hiện bằng hằng đúng: nhọn bằng nhau thì bằng nhau. p q   q  p Hoặc dưới dạng sơ đồ pq •Một con ngựa rẻ là một con ngựa hiếm •Cái gì hiếm thì đắt q Suy ra một con ngựa rẻ thì đắt () p 69 Qui Tắc Suy Diễn • Xét chứng minh • Ta suy luận • QUI TẮC TAM ĐOẠN LUẬN RỜI pr pr Qui tắc này được thể hiện bằng hằng đúng: rs rs p q   q p p q   p q ts st tu tu Ý nghĩa của qui tắc: nếu trong hai trường hợp cĩ u u thể xảy ra, chúng ta biết cĩ một trường hợp sai thì p p chắc chắn trường hợp cịn lại sẽ đúng Aristotle (ca. 384-322 B.C.) 71 18
19. VÍ DỤ Qui Tắc Suy Diễn • QUI TẮC MÂU THUẪN • Hãy chứng minh: • Cm bằng phản chứng. pr CHỨNG MINH BẰNG PHẢN CHỨNG pr Ta cĩ tương đương logic  pq  pq qs p1 p 2 pnn q p 1  p 2 p q 0 qs r • Để chứng minh vế trái là một hằng đúng ta chứng rs s minh nếu thêm phủ định của q vào các tiền đề thì được một mâu thuẫn. 0 74 Qui Tắc Suy Diễn VÍ DỤ • CHỨNG MINH THEO TRƢỜNG HỢP • Chứng minh rằng: Dựa trên hằng đúng: 3 p r  q r p  q r nn 43  • Ý nghĩa: nếu p suy ra r và q suy ra r thì p hay q cũng cĩ thể suy ra r. 19
20. Một số luật thêm VÍ DỤ TỔNG HỢP p Rule of Addition(Phép thêm) 1. Nếu nghệ sĩ Trương Ba • p:Nghệ sĩ Trương Ba đã trình khơng trình diễn hay số diễn.  pq vé bán ra ít hơn 100 thì đêm diễn sẽ bi hủy bỏ và • q:số vé bán ra ít hơn 100. ơng bầu sẽ rất buồn. • r:đêm diễn bị hủy bỏ. 2. Nếu đêm diễn bị hủy bỏ • s: ơng bầu buồn. pq Phép đơn giản nối liền thì tiềnvé phải trả lại cho người xem. • t:trả lại tiền vé cho người xem  p p  q r  s 3. Nhưng tiềnvé đã khơng p trả lại cho người xem. rt q Vậy nghệ sỹ TB đã t trình diễn  pq Luật về phép nối lền  p 77 78 VÍ DỤ Qui Tắc Suy Diễn • Ơng Minh nĩi rằng nếu • p:ơng Minh được tăng • PHẢN VÍ DỤ khơng được tăng lương thì lương. ơng ta sẽ nghỉ việc. Mặt • q: ơng Minh nghỉ việc. Để chứng minh một phép suy luận là sai hay 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. p12 p   pn q 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ễ. khơng là một hằng đúng. Ta chỉ cần chỉ ra một thì trước sau gì cũng sẽ bị phản ví dụ. mất việc và cuối cùng ơng  pq s=0 Minh đã được tăng lương. q r s t=1 • Suy ra nếu ơng Minh khơng p=1 bán xe thì vợ ơng ta đã tr q=0 khơng đi làm trễ r=1 p st  80 20
21. Formal Proof Example Proof Example cont. • Suppose we have the following premises: • Let us adopt the following abbreviations: “It is not sunny and it is cold.” – sunny = “It is sunny”; cold = “It is cold”; “Only if We will swim is it sunny.” swim = “We will swim”; canoe = “We will “If we do not swim, then we will canoe.” canoe”; early = “We will be home early”. “If we canoe, then we will be home early.” • Then, the premises can be written as: • Given these premises, prove the theorem “We will be home early” using inference rules. (1) sunny  cold (2) swim sunny (3) swim canoe (4) canoe early 81 82 Proof Example cont. Qui Tắc Suy Diễn Step Proved by • VD1 1. sunny  cold Premise #1. 2. sunny Simplification of 1. 3. swim sunny Premise #2. 4. swim Modus tollens on 2,3. 5. swim canoe Premise #3. 6. canoe Modus ponens on 4,5. 7. canoe early Premise #4. 8. early Modus ponens on 6,7. 83 84 21
22. Qui Tắc Suy Diễn • VD2 85 86 Qui Tắc Suy Diễn Qui Tắc Suy Diễn • Giải 87 88 22
23. Qui Tắc Suy Diễn à 89 90 Bài tập Bài tập 1) Đề thi ĐHBK2000 3. Cho p, q, r là các biến mệnh đề. Chứng minh các Kiểm tra lại dạng mệnh đề sau là hằng đúng dạng mệnh đề sau là các hằng đúng: [p (q  r)] [(p q) (p r)] a) ((p q)  p) q. 2) Đề thi KHTN 2001 b) ((p q) q ) p . Kiểm tra lại tính đúng đắn của suy luận sau c) ((p  q)  q) p. p d) (p q)  ((p q ) 0). q r e) ((p q)  (q r)) (p r). p  r f) ((p  q) r)  ((p r)  (q r)). ___ g) (p q) ((q r) (p r)).   q 91 92 23
24. Bài tập Bài tập 4. Cho p, q, r là các biến mệnh đề. Chứng 5. Hãy kiểm tra các suy luận sau: minh: • a) a) ((p r)  (q r)) (p r) p (q  r) pq b) ((p q r) q ) (p  r) pq  r. q c) ((p r)(q r)) (p q) p q  r r d) (p q)  (p r) p (q  r). pr 93 94 Bài tập Bài tập • b) c) p pq p (q r) pq pq p  (r q) qp qr r  (s t) p rs (q r) s s  r sq tr  t  s  st 95 96 24