Solving truth value of predicate calculus statements(Just the approach) Which of the following predicate calculus statements is/are valid?


*

*$$\forall x, P(x)\lor \forall x,Q(x) \Rightarrow \forall x, (P(x)\lor Q(x))$$

*$$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \exists x, (P(x)\land Q(x)) $$

*$$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \forall x, P(x)\lor \forall x,Q(x)$$

*$$\exists x, (P(x)\lor Q(x)) \Rightarrow \forall x, P(x)\lor \exists x,Q(x)$$
What is the approach to solve these questions?  I have learned that one way to solve these questions is to consider a $P(x)$ say "all numbers are odd" and $Q(x)$ say "all numbers are even", and then reason out with each option to see which one is true.
Being a CS freshman I have had a hard time understanding these,so can anyone explain to me in a straightforward fashion.
Also is there any mechanical(algebraic) way to solve these using propositional logic rules?
 A: The approach to solving problems like these is to either formulate a
proof to prove them true or to find a counter-example. Note that for
falsehood, a counter-example is enough but for truthhood, an example
says nothing.
The first statement is valid. To consider why, let's say P(x) stands
for "x is red" and Q(x) for "x is yellow." $\forall xP(x) \lor \forall
xQ(x)$ would translated to English state that "all objects are red or
all objects are yellow." $\forall x(P(x) \lor Q(x))$ would state that
"all objects are either red or yellow." It is obvious that the latter
follows from the former.
A proof constructed using natural deduction would look like the
following:


*

*$\forall xP(x) \lor \forall xQ(x)\quad\mathrm{Premise}$

*$a\quad\mathrm{Variable}$

*$\forall xP(x)\quad\mathrm{Assumption}$

*$P(a)\quad\forall x e3$

*$P(a) \lor Q(a)\quad\lor i_1 4$

*$\forall xQ(x)\quad\mathrm{Assumption}$

*$Q(a)\quad\forall x e6$

*$P(a) \lor Q(a)\quad\lor i_2 7$

*$P(a) \lor Q(a)\quad\lor e 1,3-5,6-8$

*$\forall x(P(x) \lor Q(x))\quad\forall x i 2-9$


Since we can transform the statement from the premise to the desired
conclusion it is valid.
The second statement is invalid. Consider $P(x): x = 1$ and $Q(x): x =
2$ then $\exists P(x) \land \exists Q(x)$ is true because you can
insert the values $P(1) \land Q(2)$. But $\exists x(P(x) \land Q(x))$
is false because no single $x$ can be both equal to 1 and 2 at the
same time. Therefore the whole statement is invalid.
You can use the same definitions for $P(x)$ and $Q(x)$ to show that
the third statement is invalid. If the domain are all the natural
numbers, then it is so that $\exists P(x) \land \exists Q(x)$ is true,
but neither $\forall x P(x)$ nor $\forall x Q(x)$ are true, therefore
$\forall x P(x) \lor \forall x Q(x)$ is false and the statement is
invalid.
For the fourth statement, set $P(x): x = 1$ and $Q(x): false$ so that
it is false for every value of $x$. Then $\exists x(P(x) \lor Q(x))$
is true for $x = 1$ but $\forall x P(x) \lor \exists x Q(x)$ is not
true for any value for $x$. It follows that the statement is invalid
