Universal instantiation
Used to conclude that P(c) is true, where c is a particular member of the domain, given the premise ∀xP(x).
Universal instantiation is used when we conclude from the statement “All women are wise” that “Lisa is wise,” where Lisa is a member of the domain of all women.
Universal generalization
States that ∀xP(x) is true, given the premise that P(c) is true for all elements c in the domain.
Universal generalization is used when we show that ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true.
Existential instantiation
The rule that allows us to conclude that there is an element c in the domain for which P(c) is true if we know that ∃xP(x) is true.
Existential generalization
The rule of inference that is used to conclude that ∃xP(x) is true when a particular element c with P(c) true is known.
That is, if we know one element c in the domain for which P(c) is true, then we know that ∃xP(x) is true.
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.”
Let D(x) denote “x is in this discrete mathematics class,” and let C(x) denote “x has taken a course in computer science.” Then the premises are ∀x(D(x) → C(x)) and D(Marla). The conclusion is C(Marla).
The following steps can be used to establish the conclusion from the premises.
| Step | Reason |
|---|---|
| ∀x(D(x) → C(x)) | Premise |
| D(Marla) → C(Marla) | Universal instantiation from (1) |
| D(Marla) | Premise |
| C(Marla) | Modus ponens from (2) and (3) |
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.”
Let C(x) be “x is in this class,” B(x) be “x has read the book,” and P(x) be “x passed the first exam.” The premises are ∃x(C(x) ∧ ¬B(x)) and ∀x(C(x) → P(x)). The conclusion is ∃x(P(x) ∧ ¬B(x)). These steps can be used to establish the conclusion from the premises.
| Step | Reason |
|---|---|
| ∃x(C(x) ∧ ¬B(x)) | Premise |
| C(a) ∧¬B(a) | Existential instantiation from (1) |
| C(a) | Simplification from (2) |
| ∀x(C(x) → P(x)) | Premise |
| C(a) → P(a) | Universal instantiation from (4) |
| P(a) | Modus ponens from (3) and (5) |
| ¬B(a) | Simplification from (2) |
| P(a)∧ ¬B(a) | Conjunction from (6) and (7) |
| ∃x(P(x) ∧ ¬B(x)) | Existential generalization from (8) |
Universal Modus Ponens
This rule tells us that if ∀x(P(x) → Q(x)) is true, and if P(a) is true for a particular element a in the domain of the universal quantifier, then Q(a) must also be true.
∀x(P(x) → Q(x)) P(a), where a is a particular element in the domain --------- ∴ Q(a)
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.
Let P(n) denote “n > 4” and Q(n) denote “n2 < 22. The statement “For all positive integers n, if n is greater than 4, then n2 is less than 22” can be represented by ∀n(P (n) → Q(n)), where the domain consists of all positive integers.
We are assuming that ∀n(P (n) → Q(n)) is true. Note that P(100) is true because 100 > 4. It follows by universal modus ponens that Q(100) is true, namely that 1002 < 2100.
Direct Proofs
A direct proof shows that a conditional statement p → q is true by showing that if p is true, then q must also be true, so that the combination p true and q false never occurs.
Give a direct proof of the theorem “If n is an odd integer, then n 2 is odd.”
we assume that the hypothesis of this conditional statement is true, namely, we assume that n is odd.
By the definition of an odd integer, it follows that n = 2k + 1, where k is some integer. We want to show that n 2 is also odd.
We can square both sides of the equation n = 2k + 1 to obtain a new equation that expresses n2 which we get as 2(2k2+ 2k) + 1. It is one more than twice an integer hence n2 is odd.
Hence, we have proved that if n is an odd integer, then n2 is an odd integer.
Proof by Contraposition
Proofs by contraposition make use of the fact that the conditional statement p → q is equivalent to its contrapositive, ¬q → ¬p.
This means that the conditional statement p → q can be proved by showing that its contrapositive, ¬q → ¬p, is true.
In a proof by contraposition of p → q, we take ¬q as a premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that ¬p must follow.
Q. Prove that if n is an integer and 3n + 2 is odd, then n is odd.
The first step in a proof by contraposition is to assume that the conclusion of the conditional statement “If 3n + 2 is odd, then n is odd” is false; namely, assume that n is even.
Then, by the definition of an even integer, n = 2k for some integer k. Substituting 2k for n, we find that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). This tells us that 3n + 2 is even (because it is a multiple of 2), and therefore not odd.
This is the negation of the premise of the theorem. Because the negation of the conclusion of the conditional statement implies that the hypothesis is false, the original conditional statement is true. Our proof by contraposition succeeded; we have proved the theorem “If 3n + 2 is odd, then n is odd.”
VACUOUS AND TRIVIAL PROOFS
A conditional statement p → q is true when we know that p is false, because p → q must be true when p is false.
Consequently, if we can show that p is false, then we have a proof, called a vacuous proof,of the conditional statement p → q.
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
Note that P(0) is “If 0 > 1, then 02 > 0.” We can show P(0) using a vacuous proof. Indeed, the hypothesis 0 > 1 is false. This tells us that P(0) is automatically true.
The fact that the conclusion of this conditional statement, 02 > 0, is false is irrelevant to the truth value of the conditional statement, because a conditional statement with a false hypothesis is guaranteed to be true.
Trivial proof.
A conditional statement p → q if we know that the conclusion q is true. By showing that q is true, it follows that p → q must also be true.
A proof of p → q that uses the fact that q is true is called a 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
The proposition P(0) is “If a ≥ b, then a0 ≥ b0.” Because a0 = b0 = 1, the conclusion of the conditional statement “If a ≥ b, then a0 ≥ b0 ” is true
Hence, this conditional statement, which is P(0), is true. This is an example of a trivial proof.
Note that the hypothesis, which is the statement “a ≥ b,” was not needed in this proof.
Proofs by Contradiction
Suppose we want to prove that a statement p is true. Furthermore, suppose that we can find a contradiction q such that ¬p → q is true.
Because q is false, but ¬p → q is true, we can conclude that ¬p is false, which means that p is true.
Because the statement r ∧ ¬r is a contradiction whenever r is a proposition, we can prove that p is true if we can show that ¬p → (r ∧ ¬r) is true for some proposition r.
A proof by contradiction does not prove a result directly, it is another type of indirect proof.
Q. Show that at least four of any 22 days must fall on the same day of the week.
Let p be the proposition “At least four of 22 chosen days fall on the same day of the week.” Suppose that ¬p is true. This means that at most three of the 22 days fall on the same day of the week.
Because there are seven days of the week, this implies that at most 21 days could have been chosen, as for each of the days of the week, at most three of the chosen days could fall on that day.
This contradicts the premise that we have 22 days under consideration. That is, if r is the statement that 22 days are chosen, then we have shown that ¬p → (r ∧ ¬r). Consequently, we know that p is true.
We have proved that at least four of 22 chosen days fall on the same day of the week.
PROOFS OF EQUIVALENCE
To prove a theorem that is a biconditional statement, that is, a statement of the form p ↔ q, we show that p → q and q → p are both true.
The validity of this approach is based on the tautology
(p ↔ q) ↔ (p → q) ∧ (q → p).
Q. Prove the theorem “If n is an integer, then n is odd if and only if n2 is odd.”
This theorem has the form “p if and only if q,” where p is “n is odd” and q is “n2 is odd.” To prove this theorem, we need to show that p → q and q → p are true.
We have already that p → q is true and that q → p is true.
Because we have shown that both p → q and q → p are true, we have shown that the theorem is true.