Question

Express the negations of each of these statements so that all negation symbols immediately precede predicates. a) ∀x∃y∀zT(x, y, z) b) ∀x∃yP(x, y) ∨ ∀x∃yQ(x, y) c) ∀x∃y(P(x, y) ∧ ∃zR(x, y, z)) d) ∀x∃y(P(x, y) → Q(x, y))

Answer 1

a) ∀x∃y ¬∀zT(x, y, z)

∀x∃y ∃z ¬T(x, y, z)

b) ∀x¬[∃y (P(x, y) ∨ Q(x, y))]

∀x∀y ¬ [P(x, y) ∨ Q(x, y)]

∀x∀y [¬P(x, y) ^ ¬Q(x, y)]

c) ∀x ¬∃y (P(x, y) ^ ∃zR(x, y, z))

∀x ∀y ¬(P(x, y) ^ ∃zR(x, y, z))

∀x ∀y (¬P(x, y) v ¬∃zR(x, y, z))

∀x ∀y (¬P(x, y) v ∀z¬R(x, y, z))

d) ∀x¬∃y (P(x, y) → Q(x, y))

∀x∀y ¬(P(x, y) → Q(x, y))

∀x∀y (¬P(x, y) ^ Q(x, y))

Answer 2

a) ∃x∀y∃z~T(x, y, z)

b) ∃x∀y~P(x, y) ∧ ∃x∀y~Q(x, y)

c) ∃x∀y(~P(x, y) ∨ ∀z~R(x, y, z))

d) ∃x∀y(P(x, y) → ~Q(x, y))

Explanation:

The negation of a is written as ~a.

Note the following properties that are going to be applied in the problems here :

~(P → Q) = P → ~Q

De Morgan's Laws

~(P ∨ Q) = ~P ∧ ~Q

~(P ∧ Q) = ~P ∨ ~Q

~∃xP = ∀xP

~∀xP = ∃xP

So back to the original problem.

a) ∀x∃y∀zT(x, y, z)

We have the negation as

~[∀x∃y∀zT(x, y, z)]

= ∃x~∃y∀zT(x, y, z)

= ∃x∀y∀~zT(x, y, z)

= ∃x∀y∃z~T(x, y, z)

b) ∀x∃yP(x, y) ∨ ∀x∃yQ(x, y)

Negation is:

~[∀x∃yP(x, y) ∨ ∀x∃yQ(x, y)]

= ~∀x∃yP(x, y) ∧ ~∀x∃yQ(x, y)

= ∃x~∃yP(x, y) ∧ ∃x~∃yQ(x, y)

= ∃x∀y~P(x, y) ∧ ∃x∀y~Q(x, y)

c) ∀x∃y(P(x, y) ∧ ∃zR(x, y, z))

Negation is:

~[∀x∃y(P(x, y) ∧ ∃zR(x, y, z))]

= ~∀x∃y(P(x, y) ∧ ∃zR(x, y, z))

= ∃x~∃y(P(x, y) ∧ ∃zR(x, y, z))

= ∃x∀y~(P(x, y) ∧ ∃zR(x, y, z))

= ∃x∀y(~P(x, y) ∨ ~∃zR(x, y, z))

= ∃x∀y(~P(x, y) ∨ ∀z~R(x, y, z))

d) ∀x∃y(P(x, y) → Q(x, y))

Negation is:

~[∀x∃y(P(x, y) → Q(x, y))]

= ~∀x∃y(P(x, y) → Q(x, y))

= ∃x~∃y(P(x, y) → Q(x, y))

= ∃x∀y~(P(x, y) → Q(x, y))

= ∃x∀y(P(x, y) → ~Q(x, y))