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.


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.


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

Previous Next