Prove using properties of logical equivalence $(P\wedge (P \to (Q \to R))) \to (Q \to R)$ is a tautology

Question

Can anyone help me with this problem using properties of logical equivalence:

Prove that $(P\wedge (P \to (Q \to R))) \to (Q \to R)$ is a tautology.

Answer 1

As you did above, you can simplify the problem: $$(P\wedge(P\rightarrow (Q\rightarrow R)))\rightarrow(Q\rightarrow R)$$ $$\equiv (\neg P \lor (P \wedge (Q\wedge\neg R)))\wedge (\neg Q \lor R)$$ Now, $$\equiv ((\neg P \lor P) \wedge (\neg P \lor (Q \wedge \neg R)))\lor (\neg Q \lor R)~~ \mbox{ (distributive property)}$$ $$\equiv (\top \wedge (\neg P \lor (Q \wedge \neg R)))\lor (\neg Q \lor R)~~ \mbox{ (property of } \wedge )$$ $$\equiv (\neg P \lor (Q \wedge \neg R))\lor (\neg Q \lor R)~~ \mbox{(absorption)}$$ $$\equiv (\neg P \lor \neg(\neg Q \lor R))\lor (\neg Q \lor R)~~ \mbox{(negating and applying Morgan's Law)}$$ Let $g:= (\neg Q \lor R)$ for clarity.

This simplifies the expression down to: $$\equiv (\neg P \lor \neg(g))\lor (g)$$ $$\equiv \neg P \lor (\neg(g)\lor (g))~~ \mbox{ (conmutative property) } $$ $$\equiv \neg P \lor \top~~ \mbox{ (property of } \wedge )$$ $$\equiv \top~~ \mbox{(absorption)}$$

Answer 2

In a situation like that you can always recur to the brute force approach. Ugly, but it always works.

You have $3$ variables, i.e. $P$, $Q$ and $R$. Each can be true or false. You have therefore $8$ possibilities to check, not a very huge task.

Still, maybe in your case it is not a tautology.

\begin{array}{|c|c|c|c|} \hline P& Q & R & (P\wedge (P \to (Q \to R))) \wedge (Q \to R) \\ \hline T & T & T & T \\ \hline T & T & F & F \\ \hline T & F & T & T \\ \hline T & F & F & T \\ \hline F & T & T & F \\ \hline F & T & F & F \\ \hline F & F & T & F \\ \hline F & F & F & F \\ \hline \end{array}