**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 ﬁrst exam” imply the conclusion “Someone who passed the ﬁrst 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 ﬁrst 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) | Simpliﬁcation 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) | Simpliﬁcation 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 quantiﬁer, 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 n ^{2} is less than 2^{n}” is true. Use universal modus ponens to show that 100^{2} < 2^{100}.**

Let P(n) denote “n > 4” and Q(n) denote “n

^{2}< 2^{2}. The statement “For all positive integers n, if n is greater than 4, then n^{2}is less than 2^{2}” 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 100^{2}< 2^{100}.

**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 deﬁnition 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 n

^{2}which we get as**2(2k**. It is one more than twice an integer hence n^{2}+ 2k) + 1^{2}is odd.Hence, we have proved that if n is an odd integer, then n

^{2}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, deﬁnitions, 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 ﬁrst 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 deﬁnition of an even integer,

**n = 2k**for some integer k. Substituting 2k for n, we ﬁnd 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 n^{2} > n” and the domain
consists of all integers

Note that P(0) is “If 0 > 1, then 0

^{2}> 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, 0

^{2}> 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 a^{n} ≥ b^{n},” where the domain
consists of all non-negative integers. Show that P(0) is true

The proposition P(0) is “If a ≥ b, then a

^{0}≥ b^{0}.” Because a^{0}= b^{0}= 1, the conclusion of the conditional statement “If a ≥ b, then a^{0}≥ b^{0}” is trueHence, 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 ﬁnd 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 n ^{2} is odd.”**

This theorem has the form “p if and only if q,” where p is “n is odd” and q is “n

^{2}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.

Previous | Next |