GateAI
Propositional and First-Order Logic

GATE CSE 2020 · Q39

MCQ2 marksMedium

Time

Which one of the following predicate formulae is NOT logically valid? Note that WW is a predicate formula without any free occurrence of xx.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) ∀ x(p(x) → W) ∀ x p(x) → W

Propositional and First-Order Logic

We can evaluate the logical validity of each equivalence using standard quantifier transformation rules, since xx does not occur free in WW:

  1. Option A: ∀x(p(x)∨W)≡∀x p(x)∨W\forall x(p(x) \lor W) \equiv \forall x\ p(x) \lor W. Since WW does not depend on xx, the universal quantifier distributes over disjunction with a constant formula. This is logically valid.

  2. Option B: ∃x(p(x)∧W)≡∃x p(x)∧W\exists x(p(x) \land W) \equiv \exists x\ p(x) \land W. Similarly, existential quantification distributes over conjunction with a constant formula. This is logically valid.

  3. Option C: Using the equivalence $A \rightarrow B \equiv

eg A \lor B:: ∀x(p(x)→W)≡∀x(egp(x)∨W)≡∀x(egp(x))∨W≡eg(∃x p(x))∨W≡∃x p(x)→W\forall x(p(x) \rightarrow W) \equiv \forall x( eg p(x) \lor W) \equiv \forall x( eg p(x)) \lor W \equiv eg(\exists x\ p(x)) \lor W \equiv \exists x\ p(x) \rightarrow WHowever,OptionCequatesthisto However, Option C equates this to \forall x\ p(x) \rightarrow W$, which is generally not equivalent. Therefore, C is NOT logically valid.

  1. 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.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

Where do you stand for GATE?

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.

One GATE CSE PYQ every morning

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 in GATE CSE

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 Logic

More from GATE CSE 2020

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2020 · Q39 · MCQ

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

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.