3

I must prove the most basic associativity in boolean algebra and there is two equation to be proved:

(1) a+(b+c) = (a+b)+c (where + indicates OR). (2) a.(b.c) = (a.b).c (where . indicates AND).

I have a hint to solve this: You can prove that both sides in (1) are equal to [a+(b+c)].[(a+b)+c] (I'm pretty sure that it's coming from idempotency.).

We can use all axioms of boolean algebra: distributivity, commutativity, complements, identity elements, null elements, absorption, idempotency, a = (a')' theorem, a+a'b = a + b theorem (' indicates NOT) except De Morgan's Law. Also duality of boolean algebra for sure.

Please help. Thanks in advance.

Hazım Türkkan
  • 51

2 Answers2

5

I assume it should be true (and known) that $a + ab = a$.

Assuming this holds, let $x = a+(b+c)$ and $y = (a+b)+c$. We want to show that $x = y$, and following the hint we reduce to showing $x = xy = y$.

I claim that $ax = a, \ bx = b, \ cx = c$, and likewise for $y$. We check for $ax$: $$ ax = aa + a(b+c) = a + a(b+c) = a$$ Likewise, for $bx$: $$ bx = ba + b(b+c) = ba + (bb+bc) = ba + (b+bc) = ba + b = b$$ The remaining checks are analogous.

Using these identities, you can derive that anything made up of $a,b,c,+,.$ does not change when multiplied by $x$, in particular $yx = x$: $$ yx = ((a+b)+c)x = (a+b)x+cx = (ax+bx)+cx = (a+b)+c = y$$ You can use a symmetric argument to conclude that $yx = xy = x$, and hence the claim follows.

For products, you can use a similar trick. Let $x = a.(b.c)$ and $y = (a.b).c$. I claim that $ x = x + y = y$. To see this, first note that $x + a = a$ (because $x+a = a+ a.(...) = a$. Secondly, $x+b = b$, because $$ x+b = a.(b.c) + b = a.(b.c) + a.b + a'.b = a.(b.c+b) + a'.b = a.b + a'.b = b$$ (I hope this is legit). Likewise, $x+c = c$. Finally, $x + y = y$, because: $$ y = (a.b).c = ((a+x).(b+x)).(c+x) = (a.b + x).(c+x) = (a.b).c + x = y + x$$ (I used the identity $(u+t).(v+t) = u.v + t.u + t.v + t.t = u.v +t$). The proof that $y+x = x$ is symmetric.

Jakub Konieczny
  • 12,588
  • Thanks for that beatiful answer and it's totally useful. Thanks a lot again. I must ask that, did we also prove the associativity of multiplication? I mean with this process, did we prove the equation a.(b.c)=(a.b).c ? – Hazım Türkkan Mar 18 '13 at 12:17
  • I overlooked the part of the problem about the products, sorry about that. I just added that, see if I am making sense there. – Jakub Konieczny Mar 18 '13 at 12:43
  • Sorry but I didn't understand a point; here is this: I think (a.b+x).(c+x) = (a.b).(c+x) => by x's property and then (a.b).c + (a.b).x Because (a.b).c + x is destroying parentheses of (c+x). Can you explain it? – Hazım Türkkan Mar 18 '13 at 14:42
  • Sorry for my rush, I understood it now it came from (a.b+x).(c+x)=(a.b).c + (a.b).x + x.c + x.x and then idempotent law and two absorptions. Thank you so much that's the final and perfect answer. You are the best. – Hazım Türkkan Mar 18 '13 at 14:54
1

The answer from Jakub Konieczny proves $(1):a+(b+c)=(a+b)+c$ just right, but for $(2):a\cdot(b\cdot c)=(a\cdot b)\cdot c,$ I would argue that you should not use it is more elegant not to use $(1)$. After all, they state the same thing but for different operators, so it makes sense to prove them separately.

In particular when proving that $x+b=b$, the statement $$[a\cdot (b\cdot c)]+[(a\cdot b)+(a'\cdot b)]=[a\cdot(b\cdot c+b)]+(a'\cdot b) $$ assumes that $$[a\cdot (b\cdot c)]+[(a\cdot b)+(a'\cdot b)]=[a\cdot(b\cdot c)+a\cdot b)]+(a'\cdot b) $$ So, I think it is better to state that $(2)$ holds because of the duality principle or just be carefull about how to prove each step. For example prove that $b+x=b$ as, $$b+x=b+[a\cdot(b\cdot c)]=[b+a]\cdot[b+(b\cdot c)]=(b+a) \cdot (b)=b+a\cdot b=b$$

To conclude, if you do not want to just state that $(2)$ holds because of the duality principle, use the dual of each step of $(1)$ to derive $(2)$.

Community
  • 1
giannisl9
  • 123