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.7.5 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 connectives -, 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))
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.7.5 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 connectives -, 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))