Prove tautology without truth using a truth table.

Question

I am struggling to prove, without using truth tables, that the statement is a tautology.

[(p→q)∧(q→r)]→(p→r)

My work so far...

¬[(¬p∨q)∧(¬q∨r)]∨(¬p∨r)

¬(¬p∨q)∨¬(¬q∨r)∨(¬p∨r)

(p ∧ ¬q) ∨ (q ∧ ¬r) ∨ (¬p ∨ r)

Answer 1

Get the two disjuncts out of the third disjunct, then resolve. That is, in the first step, you have $$(p\land\neg q)\lor (q\land\neg r)\lor\neg p\lor r.$$ In the second step, use the last two disjuncts (the '$\neg p$' and the '$r$') to delete the corresponding conjuncts in the first two disjuncts. That is, the '$p$' in the first disjunct can be deleted because you have '$\neg p$' as a top-level disjunct, and the '$\neg r$' can be deleted because you have '$r$' as a top-level disjunct. You're then left with $$\neg q\lor q\lor\neg p\lor r,$$ and the '$\neg q$' and '$q$' cancel each other out, producing $\top$, which leaves you simply with $\top$.

Your mileage may vary, of course, because I don't know which of these steps your teacher allows you to perform. You may have to do intermediate steps, but this will hopefully give you a strategy.