GATE2009 q26 Revision as of 20:00, 14 July 2014 by Arjun Suresh (talk | contribs) (Created page with "Consider the following well-formed formulae: <br> I. ¬∀x(P(x)) II. ¬∃x(P(x)) III. ¬∃x(¬P(x)) IV. &exist...") (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Consider the following well-formed formulae:
I. ¬∀x(P(x))   II. ¬∃x(P(x))   III. ¬∃x(¬P(x))   IV. ∃x(¬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)). So option (B) is correct.

Tweet