# How to prove that $[(p \to q) \land (q \to r)] \to (p \to r)$ is a tautology without using the truth table?

I am looking for a way to prove that the statement, $$[(p \to q) \land (q \to r)] \to (p \to r)$$, is a tautology without the help of the truth table. By using only Laws and Theorems like De Morgan's Law, Domination Law, etc. Also, I can't use the rules of inference. Please help, thank you.

As correctly suggested by Wuestenfux, first you should decompose $$\to$$. Then, you should apply several logical equivalences to simplify your formula to $$\top$$ (a formula that is always true). A complete simplification of your formula, using the logical equivalences listed here, is the following:

\begin{align} &\big((p \to q) \land (q \to r) \big) \to (p \to r) \\ \equiv \ & \lnot \big( (\lnot p \lor q) \land (\lnot q \lor r) \big) \lor (\lnot p \lor r) &\text{decomposition of }\to \\ \equiv \ & \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor r) \lor \lnot p \lor r&\text{De Morgan} \\ \equiv \ & (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor \lnot p \lor r &\text{De Morgan} \\ \equiv \ & \lnot p \lor (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor r &\text{commutativity} \\ \equiv \ & \big((\lnot p \lor \lnot\lnot p) \land (\lnot p \lor \lnot q)\big) \lor \big((\lnot\lnot q \lor r) \land (\lnot r \lor r) \big) &\text{distributivity} \\ \equiv \ & \big(\top \land (\lnot p \lor \lnot q)\big) \lor \big((\lnot\lnot q \lor r) \land \top \big) &\text{negation law} \\ \equiv \ & (\lnot p \lor \lnot q) \lor (\lnot\lnot q \lor r) &\text{identity law} \\ \equiv \ & \lnot p \lor (\lnot q \lor \lnot\lnot q) \lor r &\text{associativity} \\ \equiv \ & \lnot p \lor \top \lor r &\text{negation law} \\ \equiv \ & \top &\text{domination law} \\ \end{align}

• Thanks. So the problem on my solution was that, some parentheses weren't removed, that's why i kept on using the distribution law. I also didn't know that you can use associativity like that. Thanks for helping! – Francis Aaron Milano Oct 14 '18 at 9:31

Hint: $$p\rightarrow q$$ is equivalent to $$\neg p\vee q$$.

• Thanks. But my main problem is that whenever I use that theorem then start using the distributive law, i get an infinite loop because instead of shortening the statement, it just gets longer. – Francis Aaron Milano Oct 14 '18 at 9:02

When it comes to simplifying statements, a very handy rule of equivalence is:

Reduction

$$p \land (\neg p \lor q) \equiv p \land q$$

$$p \lor (\neg p \land q) \equiv p \lor q$$

If you have this rule, you can do start by doing what @Taroccoesbrocco does, but finish more quickly:

\begin{align} &\big((p \to q) \land (q \to r) \big) \to (p \to r) \\ \equiv \ & \lnot \big( (\lnot p \lor q) \land (\lnot q \lor r) \big) \lor (\lnot p \lor r) &\text{implication law} \\ \equiv \ & \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor r) \lor \lnot p \lor r&\text{De Morgan} \\ \equiv \ & (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor \lnot p \lor r &\text{De Morgan} \\ \equiv \ & \lnot p \lor (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor r &\text{commutativity} \\ \equiv \ & \lnot p \lor \lnot q \lor \lnot\lnot q \lor r &\text{reduction} \\ \equiv \ & \lnot p \lor \top \lor r &\text{complement} \\ \equiv \ & \top &\text{domination law} \\ \end{align}

You also typically don't need to do an explicit commutation if you have generalized conjunctions or disjunctions, though doing so does help the reader