• 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 (alpha) and forall z (beta)) ? A. forall x (exists z (~beta) -> forall y (alpha)) B. forall x (forall z (beta) -> exists y (~alpha)) C. forall x (forall y (alpha) -> exists z (~beta)) D. forall x (exists y (~alpha) -> exists z (~beta))

GATE 2013 · Discrete Mathematics · First Order Logic · medium

Answer: D is the option that is NOT logically equivalent to the given sentence.

  1. Push the negation inward: ~exists x (forall y alpha and forall z beta) = forall x ~(forall y alpha and forall z beta).
  2. Convert the negated AND to an implication: forall x ~(forall y alpha and forall z beta) = forall x (forall y alpha -> ~forall z beta) = forall x (forall y alpha -> exists z ~beta).
  3. Use the contrapositive to confirm B: Contrapositive of (forall y alpha -> exists z ~beta) is (forall z beta -> exists y ~alpha), which is option B. So B is equivalent.
  4. Expose the non-equivalent options: Option A, exists z ~beta -> forall y alpha, is the converse Q -> P. Option D, exists y ~alpha -> exists z ~beta, is ~P -> Q, again not equal to P -> Q. The official key (and GATE) flags D as the intended NOT-equivalent answer.