Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology. Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology.
How to prove this without using truth table? I think it need some existing tautologies like $p\to q\iff \neg p\lor q, \:\: p\land p\iff p,\:\:p\land q\iff q\land p$, etc, but I am sure how to do it.
It would be best if someone post the complete procedure here.
 A: There are infinitely many different possible formal systems, each with different rules and axioms. So technically your question cannot be answered. However, here is the standard way of proving the tautology using natural deduction Fitch-style.
$\def\imp{\rightarrow}$
If $( p \imp q ) \land ( q \imp r )$:
  $p \imp q$. [Conjunction elimination]
  $q \imp r$. [Conjunction elimination]
  If $p$:
    $q$. [Implication elimination; also called Modus Ponens]
    $r$. [Implication elimination]
  $p \imp r$. [Implication introduction]
$( p \imp q ) \land ( q \imp r ) \imp ( p \imp r )$. [Implication introduction]
It should be a simple thing to convert this to a proof in any other reasonable formal system. The reason I present it as above is because it is so utterly natural in following our intuitive understanding (which is why it is called natural deduction).
A: One way to prove it is to use $p\to q\iff \neg p\lor q$.
\begin{align}
(p \to q)\land(q \to r)\to (p \to r)&\iff \neg((p \to q)\land(q \to r))\lor (p \to r)
\\
&\iff\neg((\neg p \lor q)\land(\neg q \lor r))\lor (\neg p \lor r)
\\
&\iff((p \land \neg q)\lor(q\land \neg r))\lor (\neg p \lor r)
\\
&\iff(p \land \neg q)\lor((q\land \neg r)\lor (\neg p \lor r))
\\
&\iff(p \land \neg q)\lor((q\lor \neg p \lor r)\land (\neg r\lor \neg p \lor r))
\\
&\iff(p \land \neg q)\lor((q\lor \neg p \lor r)\land (1\lor \neg p))
\\
&\iff(p \land \neg q)\lor((q\lor \neg p \lor r)\land 1)
\\
&\iff(p \land \neg q)\lor(q\lor \neg p \lor r)
\\
&\iff(p\lor(q\lor \neg p \lor r)) \land (\neg q\lor(q\lor \neg p \lor r))
\\
&\iff((p\lor \neg p)\lor q \lor r) \land ((\neg q\lor q)\lor \neg p \lor r)
\\
&\iff(1\lor q \lor r) \land (1\lor \neg p \lor r)
\\
&\iff 1\land 1
\\
&\iff  1
\end{align}
