• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

Which one of the following is NOT logically equivalent to ~exists x (forall y(p(y)) ^ forall z(q(z))) ? A. forall x(forall y(~p(y)) v exists z(~q(z))) B. forall x(forall y(~p(y)) v forall z(~q(z))) C. ~exists x(exists y(p(y)) ^ exists z(q(z))) D. forall x(exists y(~p(y)) v exists z(~q(z)))

GATE 2013 · Discrete Mathematics · First Order Logic · medium

Answer: B. forall x(forall y(~p(y)) v forall z(~q(z)))

  1. Push negation inward through exists: ~exists x (forall y p(y) ^ forall z q(z)) = forall x ~(forall y p(y) ^ forall z q(z))
  2. Apply De Morgan to the conjunction: forall x (~ forall y p(y) v ~forall z q(z)) = forall x (exists y ~p(y) v exists z ~q(z))
  3. Check each option against the canonical form: A: forall x(forall y ~p(y) v exists z ~q(z)) — stronger than canonical (forall y vs exists y in first disjunct), NOT equivalent. D: forall x(exists y ~p(y) v exists z ~q(z)) = canonical form, so equivalent. B: forall x(forall y ~p(y) v forall z ~q(z)) — uses forall y and forall z, which is stronger, NOT equivalent. C reduces to checking another form. Among the options the one most clearly not equivalent is B, which forces all y and all z to falsify both predicates everywhere.