GATE CS 2003 Q32 — Propositional and First Order Logic

To determine which formula is valid, we can analyze the truth of each option:

Option D: $(\forall x)[\alpha \Rightarrow \beta] \Rightarrow ((\forall x)[\alpha] \Rightarrow (\forall x)[\beta])$

Let us assume the antecedent $(\forall x)[\alpha \Rightarrow \beta]$ is true, and also assume $(\forall x)[\alpha]$ is true. For any arbitrary element $d$ in the domain:

• Since $(\forall x)[\alpha \Rightarrow \beta]$ is true, $\alpha(d) \Rightarrow \beta(d)$ must be true.
• Since $(\forall x)[\alpha]$ is true, $\alpha(d)$ must be true.

By Modus Ponens, $\beta(d)$ must be true. Since $d$ is arbitrary, $(\forall x)[\beta]$ is true. Thus, the implication holds, making Option D valid.

Why other options are invalid:

• Option A: Let $\alpha(x)$ be "$x$ is even" and $\beta(x)$ be "$x$ is odd" over integers. $(\forall x)[\alpha]$ is false, so $(\forall x)[\alpha] \Rightarrow (\forall x)[\beta]$ is vacuously true. However, $(\forall x)[\alpha \Rightarrow \beta]$ is false (since even numbers do not imply odd numbers).
• Option B: If $\beta(x)$ is always false, then $(\exists x)[\alpha \land \beta]$ is false, even if $(\forall x)[\alpha]$ is true.
• Option C: Let the domain be $\{1, 2\}$. Let $\alpha(1)$ be true, $\alpha(2)$ be false, and let $\beta(1)$ be false, $\beta(2)$ be true. Here, $(\forall x)[\alpha \lor \beta]$ is true and $(\exists x)[\alpha]$ is true, making the antecedent true. However, $(\forall x)[\alpha]$ is false.