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.

  • 1
    $\begingroup$ But how you changed $(p \implies q)∧(q \implies r) \implies (p \implies r)$ into $(p \implies q)∧(q \implies r) = (p \implies r)$ ? $\endgroup$ – Mauro ALLEGRANZA May 3 '14 at 21:51
  • $\begingroup$ That's one of the points I'm unsure of. Given $(p \implies q) \wedge (q \implies r)$ and trying to show that $p \implies r$ should I be equating them? Or, should they be implied? I'm trying to prove that the two forms are equal, or at least, that's how I'm rationalizing it to myself. $\endgroup$ – Jason_L_Bens May 3 '14 at 21:55
  • $\begingroup$ If (p⟹r), does (p⟹q)∧(q⟹r) follow? Well, suppose p=1, r=1, and q=0. Then (p⟹r)=1, but [(p⟹q)∧(q⟹r)]=0. So, (p⟹r) doesn't imply (p⟹q)∧(q⟹r). Thus, you would do better to try and show that {[(p⟹q)∧(q⟹r)]⟹(p⟹r)}=1. $\endgroup$ – Doug Spoonwood May 4 '14 at 2:04
  • $\begingroup$ @Doug So, if I understand properly, by equating them, I was trying to prove $(p \implies q) \wedge (q \implies r) \iff (p \implies r)$? I can understand why that didn't work. $\endgroup$ – Jason_L_Bens May 4 '14 at 2:12
  • 1
    $\begingroup$ @Phox - the error you made is the following: "equatin" both memebers, you assumed that $(p \implies q)∧(q \implies r) \equiv (p \implies r)$ is a tautology, and it is not, while $(p \implies q)∧(q \implies r) \implies (p \implies r)$ is taut. $\endgroup$ – Mauro ALLEGRANZA May 4 '14 at 7:31

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

  • 2
    $\begingroup$ Oh my... Take heart, Phox. Boolean algebra is about the worst way to do proofs like this. If you haven't already, you will probably learn much easier ways very soon. (See truth tables, natural deduction.) $\endgroup$ – Dan Christensen May 4 '14 at 5:52
  • 1
    $\begingroup$ Not so frightening. I was working in Boolean algebra because, as an electrical engineer, it's what I'm more familiar with. It's definitely more elegant when expressed using logic, but I don't think I've developed enough intuition yet to be able to manipulate logic adeptly. $\endgroup$ – Jason_L_Bens May 4 '14 at 7:46

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.