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