Page 97 - Discrete Mathematics and Its Applications

76 1 / The Foundations: Logic and Proofs
EXAMPLE 12
TABLE 2 Rules of Inference for Quantified Statements.
Rule of Inference Name
∀xP (x)
Universal instantiation
∴ P(c)
P(c) for an arbitrary c
Universal generalization
∴ ∀xP (x)
∃xP (x)
Existential instantiation
∴ P(c) for some element c
P(c) for some element c
Existential generalization
∴ ∃xP (x)
Universal generalization is the rule of inference that 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. The element c that we select must be an arbitrary, and not a specific, element of
the domain. That is, when we assert from ∀xP (x) the existence of an element c in the domain,
we have no control over c and cannot make any other assumptions about c other than it comes
from the domain. Universal generalization is used implicitly in many proofs in mathematics and
is seldom mentioned explicitly. However, the error of adding unwarranted assumptions about
the arbitrary element c when universal generalization is used is all too common in incorrect
reasoning.
Existential instantiation is 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. We cannot select an arbitrary
value of c here, but rather it must be a c for which P(c) is true. Usually we have no knowledge
of what c is, only that it exists. Because it exists, we may give it a name (c) and continue our
argument.
Existential generalization is 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.
We summarize these rules of inference in Table 2. We will illustrate how some of these rules
of inference for quantified statements are used in Examples 12 and 13.
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.”
Solution: 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
1. ∀x(D(x) → C(x)) Premise
2. D(Marla) → C(Marla) Universal instantiation from (1)
3. D(Marla) Premise
4. C(Marla) Modus ponens from (2) and (3) ▲