GATE CS 2013 Q47 — Propositional and First Order Logic

Let us simplify the given logical expression using De Morgan's laws for quantifiers:

Let $P = \exists y (\neg \alpha)$ and $Q = \exists z (\neg \beta)$. The simplified expression is equivalent to:

Now, let us evaluate each option inside the universal quantifier $\forall x$:

• Option A: $\exists z (\neg \beta) \to \forall y (\alpha) \equiv Q \to \neg P \equiv \neg Q \lor \neg P$. (Not equivalent to $P \lor Q$)
• Option B: $\forall z (\beta) \to \exists y (\neg \alpha) \equiv \neg Q \to P \equiv Q \lor P \equiv P \lor Q$. (Equivalent)
• Option C: $\forall y (\alpha) \to \exists z (\neg \beta) \equiv \neg P \to Q \equiv P \lor Q$. (Equivalent)
• Option D: $\exists y (\neg \alpha) \to \exists z (\neg \beta) \equiv P \to Q \equiv \neg P \lor Q$. (Not equivalent to $P \lor Q$)

Since both A and D are NOT logically equivalent to the given expression, this question has multiple correct options and was marked as Marks to All (MTA).