Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x.
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2020 · Q39
Time
Select one answerSingle correct
Solution
Official answer: C) ∀ x(p(x) → W) ∀ x p(x) → W
Propositional and First-Order LogicWe can evaluate the logical validity of each equivalence using standard quantifier transformation rules, since does not occur free in :
Option A: . Since does not depend on , the universal quantifier distributes over disjunction with a constant formula. This is logically valid.
Option B: . Similarly, existential quantification distributes over conjunction with a constant formula. This is logically valid.
Option C: Using the equivalence $A \rightarrow B \equiv
eg A \lor B\forall x\ p(x) \rightarrow W$, which is generally not equivalent. Therefore, C is NOT logically valid.
Option D: $$\exists x(p(x) \rightarrow W) \equiv \exists x(
eg p(x) \lor W) \equiv \exists x( eg p(x)) \lor W \equiv eg(\forall x\ p(x)) \lor W \equiv \forall x\ p(x) \rightarrow W$$ This is logically valid.
Thus, C is the correct answer.
Try the question first, then check your work.
Examiner trap
Rewrite implications as disjunctions using and apply De Morgan's laws for quantifiers.
This Propositional and First-Order Logic previous year question is Q39 of the GATE CSE 2020 paper. Find more GATE CSE PYQs on Propositional and First-Order Logic in Engineering Mathematics, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Propositional and First-Order Logic PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Propositional and First-Order Logic has 18 GATE CSE PYQs across 16 papers from 2011 to 2026. 7 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2020.
How GATE tests Propositional and First-Order LogicIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.