Valid well-formed formulae in predicate calculus?

Question

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

1. $(\forall x~p(x) \implies \forall x~q(x)) \implies( \exists x~\lnot p(x) \lor \forall x~q(x))$
2. $(\exists x~p(x) \lor \exists x~q(x)) \implies \exists x~(p(x) \lor q(x)) $
3. $ \exists x~(p(x) \land q(x)) \implies( \exists x~p(x) \land \exists x~q(x))$
4. $ \forall x~(p(x) \lor q(x)) \implies( \forall x~p(x) \lor \forall x~q(x))$

---

My attempt :

Let $p(x)=\text{x is even}$ and $q(x)=\text{x is odd}$ in set of natural number. Then :

1. True, and converse is also true.
2. True, and converse is also true.
3. True, and converse is not true.
4. False, but converse is true.

Can you explain in formal way, please?

Answer 1

$P$ and $Q$ are unary relations, so you can model each of them as sets $P_s$ and $Q_s$, where $P(x)$ iff $x \in P_s$ and $Q(x)$ iff $x \in Q_s$. Let $W$ be every object in the universe.

So translate each statement into sets:

1. $(\forall x~p(x) \implies \forall x~q(x)) \implies( \exists x~\lnot p(x) \lor \forall x~q(x))$

Convert the $\lor$ to $\implies$, you get:

$$(\forall x~p(x) \implies \forall x~q(x)) \implies( \lnot \exists x~\lnot p(x) \implies \forall x~q(x))$$ $$(\forall x~p(x) \implies \forall x~q(x)) \implies( \forall x~p(x) \implies \forall x~q(x))$$

So the formula is valid if, for any model where $(\forall x~p(x) \implies \forall x~q(x))$ holds, that $(\forall x~p(x) \implies \forall x~q(x))$ also holds.

2. $(\exists x~p(x) \lor \exists x~q(x)) \implies \exists x~(p(x) \lor q(x)) $

If $P_s$ is not empty or $Q_s$ is not empty, then $P_s \cup Q_s$ is not empty. Fairly easy to establish that this holds for any model.

3. $ \exists x~(p(x) \land q(x)) \implies( \exists x~p(x) \land \exists x~q(x))$

If $P_s \cap Q_s$ is nonempty then $P_s$ is nonempty and $Q_s$ is nonempty. Anything will model this.

4. $ \forall x~(p(x) \lor q(x)) \implies( \forall x~p(x) \lor \forall x~q(x))$

If $P_s \cup Q_s = W$ , then $P_s = W$ or $Q_s = W$. This is clearly not true for any choice of $P_s$ and $Q_s$. In fact the only times it will be true is:

• when $P_s = W$, meaning $P(x) = \text{True}$, or
• when $Q_s = W$, meaning $Q(x) = \text{True}$, or
• when $P_s \cap Q_s \ne W$, that is, when there is a value of $x$ where both $P(x)$ and $Q(x)$ don't hold.

Otherwise the choice of $P()$ and $Q()$ will not model (4).