6
$\begingroup$

I am working through a textbook, on my own, having to do with logic and mathematical proofs, and I have a question about a problem I just completed. Here's the problem:

"Suppose $P \to (Q \to R)$. Prove that $\lnot R \to (P \to \lnot Q)$ using truth tables."

In this case, the truth tables for the two statements are the same. Do they have to be in order for the whole statement to be true? My understanding is that proofs are implications, so it is only necessary to show that the consequent is true when the antecedent is true. (In this case that means that $\lnot R \to (P \to \lnot Q)$ must be true when $P \to (Q \to R)$ is true, but not necessarily the other way around.)

Do I understand that correctly? And there's nothing special to consider when the antecedent and/or the consequent is an implication?

$\endgroup$
1
  • 2
    $\begingroup$ Your analysis is correct. $\endgroup$ Commented Aug 8, 2015 at 3:44

1 Answer 1

4
$\begingroup$

Your understanding is correct, but it may help to address a few other things you seem to be dealing with. Here is your problem as it currently stands:

Problem: Suppose $P \to (Q \to R)$. Prove that $\lnot R \to (P \to \lnot Q)$ using truth tables.

It may be helpful to rephrase this symbolically; you are being asked to show that the following implication is always true:

Rephrased problem: $[P \to (Q \to R)]\to[\lnot R \to (P \to \lnot Q)]$

For convenience, I'll use the following symbolism:

  • $\Omega: P\to(Q\to R)$
  • $\Phi : \neg R\to(P\to\neg Q)$

The cool thing is that you have noticed, via truth table, that the truth values of $\Omega$ and $\Phi$ are all the same. Thus, you can see that $\Omega\to\Phi$, as desired, but you can also see another important thing: $\Phi\to\Omega$. There's a special term for when this happens: equivalence. By your own observations, you can see that $\Omega\to\Phi$ and $\Phi\to\Omega$, a conjunction of two implications in the form $p\to q$ and $q\to p$. A statement of this form is called an equivalence and is often denoted by $p\Leftrightarrow q$; you can also express the equivalence of $p$ and $q$ by writing $p\equiv q$, where the symbol "$\equiv$" denotes equivalence and this is reflected in how that symbol is actually typeset (i.e., \equiv).

In your own problem, you have that $\Omega\Leftrightarrow\Phi$ (or simply $\Omega\equiv\Phi$); that is, $\Omega$ and $\Phi$ are equivalent. And you can actually see this by looking at your truth table; construct a column for $(\Omega\to\Phi)\land(\Phi\to\Omega)$. The entire column will have only truth values. This means that $\Omega\Leftrightarrow\Phi$ is what is called a tautology, a compound statement that is true for all truth values of the individual statements.

Hopefully that rather long-winded explanation sheds some light on the matter. As we have just established via truth table, $\Omega\equiv\Phi$. If you were asked to prove that $\Omega$ and $\Phi$ are equivalent though, I would encourage you to not use a truth table unless you absolutely have to. I'll outline a little proof below that shows $\Omega\equiv\Phi$, and hopefully this will show you the advantage(s) of not going the truth table route. Feel free to comment if a step does not make sense.


Problem: Show that $P \to (Q \to R)$ and $\lnot R \to (P \to \lnot Q)$ are logically equivalent.

Proof. First note the following for statements $p,q,r$: $$ p\to q\equiv\neg p\lor q\qquad\text{and}\qquad \underbrace{p\lor(q\lor r)\equiv(p\lor q)\lor r}_{\text{associativity of $\lor$}} $$ If you have not encountered the above equivalences, simply construct truth tables to see how they are equivalent. They will be used in the proof below though: \begin{align} P\to(Q\to R)&\equiv\neg P\lor(\neg Q\lor R)\tag{since $p\to q\equiv\neg p\lor q$}\\[0.5em] &\equiv R\lor(\neg P\lor\neg Q)\tag{by assoc. of $\lor$}\\[0.5em] &\equiv \neg R\to(P\to\neg Q).\tag{since $p\to q\equiv\neg p\lor q$} \end{align} This concludes the proof; notice how much easier/faster that was than constructing a truth table.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .