Page 67 - Discrete Mathematics and Its Applications

46 1 / The Foundations: Logic and Proofs

It follows that for all a, P(a) ∧ Q(a) is true. It follows that ∀x(P (x) ∧ Q(x)) is true. We can
now conclude that

∀x(P (x) ∧ Q(x)) ≡∀xP (x) ∧∀xQ(x). ▲

Negating Quantified Expressions

We will often want to consider the negation of a quantified expression. For instance, consider
the negation of the statement

“Every student in your class has taken a course in calculus.”

This statement is a universal quantification, namely,
∀xP (x),

where P(x) is the statement “x has taken a course in calculus” and the domain consists of the
students in your class. The negation of this statement is “It is not the case that every student in
your class has taken a course in calculus.” This is equivalent to “There is a student in your class
who has not taken a course in calculus.” And this is simply the existential quantification of the
negation of the original propositional function, namely,

∃x ¬P(x).

This example illustrates the following logical equivalence:

¬HxP (x) ≡∃x ¬P(x).
To show that ¬HxP (x) and ∃xP (x) are logically equivalent no matter what the propositional
function P(x) is and what the domain is, first note that ¬HxP (x) is true if and only if ∀xP (x) is
false. Next, note that ∀xP (x) is false if and only if there is an element x in the domain for which
P(x) is false. This holds if and only if there is an element x in the domain for which ¬P(x) is
true. Finally, note that there is an element x in the domain for which ¬P(x) is true if and only
if ∃x ¬P(x) is true. Putting these steps together, we can conclude that ¬HxP (x) is true if and
only if ∃x ¬P(x) is true. It follows that ¬HxP (x) and ∃x ¬P(x) are logically equivalent.
Suppose we wish to negate an existential quantification. For instance, consider the propo-
sition “There is a student in this class who has taken a course in calculus.” This is the existential
quantification
∃xQ(x),

where Q(x) is the statement “x has taken a course in calculus.” The negation of this statement
is the proposition “It is not the case that there is a student in this class who has taken a course in
calculus.” This is equivalent to “Every student in this class has not taken calculus,” which is just
the universal quantification of the negation of the original propositional function, or, phrased in
the language of quantifiers,

∀x ¬Q(x).

This example illustrates the equivalence

¬PxQ(x) ≡∀x ¬Q(x).
To show that ¬PxQ(x) and ∀x ¬Q(x) are logically equivalent no matter what Q(x) is and what
the domain is, first note that ¬PxQ(x) is true if and only if ∃xQ(x) is false. This is true if and