CORNELL CS 2800 - Discrete Structures

Unformatted text preview:

Discrete Structures CS 2800Methods for Proving TheoremsTheorems, proofs, and Rules of InferenceValid ArgumentsSlide 5Methods of ProofDirect ProofExample - direct proofSlide 9Slide 10Example 2: Direct ProofSlide 12Slide 13Proof by ContrapositionExample 1: Proof by ContrapositionExample 2: Proof by ContrapositionProof by ContradictionExample 1: Proof by ContradictionSlide 19Example2: Proof by ContradictionSlide 21Example 3: Proof by ContradictionExample 4: Proof by ContradictionProof of EquivalencesCounterexamplesCounterexampleProof by CasesSlide 28Existence ProofsExample 1 - Existence ProofsExample 2: Existence proofExample 3: Non-constructive proofSlide 33FallaciesThe Fallacy of Affirming the ConsequentThe Fallacy of Denying the AntecedentBegging the question or circular reasoningFinal example TilingAdditional Proof Methods Covered in CS2801Discrete StructuresCS 2800Prof. Bart [email protected] Logic (part 2 --- proof methods)2Methods for Proving Theorems3 Theorems, proofs, and Rules of InferenceWhen is a mathematical argument correct?What techniques can we use o construct a mathematical argument?Theorem – statement that can be shown to be true.Axioms or postulates – statements which are given and assumed to be true.Proof – sequence of statements, a valid argument, to show that a theorem is true.Rules of Inference – rules used in a proof to draw conclusions from assertions known to be true.Note: Lemma is a “pre-theorem” or a result that needs to be proved to prove the theorem; A corollary is a “post-theorem”, a result which follows directly the theorem that has been proved. Conjecture is a statement believed to be true but for which there is not a proof yet. If the conjecture is proved true it becomes a thereom. Fermat’s theorem was a conjecture for a long time.4Valid ArgumentsRecall:An argument is a sequence of propositions. The final proposition is called the conclusion of the argument while the other propositions are called the premises or hypotheses of the argument.An argument is valid whenever the truth of all its premises implies the truth of its conclusion. How to show that q logically follows from the hypotheses (p1  p2  …pn)?Show that (p1  p2  …pn)  q is a tautologyOne can use the rules of inference to show the validity of an argument.Vacuous proof - if one of the premises is false then (p1  p2  …pn)  q is vacuously True, since False implies anything.(reminder)5Note: Many theorems involve statements for universally quantified variables:e.g.“If x>y, where x and y are positive real numbers, then x2 > y2 ”Quite often, when it is clear from the context, theorems are proved without explicitly using the laws of universal instantiation and universal generalization.6Methods of ProofDirect ProofProof by ContrapositionProof by ContradictionProof of EquivalencesProof by CasesExistence ProofsCounterexamples7Direct ProofProof of a statement p  qAssume p From p derive q.8 Example - direct proof Here’s what you know:Theorem:Mary is a Math major or a CS major.If Mary does not like discrete math, she is not a CS major.If Mary likes discrete math, she is smart.Mary is not a math major.Can you conclude Mary is smart?M  CD  CD  SM((M  C)  (D  C)  (D  S)  (M))  S?Let M - Mary is a Math majorC – Mary is a CS majorD – Mary likes discrete math S – Mary is smart Informally, what’s the chain of reasoning?9 Example - direct proof In general, to prove p  q, assume p and show that q follows. ((M  C)  (D   C)  (D  S)  (M))  S?101. M  C Given2. D  C Given3. D  S Given4. M Given DS (1,4)MT (2,5)5. C6. D7. SMP (3,6)Mary is smart! Example - direct proof QEDQED or Q.E.D. --- quod erat demonstrandum“which was to be demonstrated”or “I rest my case” 11Example 2: Direct ProofTheorem:If n is odd integer, then n2 is odd.Definition: The integer 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. An integer is even or odd; and no integer is both even and odd.12Theorem:(n) P(n)  Q(n), where P(n) is “n is an odd integer” and Q(n) is “n2 is odd.”We will show P(n)  Q(n) Example 2: Direct ProofTheorem:If n is odd integer, then n2 is odd.Proof:Let p --- “n is odd integer”; q --- “n2 is odd”; we want to show that p  q•Assume p, i.e., n is odd.•By definition n = 2k + 1, where k is some integer.•Therefore n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2 (2k2 + 2k ) + 1, which is by definition an odd number (k’ = (2k2 + 2k ) ). QEDExample 2: Direct ProofProof strategy hint: Go back to definitions of conceptsand start by trying direct proof.14Proof by ContrapositionProof of a statement p  qUse the equivalence to :¬q  ¬ pFrom ¬q derive ¬ p.15Again, p  q  q  p (the contrapositive)So, we can prove the implication p  q by first assuming q, and showing that p follows.Example: Prove that if a and b are integers, and a + b ≥ 15, then a ≥ 8 or b ≥ 8.(a + b ≥ 15)  (a ≥ 8) v (b ≥ 8) (Assume q) Suppose (a < 8)  (b < 8).(Show p) Then (a ≤ 7)  (b ≤ 7),and (a + b) ≤ 14,and (a + b) < 15.Example 1: Proof by ContrapositionQEDProof strategy:Note that negationof conclusion iseasier to start withhere.Example 2: Proof by ContrapositionTheoremFor n integer , if 3n + 2 is odd, then n is odd. I.e. For n integer, 3n+2 is odd  n is oddProof by Contraposition: Let p --- “3n + 2” is odd; q --- “n is odd”; we want to show that p  q •The contraposition of our theorem is ¬q  ¬p n is even  3n + 2 is even •Now we can use a direct proof•Assume ¬q , i.e, n is even therefore n = 2 k for some k •Therefore 3 n + 2 = 3 (2k) + 2 = 6 k + 2 = 2 (3k + 1) which is even. QEDAgain, negationof conclusion iseasy to start with.Try direct proof. 17Proof by ContradictionA – We want to prove p.We show that:(1) ¬p  F (i.e., a False statement , say r ¬r)(2) We conclude that ¬p is false since (1) is True and therefore p is True.B – We want to show p  q(1) Assume the negation of the conclusion, i.e., ¬q (2) Use show that (p  ¬q )  F(3) Since ((p  ¬q )  F)  (p  q) (why?) we are done18Example:Rainy days make gardens grow.Gardens don’t grow if it is not hot.When it is cold outside, it rains.Prove


View Full Document

CORNELL CS 2800 - Discrete Structures

Download Discrete Structures
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Discrete Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Discrete Structures 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?