CSE115/ENGR160 Discrete Mathematics 02/01/111.6 Direct proofs of p→qExampleSlide 4Slide 5Proof by contrapositionSlide 7Slide 8Vacuous proofTrivial proofSlide 11Direct proofSlide 13Proof by contradictionSlide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Proof of equivalenceExampleEquivalent theoremsSlide 25Slide 26CounterexampleSlide 28Mistakes in proofsWhat is wrong with this proof?Slide 31Circular reasoningProofsCSE115/ENGR160 Discrete Mathematics02/01/11Ming-Hsuan YangUC Merced11.6 Direct proofs of p→q•First assume p is true•Then show q must be true (using axioms, definitions, and previously proven theorems)•So the combination of p is true and q is false never occurs •Thus p→q is true•Straightforward •But sometimes tricky and require some insight2Example•Definition:–The integer n is even if there exists an integer k such that n=2k, and –n is odd if there exists an integer k such that n=2k+1–Note that an integer is either even or odd•Show “If n is an odd integer, then n2 is odd”3Example•Note the theorem states•By definition of odd integer, n=2k+1, where k is some integer•n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1•By definition of odd integer, we conclude n2 is an odd integer •Consequently, we prove that if n is an odd integer, then n2 is odd4))()(( nqnpn Example•“If m and n are both perfect squares, then nm is also a perfect square (an integer a is a perfect square if there is an integer b such that a=b2)•By definition, there are integers s and t such that m=s2, and n=t2•Thus, mn=s2t2=(st)2 (using commutativity and associativity of multiplication)•We conclude mn is also a perfect square5Proof by contraposition•Indirect proof: sometimes direct proof leads to dead ends•Based on •Use ┐q as hypothesis and show ┐p must follow6pqqp Example•Show that “if n is an integer and 3n+2 is odd, then n is odd”•Use•Proof by contraposition: –Assume n is even, i.e., n=2k, for some k–It follows 3n+2=3(2k)+2=6k+2=2(3k+1)–Thus 3n+2 is even 7pqqp Example•Prove that if n=ab, where a and b are positive integers, then8nbna  or nabnnnabnbnanbna )( Assumepqqp Vacuous proof•Prove p→q is true •Vacuous proof: If we show p is false and then claim a proof –However, often used to establish special case•Show that p(0) is true when p(n) is “If n>1, then n2>n” and the domain consists of all integers•The fact 02>0 is false is irrelevant to the truth value of the conditional statement9Trivial proof•Trivial proof: a proof of p→q that uses the fact q is true–Often important when special cases are proved•Let p(n) be “If a and b are positive integers with a≥b, then an ≥bn where the domain consists all integers•The proposition p(0) is “If a≥b, then a0 ≥b0”. a0 ≥b0 is true, hence the conditional statement p(0) is true10Example•Definition: the real number r is rational if there exist integers p and q with q≠0 such that r=p/q•A real number that is not rational is irrational•Prove that the sum of two rational numbers is rational (i.e., “For every real number r and every real number s, if r and s are rational numbers, then r+s is rational”)•Direct proof? Proof by contraposition?11Direct proof•Let r=p/q and s=t/u where p, q, t, u, are integers and q≠0, and u≠0.•r+s=p/q+t/u=(pu+qt)/qu•Since q≠0 and u≠0, qu≠0•Consequently, r+s is the ratio of two integers. Thus r+s is rational12Example•Prove that if n is an integer and n2 is odd, then n is odd•Direct proof? Proof by contraposition?13Proof by contradiction•Suppose we want to prove a statement p•Further assume that we can find a contradiction q such that ┐p→q is true•Since q is false, but ┐p→q is true, we can conclude ┐p is false, which means p is true•The statement ┐r˄r is contradiction, we can prove that p is true if we can show that ┐p→(┐r˄r), i.e., if p is not true, then there is a contradiction 14Example•Show that at least 4 of any 22 days must fall on the same day of the week•Let p be the proposition “at least 4 of any 22 days fall on the same day of the week”•Suppose ┐p is true, which means at most 3 of 22 days fall on the same day of the week•Which implies at most 21 days could have been chosen because for each of the days of the week, at most 3 of the chosen days could fall on that day•If r is the statement that 22 days are chosen. Then, we have 15┐p→(┐r r)˄Example•Prove that is irrational by giving a proof by contradiction•Let p be the proposition “ is irrational”•┐p: is rational, and thus where a and b have no common factors•Thus 2=a2/b2, 2b2=a2, and thus a2 is even•a2 is even and so a is even. Let a=2c for some integer c, 2b2=4c2, and thus b2=2c2, and b2 is even 16222ba /2 Example•Use the fact that if the square of an integer is even, then the integer itself is even, we conclude b must be even•┐p leads to where and b have no common factors, and both a and b are even (and thus a common factor), a contradiction•That is, the statement “ is irrational” is true17ba /2 2Proof by contradiction•Can be used to prove conditional statements•First assume the negation of the conclusion•Then use premises and negation of conclusion to arrive a contradiction•Reason: p→q≡((p ┐q)→F)˄18Proof by contradiction•Can rewrite a proof by contraposition of a conditional statement p→q as proof by contradiction•Proof by contraposition: show if ┐q then ┐p•Proof by contradiction: assume p and ┐q are both true•Then use steps of ┐q→┐p to show ┐p is true•This leads to p ┐p, a contradiction˄19Example•Proof by contradiction “If 3n+2 is odd, then n is odd”•Let p be “3n+2 is odd” and q be “n is odd”•To construct a proof by contradiction, assume both p and ┐q are both true•Since n is even, let n=2k, then 3n+2=6k+2= 2(3k+1). So 3n+2 is even, i.e. ┐p, •Both p and ┐p are true, so we have a contradiction20Example•Note that we can also prove by contradiction that p→q is true by assuming that p and ┐q are both true, and show that q must be also true •This implies q and ┐q are both true, a contradiction•Can turn a direct proof into a proof by contradiction21Proof of equivalence•To prove a theorem that is a biconditional statement p↔q, we show p→q and q →p•The