GATE 2020 CS Q.39: solution and answer

GATE 2020 · CSQ.39 · 2 marks · 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$ .

(A)
$\forall x (p (x) \lor W) \equiv \forall x p (x) \lor W$
(B)
$\exists x (p (x) \land W) \equiv \exists x p (x) \land W$
(C)
$\forall x (p (x) \to W) \equiv \forall x p (x) \to W$
(D)
$\exists x (p (x) \to W) \equiv \forall x p (x) \to W$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The formula that is not logically valid is option (C).

Official answer: CSource: Official answer key, GATE 2020 CS (IIT Delhi)

Since $x$ does not occur free in $W$ , a quantifier over $x$ can be moved across $W$ for $\land$ and $\lor$ . So $\forall x (p (x) \lor W) \equiv \forall x p (x) \lor W$ and $\exists x (p (x) \land W) \equiv \exists x p (x) \land W$ . Options (A) and (B) are logically valid.
Rewrite the implication: $p (x) \to W \equiv \neg p (x) \lor W$ .
Option (D): $\exists x (\neg p (x) \lor W) \equiv \exists x \neg p (x) \lor W \equiv \neg\forall x p (x) \lor W \equiv \forall x p (x) \to W$ . So (D) is valid.
Option (C): $\forall x (\neg p (x) \lor W) \equiv \forall x \neg p (x) \lor W \equiv \neg\exists x p (x) \lor W \equiv \exists x p (x) \to W$ . This is not equivalent to $\forall x p (x) \to W$ , because $\exists$ and $\forall$ differ.
Counter-model for (C): take the domain ${1, 2}$ with $p (1)$ true, $p (2)$ false and $W$ false. Left side: $\forall x (p (x) \to W)$ is false, because at $x = 1$ we get true $\to$ false, which is false. Right side: $\forall x p (x)$ is false, so $\forall x p (x) \to W$ is true. The two sides have different truth values, so the equivalence in (C) is not valid.
Hence the formula that is NOT logically valid is (C).

KEY IDEA

A quantifier moves freely across a formula $W$ in which $x$ is not free when the connective is $\land$ or $\lor$ . Under $\to$ , the quantifier flips when it passes into the antecedent: $\forall x (p (x) \to W) \equiv \exists x p (x) \to W$ and $\exists x (p (x) \to W) \equiv \forall x p (x) \to W$ .

WATCH OUT FOR

Pulling $\forall$ out of the antecedent of an implication unchanged. $\forall x (p (x) \to W)$ is not $\forall x p (x) \to W$ . The antecedent turns the universal quantifier into an existential one.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 7 Mathematical logic questions, with notes

GATE 2020 CS Q.39: solution and answer

Answer and solution

More Mathematical logic questions