165k views
7 votes
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)

User Rsbarro
by
8.0k points

1 Answer

7 votes

Answer:

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) ]

User LearningSlowly
by
8.2k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories