How to prove logical truth in predicate calculus?

Question

Next week I have a final exam in math logic, then I'm trying to solve a sample exam but I'm having a difficulty.

I have a formula under predicate calculus, and I have to prove that it's a logical truth.

12 . (8%) Let $P, R, Q$ be a predicate signs. Prove that:

$\exists x (R(x)\lor P(x)) \to (\forall y \lnot R(y) \to (\exists x Q(x) \to \forall x \lnot P(x))) $

I thought to solve it using a truth table, but I've noticed that there are $5$ predicates which are $2^5 = 32$ rows and I don't think that it's the right way.

How can I prove that this predicate is logical truth?

Please help me. thanks in advance!

Answer 1

We want to prove that the given implication necessarily holds. To verify the formula, we need to check only the situations where the antecedent is true. So we suppose there exists an $x:= a \in U$ such that either $R(a)$ or $P(a)$.

As Zhen Lin suggests, we see that the statement is false when $P(a) \land Q(a) \land \lnot R(a)$ holds, together with a universe U in which for all $\forall x \in U, \lnot R(x)$, i.e., $\lnot \exists x (R(x))$, where $U$ is the universe over which we are quantifying. Then we have a true antecedent but a false conclusion, and hence, a situation in which the implication is false.

Hence the statement fails to be a logical truth.

Answer 2

$\exists x (R(x)\lor P(x)) \to (\forall y \lnot R(y) \to (\exists x Q(x) \to \forall x \lnot P(x))) $

Another perhaps more intuitive approach to show this statement must be false:

Suppose that $\exists x (R(x)\lor P(x))$. Specify $R(a) \lor P(a)$

Suppose further that $\forall y \lnot R(y)$. Since $R(a) \lor P(a)$, we must then have $P(a)$.

Suppose further that $\exists x Q(x)$. Since $P(a)$, we cannot then have $\forall x \lnot P(x)$.