The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
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))] \}$
asked in Mathematical Logic by Boss (13.8k points)
edited by | 104 views
0
is option A ?

1 Answer

+3 votes
Best answer

Consider LHS of option A:

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

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.

answered by Active (1.1k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,080 questions
51,333 answers
177,708 comments
66,675 users