Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 8 page Class Notes was uploaded by Chaya Botsford II on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 13 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
19CONTRADICTION AND CONTRAPOSITIVE We address once again the question of how to prove a mathematical statement of the form quotif A then B We have used so far the template for a direct proof unravel A unravel B produce the link from A to B So in a direct proof no negation is involved We will introduce now two more ways to prove quotif A then B called Contrapositive and Contradiction They are actually two versions of a similar approach and we will underscore their differences at the end of this discussion ADVICE Since we will need to negate sentences it is important to review sections 6 and 11 before proceeding J Viola Prioli It is a simple veri cation and a good way to review Truth Tables that x gt y and y gt x have the same truth tables and so they are equivalent Boolean expressions Therefore to prove quotif A then B we can equivalently prove quotif NOT B then NOT A Thus the scheme or quottemplatequot to prove a statement quotif A then B by contrapositive boils down to Unravel NOT B Unravel NOTA Produce the link from NOT B to NOT A Proofs by contrapositive and by contradiction are particular useful when trying to show that some set is empty As a simple illustration we have J Viola Prioli Prove that if A H C Q B then C B A Q Proof Let us state and prove the contrapositive that is if C B H A a Q then A n C is not contained in B Unravel the hypothesis C B n A Q means there is an element x in C B H A Therefore x E C x EB and x E A Unravel the conclusion A 0 C is not contained in B means we must exhibit an element ofA n C that is not an element of B Link From we have that x E C and x E A so x E A n C At the same time by x E B Hence this element x satis es our requirement in The proof is complete A proof by Contradiction is the other indirect technique to be considered Recall that in trying to proof quotif A then B we can never assume the conclusion B to be true However the truth table of A gt B shows that the only possibility for the end result to be false is that A be true and B be false J Viola Prioli The template to prove by contradiction quotif A then B is as follows Assume A to be true B to be false and try to arrive to something impossible that is to a contradiction NOTE a A contradiction might be a violation of a principle a violation ofA which was assumed to be true a violation of a result previously shown etc b Once we arrive to a contradiction we have shown that the negation of quotif A then B is false and so the statement quotif A then B is true Usually a proof by contradiction begins with the sentence lssume for sake of a contradiction that ILLUSTRATIONS J Viola Prioli 1 Prove that no integer is simultaneously even and odd Proof This is rephrased as ifx E Z then x can not be both even and odd Notice that this is A B where A XEZ B x can not be both even and odd Assume for sake of a contradiction that A is true and B is false Hence x is an integer that can be written simultaneously as x 2k some integer k and x 2w 1 some integer w Therefore 2k 2w 1 and so 2k w 1 which gives that k w is 12 This is a contradiction since k w is an integer and 12 is not Having arrived to a contradiction we have proved that the original statement is true J Viola Prioli 2 Prove by contradiction that if 4 divides a2 b2 then a and b are even Proof This is A B where A 4 divides a2 b2 B a is even and b is even Assume for sake of a contradiction that A is true and B is false A true means that a2 b2 4k for some integer k We negate B so a is odd Kb is odd Let us consider for instance that a is odd Then a2 is odd Since a2 b2 4 k we have b2 a2 b2 a2 4k a2 so b must be odd also because quoteven odd is odd Thus b must be odd Therefore we have a 2t1 and b 2w1 with t and w integers 50 4k a2 b2 2t12 2w12 4t2 4t 1 4w2 4w 1 4t2 t w2 w 2 4y2ifwesetyt2tw2w J Viola Prioli Therefore 4k 4y 2 with y an integer and so 2k 2y1 This equality shows that we have arrived to an integer that is simultaneously even and odd This is a contradiction 3 Prove that if a b and a b are prime then a 2 or b 2 Proof Assume for sake of a contradiction that the hypothesis holds but the conclusion is false Thus neither a nor b equals 2 Being prime numbers according to the hypothesis and different from 2 they must be odd and greater than or equal to 3 Thus a b 2 6 Since a and b are odd a b is even But by hypothesis a b is prime so we arrive to the following a b is prime a b 2 6 and a b is even This is a contradiction because the only even prime is 2 How do these two methods compare Observe that in a contrapositive we have only one starting point NOT B and must arrive to NOT A That is done through a link Hence not much information but a clear goal J Viola Prioli On the other hand in a proof by contradiction we have more information A and NOT B which means an edge over the contrapositive However we must arrive to a contradiction but a priori we ignore which contradiction we will end up with Hence more information but the goal is somehow undefined CAUTION Do not confuse quotprove by contradiction with quot nd a counterexample DISCUSSION PROBLEM Suppose we paint each point of the xyplane by using one of either three given colors Blue Red and Yellow Prove that given any positive real number d there exist two points of the same color exactly d units apart J Viola Prioli