Page 68 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 47

TABLE 2 De Morgan’s Laws for Quantifiers.
Negation Equivalent Statement When Is Negation True? When False?
¬PxP (x) ∀x¬P(x) For every x, P(x) is false. There is an x for which
P(x) is true.
¬HxP (x) ∃x¬P(x) There is an x for which P(x) is true for every x.
P(x) is false.

only if no x exists in the domain for which Q(x) is true. Next, note that no x exists in the domain
for which Q(x) is true if and only if Q(x) is false for every x in the domain. Finally, note that
Q(x) is false for every x in the domain if and only if ¬Q(x) is true for all x in the domain,
which holds if and only if ∀x¬Q(x) is true. Putting these steps together, we see that ¬PxQ(x)
is true if and only if ∀x¬Q(x) is true. We conclude that ¬PxQ(x) and ∀x ¬Q(x) are logically
equivalent.
The rules for negations for quantifiers are called De Morgan’s laws for quantifiers. These
rules are summarized in Table 2.

Remark: When the domain of a predicate P(x) consists of n elements, where n is a positive
integer greater than one, the rules for negating quantified statements are exactly the same as
De Morgan’s laws discussed in Section 1.3. This is why these rules are called De Morgan’s
laws for quantifiers. When the domain has n elements x 1 , x 2 ,...,x n , it follows that ¬HxP (x)
is the same as ¬(P (x 1 ) ∧ P(x 2 ) ∧ ··· ∧ P(x n )), which is equivalent to ¬P(x 1 ) ∨¬P(x 2 ) ∨
· · ·∨¬P(x n ) by De Morgan’s laws, and this is the same as ∃x¬P(x). Similarly, ¬PxP (x)
is the same as ¬(P (x 1 ) ∨ P(x 2 ) ∨ ··· ∨ P(x n )), which by De Morgan’s laws is equivalent to
¬P(x 1 ) ∧¬P(x 2 ) ∧· · ·∧¬P(x n ), and this is the same as ∀x¬P(x).

We illustrate the negation of quantified statements in Examples 20 and 21.

EXAMPLE 20 What are the negations of the statements “There is an honest politician” and “All Americans eat
cheeseburgers”?

Solution: Let H(x) denote “x is honest.” Then the statement “There is an honest politician”
is represented by ∃xH(x), where the domain consists of all politicians. The negation of this
statement is ¬PxH(x), which is equivalent to ∀x¬H(x). This negation can be expressed as
“Every politician is dishonest.” (Note: In English, the statement “All politicians are not honest”
is ambiguous. In common usage, this statement often means “Not all politicians are honest.”
Consequently, we do not use this statement to express this negation.)
Let C(x) denote “x eats cheeseburgers.” Then the statement “All Americans eat cheese-
burgers” is represented by ∀xC(x), where the domain consists of all Americans. The negation
of this statement is ¬HxC(x) , which is equivalent to ∃x¬C(x). This negation can be expressed
in several different ways, including “Some American does not eat cheeseburgers” and “There
is an American who does not eat cheeseburgers.” ▲

2
2
EXAMPLE 21 What are the negations of the statements ∀x(x >x) and ∃x(x = 2)?
2
2
Solution: The negation of ∀x(x >x) is the statement ¬Hx(x >x), which is equivalent to
2
2
2
∃x¬(x >x). This can be rewritten as ∃x(x ≤ x). The negation of ∃x(x = 2) is the statement
2
2
2
¬Px(x = 2), which is equivalent to ∀x¬(x = 2). This can be rewritten as ∀x(x = 2). The
truth values of these statements depend on the domain. ▲
We use De Morgan’s laws for quantifiers in Example 22.