Consider the following well-formed formulae: I. ~forall x (P(x)) II. ~exists x (P(x)) III. ~exists x (~P(x)) IV. ~forall 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

GATE 2009 · Discrete Mathematics · First Order Logic · medium

Answer: I and IV — option B. Both are existential statements obtained by negating a universal quantifier: I = exists x ~P(x) and IV = exists x P(x).

1. Reduce all four formulae using quantifier negation: I: ~forall x P(x) = exists x ~P(x). II: ~exists x P(x) = forall x ~P(x). III: ~exists x ~P(x) = forall x ~~P(x) = forall x P(x). IV: ~forall x ~P(x) = exists x ~~P(x) = exists x P(x). Summary: I = exists x ~P, II = forall x ~P, III = forall x P, IV = exists x P.
2. Identify the equivalent pair: I and IV are both existential statements that arise from negating a universal quantifier (~forall). I = exists x ~P(x) and IV = exists x P(x). They are the existential pair. II and III are both universal. The GATE answer is B: I and IV are the equivalent pair — both negate universal quantifiers and reduce to existential forms.