GATE2009 q26 Revision as of 20:55, 15 September 2014 by Arjun Suresh (talk | contribs) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Consider the following well-formed formulae:

I. $\neg \forall x(P(x))$

II. $\neg \exists x(P(x))$

III. $\neg \exists x(\neg P(x))$

IV. $\exists x(\neg P(x))$

Which of the above are equivalent?

(A) I and III

(B) I and IV

(C) II and III

(D) II and IV

Solution by Happy Mittal

A formula $∀x(P(x))$ is equivalent to formula $¬∃x(¬P(x))$ i.e. add $¬$ inside and outside, and convert $∀$ to $∃$.

So, $¬∀x(P(x))$ is equivalent to $∃x(¬P(x))$.

Tweet