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


*

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

*$(\exists x~p(x) \lor \exists x~q(x))     \implies  \exists x~(p(x) \lor q(x)) $

*$ \exists x~(p(x) \land q(x))             \implies( \exists x~p(x) \land \exists x~q(x))$ 

*$ \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 :


*

*True, and converse is also true.

*True, and converse is also true.

*True, and converse is not true.

*False, but converse is true.



Can you explain in formal way, please?

 A: $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:

  
*
  
*$(\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.


  
*$(\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.


  
*$ \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.


  
*$ \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).  
