Question

Write the negation of each of the following logical expressions so that all negations immediately precede predicates. In some cases, it may be necessary to apply one or more laws of propositional logic.

a. ∃x ∀y(P(x,y) → Q(x,y))
b. ∃x ∀y(P(x,y) → P(y,x))
c. ∃x ∃y P(x,y) ∧ ∀x ∀y Q(x,y)

Answer 1

a. Negation of ∃x ∀y(P(x,y) → Q(x,y)) = ∀x ∃y P(x,y) ∧ ¬Q(x,y) ]

b. Negation of ∃x ∀y(P(x,y) → P(y,x)) = ∀x ∃y [ ¬P(x,y) ∨ ¬P(y,x) ] ∧ [P(x,y) ∨ P(y,x)]

c. Negation of ∃x ∃y P(x,y) ∧ ∀x ∀y Q(x,y) = ∀x ∀y ¬ [P(x,y)] ∨ ∃x ∃y ¬ [Q(x,y)]

Explanation:

a.∃x ∀y(P(x,y) → Q(x,y))

Negation = ¬ [ ∃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) ]

Negation of ∃x ∀y(P(x,y) → Q(x,y)) = ∀x ∃y P(x,y) ∧ ¬Q(x,y) ]

b. ∃x ∀y(P(x,y) → P(y,x))

Negation = ¬ [ ∃x ∀y(P(x,y) → P(y,x)) ]

= ∀x ¬ [ ∀y(P(x,y) → P(y,x)) ]

= ∀x ∃y ¬ [ (P(x,y) → P(y,x)) ]

= ∀x ∃y ¬ [ ( P(x,y) ∧ P(y,x) ) ∨ ( ¬P(x,y) ∧ ¬P(y,x) )]

= ∀x ∃y ¬ [ P(x,y) ∧ P(y,x) ] ∧ ¬[ ¬P(x,y) ∧ ¬P(y,x) ]

= ∀x ∃y [ ¬P(x,y) ∨ ¬P(y,x) ] ∧ [ P(x,y) ∨ P(y,x) ]

∴ we get

Negation of ∃x ∀y(P(x,y) → P(y,x)) = ∀x ∃y [ ¬P(x,y) ∨ ¬P(y,x) ] ∧ [P(x,y) ∨ P(y,x)]

c. ∃x ∃y P(x,y) ∧ ∀x ∀y Q(x,y)

Negation = ¬ [ ∃x ∃y P(x,y) ∧ ∀x ∀y Q(x,y) ]

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

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

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

∴ we get

Negation of ∃x ∃y P(x,y) ∧ ∀x ∀y Q(x,y) = ∀x ∀y ¬ [ P(x,y) ] ∨ ∃x ∃y ¬ [ Q(x,y) ]