Intro to Discrete Structures Lecture 6 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 6 p 1 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Hints for HW1 Intro to Discrete StructuresLecture 6 p 2 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Hints for HW1 Intro to Discrete StructuresLecture 6 p 3 29 Formal Notation Meaning Let p1 p2 pn and c be compound propositions The notation p1 p2 pn c means p1 p2 pn c T p1 p2 pn are called the premises and c is called the conclusion Intro to Discrete StructuresLecture 6 p 4 29 I Rules of Inference Modus ponens p p q q Modus tollens q p q p Intro to Discrete StructuresLecture 6 p 5 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modus Ponens Modus Tollens Intro to Discrete StructuresLecture 6 p 6 29 II Rules of Inference Hypothetical syllogism p q q r p r Disjuctive syllogism p q p q Intro to Discrete StructuresLecture 6 p 7 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modus Ponens Disjunctive syllogism Intro to Discrete StructuresLecture 6 p 8 29 III Rules of Inference Addition p p q Simplification p q p Intro to Discrete StructuresLecture 6 p 9 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com IV Rules of Inference Conjunction p q p q Resolution p q p r q r Intro to Discrete StructuresLecture 6 p 10 29 Resolution The inference rule resolution p q p r q r is based on the tautology p q p r q r We recover disjunctive syllogism by setting r F p q p q Intro to Discrete StructuresLecture 6 p 11 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Hypothetical Syllogism Resolution Intro to Discrete StructuresLecture 6 p 12 29 Hypothetical Syllogism Resolution Intro to Discrete StructuresLecture 6 p 13 29 Rules of Inference for Quantified Statements Universal instantiation xP x P c Universal generalization P c for an arbitrary c xP x Intro to Discrete StructuresLecture 6 p 14 29 Rules of Inference for Quantified Statements Existential instantiation xP x P c for some element c Existential generalization P c for an some element c xP x Intro to Discrete StructuresLecture 6 p 15 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Universal Modus Ponens Universal Modus Ponens x P x Q x P a where a is a particular element in the domain Q a Intro to Discrete StructuresLecture 6 p 16 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com UMP in Math Assume that the statement For all positive integers n if n is greater than 4 then n2 is less than 2n is true Use UMP to show that 1002 2100 Intro to Discrete StructuresLecture 6 p 17 29 Universal Modus Tollens Universal Modus Tollens x P x Q x Q a where a is a particular element in the domain P a Intro to Discrete StructuresLecture 6 p 18 29 Introduction to Proofs Some Terminology Axiom or Postulate Theorem Proposition Lemma Lemmas or Lemmata Corollary Proof Conjecture Intro to Discrete StructuresLecture 6 p 19 29 Proofs Methods Direct Proof Proof by Contraposition or Indirect Proof Proof by Contradition Proof by Induction Intro to Discrete StructuresLecture 6 p 20 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Direct Proof Definition 1 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 Example 1 Give a direct proof of the theorem If n is odd then n2 is odd Intro to Discrete StructuresLecture 6 p 21 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Direct Proof Definition An integer a is a perfect square if there is an integer b such that a b2 Example 2 Give a direct proof that if m and n are both perfect squares then nm is also a perfect square Intro to Discrete StructuresLecture 6 p 22 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Indirect Proof Example 3 Prove that if n is an integer and 3n 2 is odd then n is odd The direct approach does not work Intro to Discrete StructuresLecture 6 p 23 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Indirect Proof Example 3 Prove that if n is an integer and 3n 2 is odd then n is odd Use contraposition n N odd 3n 2 odd n Intro to Discrete StructuresLecture 6 p 24 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Indirect Proof Example 4 Prove that if n ab where a and b are positive integers then a n and b n Intro to Discrete StructuresLecture 6 p 25 29 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Proof Strategy We have seen two important methods for proving theorems of the form x P x Q x These two methods are the direct proof and the indirect proof methods It takes some practice solving homework problems to learn to recognize quickly the correct approach Try first the direct approach If it does not work then try the indirect approach Intro to Discrete StructuresLecture 6 p 26 29 Direct or Indirect Proof Definition The real number r is rational if there exist integers p and q with q 6 0 such that r p q Example 7 Prove that the sum of two rational numbers is rational Intro to Discrete StructuresLecture 6 p 27 29 Direct or Indirect Proof Example 8 Prove that if n is an integer and n2 is odd then n is odd Intro to Discrete StructuresLecture 6 p 28 29 Proof by Contradition We can prove that p is true if we can show that p r r is true for some proposition r Intro to Discrete StructuresLecture 6 p 29 29
View Full Document
Unlocking...