Proving hypothetical sylloligism (p implies q, q implies r, therefore p implies r) with boolean algebra

Question

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.

Answer 1

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.$$

Answer 2

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...