Let $R, P , Q$ be relations, prove that the following statement is tautology 
Let $P, R, Q$ be relations. Prove that:
$\exists x(R(x) \vee P(x)) \to (\forall y \neg R(y) \to (\exists xQ(x)
 \to \forall x \neg P(x)))$ is a tautology.

How do I do so? please help. 
 A: Relations of arity 1 (that is the relations that take only one argument) are just subsets of the universe. Therefore, your formula can be translated into
$$(R \cup P \neq \varnothing) \to (R = \varnothing \to (Q \neq \varnothing \to P = \varnothing))$$
and then simplified into
$$(R \neq \varnothing \lor P \neq \varnothing) \to (R = \varnothing \to (Q \neq \varnothing \to P = \varnothing)),$$
and further into
$$(r \lor p) \to (\neg r \to (q \to \neg p)),$$
where $r := (R \neq \varnothing)$, etc. Now, let's set $\neg r$, $p$ and $q$, then $$(0\lor 1) \to (1 \to (1 \to 0)) = 1 \to (1 \to 0) = 1 \to 0 = 0,$$
which shows that your formula is not a tautology. To generate appropiate example, we set $U = \{\bullet\}$ and $R = \varnothing, P = U, Q = U$. Now we evaluate
$$\exists x_1(R(x_1) \vee P(x_1)) \to (\forall y_2 \neg R(y_2) \to (\exists x_3Q(x_3)
 \to \neg \exists x_4 P(x_4))) $$
by setting $x_1 = \bullet$, $x_3 = \bullet$ and $x_4 = \bullet$ (observe that I have changed $\forall x \neg P(x)$ to $\neg \exists x_4 P(x_4)$, so that I can put some value there). What we get is
$$(R(\bullet) \vee P(\bullet)) \to (\forall y_2 \neg R(y_2) \to (Q(\bullet)
 \to \neg P(\bullet))). $$
Now, $\forall y_2 \neg R(y_2)$ is true, so we get exactly the same expression as before, i.e. your formula is false in this case. 

What would make it a tautology is, for example, $\land$ in the beginning
$$\exists x_1(R(x_1) \land P(x_1)) \to (\forall y_2 \neg R(y_2) \to (\exists x_3Q(x_3)
 \to \forall x_4 \neg P(x_4))) $$
which could be more easily seen with
$$(R \cap P \neq \varnothing) \to (R = \varnothing \to (Q \neq \varnothing \to P = \varnothing)).$$
If we substitute $\alpha := (Q \neq \varnothing \to P = \varnothing)$, that is
$$(R \cap P \neq \varnothing) \to (R = \varnothing \to \alpha),$$
then we can observe that $\alpha$ does not matter, because $(R \cap P \neq \varnothing)$ implies $R \neq \varnothing$. To do it more formally, consider two cases:


*

*$R = \varnothing$, then the left side of the top-most implication is false, hence all is true.

*$R \neq \varnothing$, then the left side of the $R = \varnothing \to \alpha$ is false, so the right side of the top-most implication is true, hence, the expression is true.


I hope this helps.
A: This isn't a tautology. Consider a universe with one single object such that the object satisfies $P$ and it doesn't satisfy $R$. For simplicity let $Q$ mean the same as $P$.
Then it is true that $\exists x(R(x) \lor P(x))$. It is also true that $\forall y \neg R(y)$. Furthermore it is true that $\exists xQ(x)$. However it is false that $\forall x \neg P(x)$ because of our initial hypothesis.
A: Drawing the truth table with $2^3$ possible valuations, it turns out there are four columns with the value $0$ which means the statement is not a tautology. 
