Boolean Law that proves theorem

Question

What Boolean Law proves the following theorem:

(a && b) || (b && c) || (a && c) = (a || b) && (b || c) && (a || c)

I made a truth table for both of them and they are equal, but I'm not able to prove it.

I'd prefer some hints instead of the full answer.

If you made a truth table for both and they're equal, then that IS the proof. — 2012ssohn, Jan 14 '14 at 01:54
@2012ssohn It's a book exercise, and it asks you to probe it using Boolean Laws — jviotti, Jan 14 '14 at 01:55
Proving is for mathematicians. Probing is for space aliens and proctologists. — Cameron Buie, Jan 14 '14 at 13:19

score 1 · Accepted Answer · answered Jan 14 '14 at 02:43

I'm going to use the convention that $a+b$ means a || b and $ab = a \cdot b$ means a && b. Note that each distributes over the other, so that $$ a(b + c) = ab + ac\\ a + bc = (a + b)(a + c) $$ As you may verify via truth table. Now, noting that $x^2 = x$, $x + x = x$, and $1+x = 1$ for all $x$, we can state that $$ \begin{align} (a + b)(b +c)(c+a) &= bca + bcc + bba + bbc + aca + acc + aba + abc\\ &= abc + ab + bc + ac\\ &= ab(c+1) + bc + ac\\ &= ab + bc + ac \end{align} $$ As desired.

Boolean Law that proves theorem

1 Answers1