Contrapositive Proofs in Discrete Mathematics
Explore contrapositive proofs in discrete mathematics through examples and explanations of proof techniques such as proof by contraposition and truth tables for implications. Discover how and when to use contrapositive proofs effectively in logic and mathematical reasoning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Proof by contraposition Proof by cases Section 3.5 in Jenkyns, Stephenson
Proof by contraposition To prove a statement of the form ( x P x )( ( ) ( )) Q x You can equivalently prove its contra-positive form )( ( x Q x ( ) ( )) P x Remember: (p q) ( q p)
Truth table for implication p T T F F q T F T F p q T F T T Rule this row out!
Contrapositive proof of pq Procedure: 1. Derive contrpositive form: ( q p) 2. Assume q is false (take it as given ) 3. Show that p logically follows
Example Thm.: Let x,y be numbers such that x 0. Then either x+y 0 or x-y 0. Proof: Given (contrapositive form): Let WTS (contrapositive form): ??? Conclusion:
Example Thm.: Let x,y be numbers such that x 0. Then either x+y 0 or x-y 0. Proof: Given (contrapositive form): Let A. x+y 0 or x-y 0 B. x+y=0 or x-y=0 C. x+y=0 and x-y=0 D. y 0 E. None/more/other
Example Thm.: Let x,y be numbers such that x 0. Then either x+y 0 or x-y 0. Proof: Given (contrapositive form): Let x+y=0 and x-y=0 WTS (contrapositive form): A. x 0 B. x=0 C. x+y 0 or x-y 0 D. x+y=0 or x-y=0 E. None/more/other
Example Thm.: Let x,y be numbers such that x 0. Then either x+y 0 or x-y 0. Proof: Given (contrapositive form): Let x+y=0 and x-y=0 WTS (contrapositive form): x=0 Try it yourself first Conclusion:
When should you use contra-positive proofs? You want to prove ( x P x )( ( ) ( )) Q x ( x Q x )( ( ) ( )) P x Which is equivalent to So, it shouldn t matter which one to prove In practice, one form is usually easier to prove - depending which assumption gives more information (either P(x) or Q(x))
11 Breaking a proof into cases Sometimes it is useful to break a proof into a few cases, and then prove each one individually We will see an example demonstrating this principle
12 Breaking a proof into cases 6 people at a party Any two people either know each other, or not (it is symmetric: if A knows B then B knows A) Theorem: among any 6 people, either there are 3 who all know each other (3 friends), or there are 3 who all don t know each other (3 strangers)
Breaking a proof into cases Theorem: Every 6 people includes 3 friends or 3 strangers Proof: The proof is by case analysis. Let x denote one of the 6 people. There are two cases: Case 1: x knows at least 3 of the other 5 people Case 2: x knows at most 2 of the other 5 people Notice it says there are two cases You d better be right there are no more cases! Cases must completely cover possibilities Tip: you don t need to worry about trying to make the cases equal size or scope Sometimes 99% of the possibilities are in one case, and 1% are in the other Whatever makes it easier to do each proof
Breaking a proof into cases Theorem: Every 6 people includes 3 friends or 3 strangers Case 1: suppose x knows at least 3 other people. Case 1.1: No pair among these 3 people know each other. Case 1.2: Some pair among these people know each other. Notice it says: This case splits into two subcases Again, you d better be right there are no more than these two! Subcases must completely cover the possibilities within the case
Breaking a proof into cases Theorem: Every 6 people includes 3 friends or 3 strangers Case 1: suppose x knows at least 3 other people Case 1.1: No pair among these people know each other. Case 1.2: Some pair among these people know each other. Proof for case 1.1: Let y,z,w be 3 friends of x. By assumption, none of them knows each other. So {y,z,w} is a set of 3 strangers.
Breaking a proof into cases Theorem: Every 6 people includes 3 friends or 3 strangers Case 1: suppose x knows at least 3 other people Case 1.1: No pair among these people know each other. Case 1.2: Some pair among these people know each other. Proof for case 1.2: Let y,z be 2 friends of x who know each other. So {x,y,z} is a set of 3 friends.
Breaking a proof into cases Theorem: Every 6 people includes 3 friends or 3 strangers Case 2: suppose x knows at most 2 of the other 5 people So, there are at least 3 people x doesn t know Cases 2.1: All pairs among these people know each other. Case 2.2:Some pair among these people don t know each other. Then this pair, together with x, form a group of 3 strangers. So the theorem holds in this subcase.
18 Breaking a proof into cases Theorem: Proof: There are two cases to consider Case 1: there are two cases to consider Case 1.1: Verify theorem directly Case 1.2: Verify theorem directly Case 2: there are two cases to consider Case 2.1: Verify theorem directly Case 2.2: Verify theorem directly
Next class Indirect proof techniques Read section 3.5 in Jenkyns, Stephenson
