GATE CS 1992 Q92 — Propositional and First Order Logic

A predicate calculus statement is valid if it is true under all possible interpretations.

Let's analyze the options:

• Option A: $(\forall x) P(x) \vee (\forall x) Q(x) \implies (\forall x) (P(x) \vee Q(x))$
  If the antecedent $(\forall x) P(x) \vee (\forall x) Q(x)$ is true, then either $P(x)$ is true for all $x$, or $Q(x)$ is true for all $x$. In either case, every element $x$ satisfies $P(x) \vee Q(x)$. Thus, the consequent $(\forall x) (P(x) \vee Q(x))$ is always true. This statement is valid.
• Options B & C: Consider a domain $D = \{1, 2\}$ where $P(1)$ is true, $P(2)$ is false, $Q(1)$ is false, and $Q(2)$ is true. Here, $(\exists x) P(x) \wedge (\exists x) Q(x)$ is true but $(\exists x) (P(x) \wedge Q(x))$ is false (disproving B). Similarly, $(\forall x) (P(x) \vee Q(x))$ is true but $(\forall x) P(x) \vee (\forall x) Q(x)$ is false (disproving C).
• Option D: Consider a domain $D = \{1\}$ where $P(1)$ is true and $Q(1)$ is false. The antecedent $(\exists x) (P(x) \vee Q(x))$ is true, but the consequent $\sim (\forall x) P(x) \vee (\exists x) Q(x)$ is false. Thus, D is invalid.