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?

  • 2
    $\begingroup$ Trying a concrete example can be used to show that a formula is not valid nut not that it is -- so the only thing you learn from the attempt is that (4) is not valid. $\endgroup$ – Henning Makholm Mar 2 '16 at 11:31
  • 1
    $\begingroup$ (The other three are in fact valid, but your single example doesn't prove that they are). $\endgroup$ – Henning Makholm Mar 2 '16 at 11:32
  • $\begingroup$ I dont think the use of quantifiers in the implication is something right... but Im unsure about it. $\endgroup$ – Masacroso Mar 2 '16 at 13:12

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

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

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.