Question 37

A formula in first-order logic is valid if it is true under all possible interpretations (domains and predicates).

Examine Option (D): $\forall x (p(x) \lor q(x)) \implies (\forall x p(x) \lor \forall x q(x))$.

Construct an interpretation:

• Domain: The set of positive integers $\mathbb{Z}^+ = \{1, 2, 3, 4, \dots\}$.
• Let $p(x)$ be "$x$ is even".
• Let $q(x)$ be "$x$ is odd".

Evaluate the antecedent and consequent under this interpretation:

• Antecedent: $\forall x (p(x) \lor q(x))$. Every integer is either even or odd. This is TRUE.
• Consequent: $\forall x p(x) \lor \forall x q(x)$.
  • $\forall x p(x)$ states "all integers are even", which is FALSE.
  • $\forall x q(x)$ states "all integers are odd", which is FALSE.
  • False $\lor$ False is FALSE.
• The implication becomes $\text{True} \implies \text{False}$, which evaluates to FALSE.

Since there exists an interpretation under which the formula is false, it is NOT valid.

All other options are valid tautologies of predicate logic:

• (A) distributes negation through implication: $(\forall x p(x) \implies A) \equiv (\neg \forall x p(x) \lor A) \equiv (\exists x \neg p(x) \lor A)$.
• (B) existential quantification distributes over disjunction: $\exists x (p(x) \lor q(x)) \equiv \exists x p(x) \lor \exists x q(x)$.
• (C) if an element satisfies both $p$ and $q$, then an element satisfies $p$ and an element satisfies $q$.

Hence, option (D) is not valid.