The GATE Grind

GATE 2015 CS (CS2) – Question 63

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

Which first-order formula is logically valid?

  1. $\forall x\exists y R(x,y)\leftrightarrow\exists y\forall xR(x,y)$
  2. $(\forall x[\exists yR(x,y)\to S(x,y)])\to\forall x\exists yS(x,y)$
  3. $[\forall x\exists y(P(x,y)\to R(x,y))]\leftrightarrow[\forall x\exists y(\neg P(x,y)\lor R(x,y))]$
  4. $\forall x\forall yP(x,y)\to\forall x\forall yP(y,x)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $[\forall x\exists y(P(x,y)\to R(x,y))]\leftrightarrow[\forall x\exists y(\neg P(x,y)\lor R(x,y))]$

Explanation

C applies the propositional identity P→R ≡ ¬P∨R inside unchanged quantifiers, so its two sides have identical truth values. The published option is C. As printed, D is also valid by renaming the two universally quantified variables. Therefore the source has an ambiguity: C grading is preserved, and D is not incorrectly described as invalid.

More Discrete Mathematics: Propositional and First Order Logic questions

All Discrete Mathematics: Propositional and First Order Logic questions →