Proving hypothetical sylloligism (p implies q, q implies r, therefore p implies r) with boolean algebra I'm trying to prove the hypothetical sylloligism using boolean algebra.  We already have a solution using propositional logic, which relies on proof by contradiction. $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$
Can this be shown simply by simplifying a boolean algebra equation?
$$ (p \implies q) \wedge (q \implies r) = (p \implies r) $$
can represented in boolean algebra as
$$(\overline{p}+q)(\overline{q}+r)=\overline{p} + r$$
Doing math unto it, I get:
$$
\overline{p}\overline{q} + \overline{p}r + q\overline{q} + qr = \overline{p}+r \\
\overline{p}\overline{q} + \overline{p}r + qr = \overline{p}+r \\
$$
From here, I'm not seeing where to proceed.  Is $\overline{p}(\overline{q} + r)$ more useful than, say, $r(\overline{p} + q)$?  Am I incorrect in equating $(p \implies q) \wedge (q \implies r) = (p \implies r)$?  The related link uses implication, and I'm not sure I understand why.
Any advice on what's next?
A few notes: This sounds like a homework question, but it's not.  We're unconstrained in how we solve it (provided it's solved using boolean algebra, the whole point of this endeavor).  Also, I can show the equivalence using truth tables and karnaugh maps if I so chose, but I'm looking for the methodology, not the answer.
 A: If the hypothetical syllogism is a theorem, then:
$$(p\overline{q})+(q\overline{r}) + \overline{p} + r = 1.$$
Here is one way of demonstrating that:
$$\overline{(p\overline{q})+(q\overline{r}) + \overline{p} + r} = 0.$$
$$(\overline{p} + q)(\overline{q} + r) p \overline{r} = 0.$$
$$p (\overline{p} + q)\overline{r}(\overline{q} + r) = 0.$$
$$(p\overline{p} + pq)(\overline{r}\overline{q} + \overline{r}r) = 0.$$
$$(0 + pq)(\overline{r}\overline{q} + 0) = 0.$$
$$(pq)(\overline{r}\overline{q}) = 0.$$
$$(p\overline{r})(q\overline{q}) = 0.$$
$$(p\overline{r})(0) = 0.$$
$$0 = 0.$$
I didn't read the comments, so I suspect you already got a satisfactory answer, but if not, this might be of some help. If some step is wrong or unclear, leave a comment and we'll find the appropriate rule of boolean algebra that justifies it.

Since you explicitly asked for a direct proof and I am stuck at an airport, I'll add the following:
$$(p\overline{q})+(q\overline{r}) + \overline{p} + r = 1.$$
$$(~(p\overline{q})+ \overline{p}~) + (~(q\overline{r}) + r~) = 1.$$
$$(~\overline{q} + \overline{p}~) + (~q + r~) = 1.$$
$$(~\overline{q} + q~) + (~\overline{p} + r~) = 1.$$
$$(1) + (~\overline{p} + r~) = 1.$$
$$1 + \dots = 1.$$
A: Given boolean $p,q,r$, you want to prove $( p \Rightarrow q ) \wedge ( q \Rightarrow r ) \Rightarrow ( p \Rightarrow r )$. Since $( x \Rightarrow y ) \equiv ( \neg x \vee y )$ for any boolean $x,y$, what we want to prove is equivalent to $((p'+q)(q'+r))'+(p'+r) = 1$. This can be checked simply by expanding everything and collecting terms:
$((p'+q)(q'+r))'+(p'+r) = (p'+q)'+(q'+r)'+(p'+r) = pq'+qr'+(p'+r)$
$ = (pq'+p')+(qr'+r) = (q'+p')+(q+r) = (q'+q)+p'+r = 1+p'+r = 1$
Note that in the 4th equality I used the following identity:
$x+x'y = xy+xy'+x'y = (xy+xy')+(xy+x'y) = x(y+y') + (x+x')y$
$ = x+y$ for any boolean $x,y$
In general it will always be possible to prove any tautology in propositional logic using boolean algebra, by expanding everything as in the first line of the solution I gave above and then further dividing each term into the smallest possible pieces given the variables involved. For example $r = pqr+pq'r+p'qr+p'q'r$. After that it is straightforward to check whether all pieces are covered. However this may result in an exponential number of pieces and can often be avoided by a little more clever manipulation as in the second line of the solution. But I'm not sure if there are cases that require an exponentially sized proof...
