Question 49

Given that $W$ contains no free occurrences of $x$:

• A: $\forall x (p(x) \lor W) \equiv \forall x\, p(x) \lor W$. Since universal quantifier distributes over disjunction with a constant formula $W$, this is logically valid.
• B: $\exists x (p(x) \land W) \equiv \exists x\, p(x) \land W$. Since existential quantifier distributes over conjunction with a constant formula $W$, this is logically valid.
• D: $\exists x (p(x) \to W) \equiv \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$. This is logically valid.

Analysis of Formula C:

• The correct equivalent of $\forall x (p(x) \to W)$ is $(\exists x\, p(x)) \to W$, NOT $(\forall x\, p(x)) \to W$.
• Counterexample: Suppose in domain $D = \{1, 2\}$, $p(1)$ is true, $p(2)$ is false, and $W$ is false.
  • LHS: $\forall x (p(x) \to W)$ requires both $p(1) \to W$ (True $\to$ False = False) and $p(2) \to W$ (False $\to$ False = True) to hold. Their conjunction is False.
  • RHS: $(\forall x\, p(x)) \to W$. Since $\forall x\, p(x)$ is False, False $\to$ False evaluates to True.
  • Since LHS $\ne$ RHS, formula C is NOT logically valid.