CSE115/ENGR160 Discrete Mathematics 01/31/121.7 Introduction to proofsSome terminologyDirect proofs of p→qExampleSlide 6Slide 7Proof by contrapositionSlide 9Slide 10Vacuous proofTrivial proofSlide 13Direct proofSlide 15Proof by contradictionSlide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Proof of equivalenceExampleEquivalent theoremsSlide 27Slide 28CounterexampleSlide 30Mistakes in proofsWhat is wrong with this proof?Slide 33Circular reasoningProofsCSE115/ENGR160 Discrete Mathematics01/31/12Ming-Hsuan YangUC Merced11.7 Introduction to proofs•Proof: valid argument that establishes the truth of a mathematical statement, e.g., theorem•A proof can use hypotheses, axioms, and previously proven theorems•Formal proofs: can be extremely long and difficult to follow•Informal proofs: easier to understand and some of the steps may be skipped, or axioms are not explicitly stated2Some terminology•Theorem: a mathematical statement that can be shown to be true•Proposition: less important theorem•Axiom (postulate): a statement that is assumed to be true•Lemma: less important theorem that is helpful in the proof of other results•Corollary: a theorem that can be established directly from a theorem that has been proved•Conjecture: a statement proposed to be true, but not proven yet3Direct 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 insight4Example•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”5Example•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 odd6))()(( 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 square7Proof by contraposition•Indirect proof: sometimes direct proof leads to dead ends•Based on •Use ┐q as hypothesis and show ┐p must follow8pqqp 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 9pqqp Example•Prove that if n=ab, where a and b are positive integers, then10nbna  or nabnnnabnbnanbna )( Assumepqqp Vacuous proof•Prove p→q is true •Vacuous proof: If we show p is false and then claim a proof of p→q–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 statement11Trivial 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 of all integers•The proposition p(0) is “If a≥b, then a0 ≥b0”. a0 ≥b0 is true, hence the conditional statement p(0) is true12Example•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?13Direct 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 rational14Example•Prove that if n is an integer and n2 is odd, then n is odd•Direct proof? Proof by contraposition?15)2(24 that followsit ,2:ioncontradictby Proof12then ,12Let :proofDirect odd is :qodd is :p22222kknknknknnnProof 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 16Example•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 17┐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 (can easily show if n2 is even, then n is even). Let a=2c for some integer c, 2b2=a2=4c2, and thus b2=2c2, and b2 is even18222ba /2 Example•Since b2 is even, 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 true19ba /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)˄20Proof by contradiction•Can rewrite a proof by contraposition of a conditional statement p→q as proof by