138 CHAPTER 2 Formal Logic
Generally, if 3x (Vy (P(x, y))) is true, so is Vy (3x (P(x, y))): If the first is true, then
one can pick x0 where Vy (P(xo, y)). In that case, for each individual y, one can pick that
same value x0 to make P(xo, y) true, so Vy (3x (P(x, y))) is true. The converse, however,
is false, as Example 4 in Section 2.7.4 shows.2.75 Negation and Quantification
One has to be careful about how negation interacts with quantification-partly because in
ordinary human conversation, people are not always very precise.The formula -'(3x (P(x)) says that there does not exist even one x in the universal set
that makes P (x) true. This is the same as asserting that every x in the universal set makes
P false. Thus,--(3x (P(x))) is logically equivalent to Vx (-'P(x))
Analogously, --(Vx (P(x))) says that P(x) is not true for all x in the universal set.
That is, there is at least one x for which P(x) is false. Thus,--(Vx (P (x))) is logically equivalent to 3x (--P (x))
One important result of these rules is that we can always "push negation inward" to be
an operator on a predicate rather than on a quantified formula. Often, it becomes easier to
understand a formula after the negations are "pushed inward." As an illustration, consider
the formulas- (Vx (3y (P(x, y)))) is logically equivalent to 3x (-' (3y ((P(x, y)))))
which is logically equivalent to 3x (Vy (- P(x, y)))
-'(3x (Vy (P(x, y)))) is logically equivalent to Vx (- (Vy (P(x, y))))which is logically equivalent to Vx (3y (- P (x, y)))
The resulting formulas with -- applied only to atomic formulas and using only the connec-
tives -, v, and A is said to be in negation normal form.Example 5. Find formulas in negation normal form equivalent to each of the following
formulas. (In cases (c) and (d), the intended universal set is the set of all real numbers, but
that does not affect the answers.)(a) --Vx E N (x is prime - 2 + I is even)
(b) -3x E Q (x > 0 A x^3 2)
(c) -3x (Vy (xy = y))
(d) -Vx (Vy (x < y -). (3z (x < z A Z < y))))Solution. We use 4:' to mean "is logically equivalent to."
(a) -(Vx E N (x is prime -+ x^2 + 1 is even))
3.x E N-N- (x is prime --* x2 + I is even)
S3x e N - (x is not a prime V (x2 + 1 is even))
3X E N (x is prime A -(x^2 + I is even))