Predicates and Quantification
139
If we go beyond pure logic and use English synonyms, we can further simplify that
last expression to 3x E N (x is prime A (x
2 + 1 is odd)).
(b)
(ýx E•Q (x> 0 A x
3 = 2))
<*, Vx E Q (--(X > 0A X3 = 2))
€,Vx E Q (-• (x > O) v -• (xI = 2))
:VX EQ(X (c)
-'3x(Vy(xy = y))
V 'lx (-3y (xy = y))
SVx(3y(--(xy = y))
ۥVx(3x(xy A y))
(d)
-(Vx (Vy (x < y - (3z (x < z) A (Z < y))))))
.'
3xx(-,(Vyy(x < y -+ (3x((x < Z) A (x < y))))))
.4*
3x3y--(x < y --* (3z((x < Z) A (z < y))))
3• qx3y(--(-'(x < y) V (3Z((x < Z) A (Z < y)))))
.:
3x3y((x < y) A -- (3z((x < Z) A (Z < y))))
,3 2x3y((x < y) A (Vz-((x < z) A (z < y))))
3 2x3y((x < y) A (VZ((X > Z) V (Z > y))))
The last step used DeMorgan's Law.
Again, we note that putting formulas into negation normal form often-although not
always-makes them more comprehensible.
2.7.6 Quantification with Conjunction and Disjunction
Predicates can be joined by the usual logical operations. Note the English translations of
the following formulas:
Formula
English Translation
3x (P(x) A Q(x))
"For some particular choice of x,
both P(x)
and Q(x) are true."
Vx (P(x) A Q(x))
"For every choice of x,
both P(x)
and Q(x) are true."
3x (P (x) v Q (x))
"For some particular choice of x,
P(x) or Q(x)
(or both) is true."
Vx (P(x) V Q(x))
"For every choice of x,
P(x) or Q(x) (or both) is true."
Example 6. For the universal set N, is 3x ((x + 3 = 2) A (x - 2 = 1)) true?
Solution. For any x, if x + 3 = 2, then x must be - 1. If x - 2 = 1, then x = 3. So, no
choice of x makes both true.
U