Page 98 - Discrete Mathematics and Its Applications

1.6 Rules of Inference 77

EXAMPLE 13 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.”

Solution: 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
1. ∃x(C(x) ∧¬B(x)) Premise
2. C(a) ∧¬B(a) Existential instantiation from (1)
3. C(a) Simplification from (2)
4. ∀x(C(x) → P(x)) Premise
5. C(a) → P(a) Universal instantiation from (4)
6. P(a) Modus ponens from (3) and (5)
7. ¬B(a) Simplification from (2)
8. P(a) ∧¬B(a) Conjunction from (6) and (7)
9. ∃x(P (x) ∧¬B(x)) Existential generalization from (8)
▲

Combining Rules of Inference for Propositions
and Quantified Statements

We have developed rules of inference both for propositions and for quantified statements. Note
that in our arguments in Examples 12 and 13 we used both universal instantiation, a rule of
inferenceforquantifiedstatements,andmodusponens,aruleofinferenceforpropositionallogic.
We will often need to use this combination of rules of inference. Because universal instantiation
and modus ponens are used so often together, this combination of rules is sometimes called
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. To see this, note that by universal instantiation, P(a) → Q(a) is true. Then, by modus
ponens, Q(a) must also be true. We can describe universal modus ponens as follows:

∀x(P (x) → Q(x))
P(a), where a is a particular element in the domain
∴ Q(a)

Universal modus ponens is commonly used in mathematical arguments. This is illustrated
in Example 14.

2
n
EXAMPLE 14 Assume that “For all positive integers n,if n is greater than 4, then n is less than 2 ” is true.
2
Use universal modus ponens to show that 100 < 2 100 .
n
2
Solution: Let P(n) denote “n> 4” and Q(n) denote “n < 2 .” The statement “For all positive
n
2
integers n,if n is greater than 4, then n is less than 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
2
Q(100) is true, namely that 100 < 2 100 . ▲
Another useful combination of a rule of inference from propositional logic and a rule
of inference for quantified statements is universal modus tollens. Universal modus tollens