Discrete Mathematics for Computer Science

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 <OVX3 #2)

(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.76 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