Which one of the following well-formed formulae in predicate calculus is NOT valid?

A formula is valid if it evaluates to true under every possible interpretation.

Let us analyze each option:

• Option (A): $(\forall x\, p(x) \Rightarrow \forall x\, q(x)) \Rightarrow (\exists x\,

eg p(x) \vee \forall x\, q(x))$Using material implication$A \Rightarrow B \equiv eg A \vee B$, the antecedent is$ eg (\forall x\, p(x)) \vee \forall x\, q(x) \equiv \exists x\, eg p(x) \vee \forall x\, q(x)$. Since the antecedent and consequent are logically equivalent, this implication is valid.

• Option (B): $(\exists x\, p(x) \vee \exists x\, q(x)) \Rightarrow \exists x\, (p(x) \vee q(x))$ Existential quantification distributes over disjunction: $\exists x\, (p(x) \vee q(x)) \equiv \exists x\, p(x) \vee \exists x\, q(x)$. Thus, the formula is valid.

• Option (C): $\exists x\, (p(x) \wedge q(x)) \Rightarrow (\exists x\, p(x) \wedge \exists x\, q(x))$ If there exists an element $x_0$ that satisfies both $p(x_0)$ and $q(x_0)$, then clearly $\exists x\, p(x)$ is true (witnessed by $x_0$) and $\exists x\, q(x)$ is true (witnessed by $x_0$). Thus, their conjunction is true, making this formula valid.

• Option (D): $\forall x\, (p(x) \vee q(x)) \Rightarrow (\forall x\, p(x) \vee \forall x\, q(x))$ Universal quantification does not distribute over disjunction. For example, let the domain be the set of integers $\mathbb{Z}$, $p(x)$ be "$x$ is even", and $q(x)$ be "$x$ is odd".

  • Every integer is either even or odd, so $\forall x\, (p(x) \vee q(x))$ is True.

  • However, not all integers are even ($\forall x\, p(x)$ is False), and not all integers are odd ($\forall x\, q(x)$ is False). Thus, $(\forall x\, p(x) \vee \forall x\, q(x))$ is False.

  • The implication $\text{True} \Rightarrow \text{False}$ evaluates to False.

  Therefore, formula (D) is NOT valid.

Thus, the correct option is (D).