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