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 🙂
Best Answer
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*}$$