Page 64 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 43

The meaning of the existential quantifier is summarized in the second row of Table 1. We
illustrate the use of the existential quantifier in Examples 14–16.

EXAMPLE 14 Let P(x) denote the statement “x> 3.” What is the truth value of the quantification ∃xP (x),
where the domain consists of all real numbers?

Solution: Because “x> 3” is sometimes true—for instance, when x = 4—the existential quan-
tification of P(x), which is ∃xP (x), is true. ▲

Observe that the statement ∃xP (x) is false if and only if there is no element x in the domain
for which P(x) is true. That is, ∃xP (x) is false if and only if P(x) is false for every element of
the domain. We illustrate this observation in Example 15.

EXAMPLE 15 Let Q(x) denote the statement “x = x + 1.”What is the truth value of the quantification ∃xQ(x),
where the domain consists of all real numbers?

Solution: Because Q(x) is false for every real number x, the existential quantification of Q(x),
which is ∃xQ(x), is false. ▲

Remember that the truth
value of ∃xP (x) depends
on the domain! Remark: Generally, an implicit assumption is made that all domains of discourse for quantifiers
are nonempty. If the domain is empty, then ∃xQ(x) is false whenever Q(x) is a propositional
function because when the domain is empty, there can be no element x in the domain for which
Q(x) is true.

When all elements in the domain can be listed—say, x 1 ,x 2 ,..., x n — the existential quan-
tification ∃xP (x) is the same as the disjunction

P(x 1 ) ∨ P(x 2 ) ∨ ··· ∨ P(x n ),

because this disjunction is true if and only if at least one of P(x 1 ), P (x 2 ),...,P(x n ) is true.

2
EXAMPLE 16 What is the truth value of ∃xP (x), where P(x) is the statement “x > 10” and the universe of
discourse consists of the positive integers not exceeding 4?

Solution: Because the domain is {1, 2, 3, 4}, the proposition ∃xP (x) is the same as the disjunc-
tion

P(1) ∨ P(2) ∨ P(3) ∨ P(4).

2
Because P(4), which is the statement “4 > 10,” is true, it follows that ∃xP(x) is true. ▲

It is sometimes helpful to think in terms of looping and searching when determining the
truth value of a quantification. Suppose that there are n objects in the domain for the variable x.
To determine whether ∀xP(x) is true, we can loop through all n values of x to see whether
P(x) is always true. If we encounter a value x for which P(x) is false, then we have shown that
∀xP(x) is false. Otherwise, ∀xP(x) is true. To see whether ∃xP(x) is true, we loop through
the n values of x searching for a value for which P(x) is true. If we find one, then ∃xP(x) is
true. If we never find such an x, then we have determined that ∃xP(x) is false. (Note that this
searching procedure does not apply if there are infinitely many values in the domain. However,
it is still a useful way of thinking about the truth values of quantifications.)