# Prove the following is a tautology

I was trying to prove this statement is a tautology without using truth tables. Something doesn't add it here as I keep getting stuck. Take a look please!

For statements, P, Q and R prove that that the statement $$[(P \implies Q) \implies R] \lor [\neg P \lor Q]$$

It is possible to do this without truth tables right? Here is what I have so far! :)

The statement $(P \implies Q)$ can be collapsed into $(\neg P \lor Q)$. So we can replace the phrase $[(P \implies Q) \implies R]$ with $(\neg P \lor Q) \implies R$. Again, we can collapse that expression and get $(P \land \neg Q) \lor R)$. From here I am not sure where to go. There isn't even an $R$ in the expression $[\neg P \lor Q]$ ! Help would be greatly appreciated! Thank you :)

• You can use \lor and \land for $\lor$ and $\land$. Apr 11, 2013 at 20:52
• Thank you everyone! Very helpful indeed :) Apr 11, 2013 at 21:14
• You’re welcome. Apr 11, 2013 at 21:21

## 3 Answers

You’ve done much of it. You have

$$\Big((P\land\neg Q)\lor R\Big)\lor(\neg P\lor Q)\;,$$

but you’d be better off backing up a step to

$$\Big(\neg(\neg P\lor Q)\lor R\Big)\lor(\neg P\lor Q)\;.$$

Now rewrite this as

$$\Big(\neg(\neg P\lor Q)\lor(\neg P\lor Q)\Big)\lor R$$

and notice that the big parenthesis is of the form $\neg S\lor S$.

You can instead work directly from what you already have, if you want:

\begin{align*} (P\land\neg Q)\lor(\neg P\lor Q)&\equiv\Big(P\lor(\neg P\lor Q)\Big)\land\Big(\neg Q\lor(\neg P\lor Q)\Big)\\ &\equiv\Big((P\lor\neg P)\lor Q\Big)\land\Big(\neg P\lor(\neg Q\lor Q)\Big)\\ &\equiv(\top\lor Q)\land(\neg P\lor\top)\\ &\equiv\top\land\top\\ &\equiv\top\;. \end{align*}

Applying the same equivalence you used in the first transformation:

From $$((\lnot P \lor Q)\rightarrow R) \lor (P \lor Q)$$

You get $$(\color{blue}{\bf\lnot (\lnot P \lor Q)} \lor R ) \lor \color{blue}{\bf (\lnot P \lor Q)}$$

Which is necessarily true because the law of the excluded middle:

$$\lnot(\lnot P \lor Q) \lor (\lnot P \lor Q)$$ is necessarily true. And $T \lor R$ is necessarily true.

• Is this clear now? You have three statements "or'd", and two of them are necessarily true, together, giving us $T \lor R$: If one of two terms in a disjunction is true, then the disjunction as a whole is necessarily true. $T \lor R =$ True. Hence the statement is indeed a tautology, necessarily true. Apr 11, 2013 at 21:17
• Oh yes! Makes perfect sense! Thank you :) Apr 11, 2013 at 22:03
• When OPs answer like that - it is nice! +1 Apr 12, 2013 at 0:32
• Yes, indeed. nicefella's always responsive and shows work, and such. nicefella is a model "asker" for the site. Apr 12, 2013 at 0:35

You're almost there.

(¬P∨Q)⟹R = ¬(¬P∨Q)∨R

¬(¬P∨Q)vR∨(¬P∨Q)

Let (¬P∨Q) = A. Then you have ¬A v R v A. So you have NOT A or A. Which is always true.