GATE CS 2020 Q39 — Propositional and First Order Logic

To determine which formula is NOT logically valid, we can use the rules of null quantification. Since $W$ does not contain any free occurrences of $x$, we can move the quantifiers past $W$ using standard logical equivalences.

Step-by-Step Analysis:

• Option A: $\forall x (p(x) \vee W) \equiv \forall x \: p(x) \vee W$
  Since $x$ is not free in $W$, the universal quantifier distributes over disjunction with $W$.
  $$\forall x (p(x) \vee W) \equiv (\forall x \: p(x)) \vee W$$ This is valid.
• Option B: $\exists x (p(x) \wedge W) \equiv \exists x \: p(x) \wedge W$
  Similarly, the existential quantifier distributes over conjunction with $W$.
  $$\exists x (p(x) \wedge W) \equiv (\exists x \: p(x)) \wedge W$$ This is valid.
• Option C: $\forall x (p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
  Let us rewrite the implication $p(x) \rightarrow W$ as $\neg p(x) \vee W$: $$\forall x (p(x) \rightarrow W) \equiv \forall x (\neg p(x) \vee W)$$ Since $x$ is not free in $W$, we can pull $W$ out of the quantifier: $$\forall x (\neg p(x) \vee W) \equiv (\forall x \neg p(x)) \vee W$$ Using the equivalence $\forall x \neg p(x) \equiv \neg \exists x p(x)$: $$\neg (\exists x p(x)) \vee W \equiv \exists x p(x) \rightarrow W$$ Thus, the LHS simplifies to $\exists x p(x) \rightarrow W$, which is not equivalent to the RHS $\forall x p(x) \rightarrow W$.
  Therefore, this formula is NOT logically valid.
• Option D: $\exists x (p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
  Rewriting the implication on the LHS: $$\exists x (p(x) \rightarrow W) \equiv \exists x (\neg p(x) \vee W)$$ Pulling $W$ out: $$\exists x (\neg p(x) \vee W) \equiv (\exists x \neg p(x)) \vee W$$ Using the equivalence $\exists x \neg p(x) \equiv \neg \forall x p(x)$: $$\neg (\forall x p(x)) \vee W \equiv \forall x p(x) \rightarrow W$$ This matches the RHS exactly. Thus, this is valid.