GATE CSE 2020 Q49: Which quantifier equivalence with a closed formula W is not valid

Which one of the following predicate formulae is NOT logically valid?

Note that $W$ is a predicate formula without any free occurrence of $x$ .

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: C (official GATE 2020 final answer key)

Concept used: Moving a quantifier out of the antecedent of an implication flips it: $\forall x (p(x) \to W) \equiv \exists x\, p(x) \to W$ .

First step: Rewrite $p(x) \to W$ as $\lnot p(x) \lor W$ and push the quantifier through the negation.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key