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

Question

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.

Answer 1

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}

Answer 2

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

Answer 3

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