3
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ Using as template a similar thing in your book/notes. I would let $M$ be a structure for the language. We want to prove that a certain implication holds. To verify it, all we need to check is situations where the first part is true. So suppose there really is an $a\in M$ such that $\dots$. $\endgroup$
    – André Nicolas
    Aug 18, 2013 at 13:50
  • $\begingroup$ @AndréNicolas Can you please extend your answer? $\endgroup$
    – Billie
    Aug 18, 2013 at 14:06
  • $\begingroup$ So there is an $a\in M$ such that $R^\ast(a)$ is true in $M$ or $P^\ast(a)$ is true in $M$, were we use $F^\ast$ to mean the interpretation of $F$ in $M$. Suppose first that $R^\ast(a)$ is true in $M$, Then $\dots$. $\endgroup$
    – André Nicolas
    Aug 18, 2013 at 14:18
  • $\begingroup$ There are only 3 predicates and have you not learned a way to prove theorems? $\endgroup$
    – Willemien
    Aug 18, 2013 at 14:18
  • 3
    $\begingroup$ The given formula is false: for a countermodel, take a one-element set whose unique element satisfies $P$ and $Q$ but not $R$. $\endgroup$
    – Zhen Lin
    Aug 18, 2013 at 14:25

2 Answers 2

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Always so excellent with these +1 $\endgroup$
    – Amzoti
    Aug 19, 2013 at 0:30
0
$\begingroup$

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

$\endgroup$

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.