The GATE Grind

GATE 2020 CS – Question 49

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

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

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

  1. $\forall x(p(x)\vee W)\equiv\forall x\,p(x)\vee W$
  2. $\exists x(p(x)\wedge W)\equiv\exists x\,p(x)\wedge W$
  3. $\forall x(p(x)\to W)\equiv\forall x\,p(x)\to W$
  4. $\exists x(p(x)\to W)\equiv\forall x\,p(x)\to W$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\forall x(p(x)\to W)\equiv\forall x\,p(x)\to W$

Explanation

Since $W$ has no free $x$, $\forall x(p\to W)\equiv\forall x\neg p\vee W$, which is not equivalent to $\forall x\,p\to W\equiv\exists x\neg p\vee W$. Options A, B and D are valid equivalences.