104 views

Which of the following first order logic statements is VALID?

1. $\neg\forall x \{ P(x) \vee ∃y [Q(y) \wedge P(y)] \} ≡ ∃x \{ \neg P(x) \wedge \forall y [(P(y) → \neg Q(y)) \vee (Q(y) → \neg P(y))] \}$
2. $\neg\forall x \{ P(x) \vee ∃y [Q(y) \wedge P(y)] \} ≡ ∃x \{ \neg P(x) \wedge \forall y [\neg(P(y) → \neg Q(y)) \vee (\neg Q(y) → \neg P(y))] \}$
3. $\neg\forall x \{ P(x) \vee ∃y [Q(y) \wedge P(y)] \} ≡ ∃x \{ \neg P(x) \wedge \forall y [(P(y) → \neg Q(y)) \vee (\neg Q(y) → \neg P(y))] \}$
4. $\neg\forall x \{ P(x) \vee ∃y [Q(y) \wedge P(y)] \} ≡ ∃x \{ \neg P(x) \wedge \forall y [\neg(P(y) → \neg Q(y)) \vee (Q(y) → \neg P(y))] \}$
edited | 104 views
0
is option A ?

### Consider RHS of option A:

∃x[ ¬P(x) ∧ ∀y[ (P(y) → ¬Q(y)) ∨ (Q(y) → ¬P(y)) ] ]

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

= ∃x[ ¬P(x) ∧ ∀y[ (¬Q(y) ∨ ¬P(y)) ∨ (¬Q(y) ∨ ¬P(y)) ] ]    (∵ A ∨ B = B ∨ A)

= ∃x[ ¬P(x) ∧ ∀y[ ¬Q(y) ∨ ¬P(y) ] ]     (∵A ∨ A = A )

= ∃x[ ¬P(x) ∧ ¬[ ∃y[ Q(y) ∧ P(y) ] ] ]           $[\neg(\forall xP(x))\equiv\neg \forall x\neg P(x)\equiv\exists x\neg P(x)]$

= ∃x[ ¬[ P(x) ∨ ∃y[ Q(y) ∧ P(y) ] ] ]                $[\neg(\exists xP(x))\equiv\neg \exists x\neg P(x)\equiv\forall x\neg P(x)]$

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

= LHS

So option (A) is the answer.

edited

1