X


Rules of Inference for Quantified Statements




Universal instantiation



Universal generalization





Existential instantiation



Existential generalization



Show that the premises “Everyone in this discrete mathematics class has taken a course in computer science” and “Marla is a student in this class” imply the conclusion “Marla has taken a course in computer science.”



Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.”



Universal Modus Ponens





Assume that “For all positive integers n, if n is greater than 4, then n2 is less than 2n” is true. Use universal modus ponens to show that 1002 < 2100.




Methods of Proving Theorems




Direct Proofs



Give a direct proof of the theorem “If n is an odd integer, then n 2 is odd.”





Proof by Contraposition



Q. Prove that if n is an integer and 3n + 2 is odd, then n is odd.



VACUOUS AND TRIVIAL PROOFS





Q. Show that the proposition P(0) is true, where P(n) is “If n > 1, then n2 > n” and the domain consists of all integers



Trivial proof.



Q. Let P(n) be “If a and b are positive integers with a ≥ b, then an ≥ bn,” where the domain consists of all non-negative integers. Show that P(0) is true





Proofs by Contradiction



Q. Show that at least four of any 22 days must fall on the same day of the week.



PROOFS OF EQUIVALENCE





Q. Prove the theorem “If n is an integer, then n is odd if and only if n2 is odd.”


Previous Next