3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Hazım Türkkan Mar 18 '13 at 12:17
  • $\begingroup$ I overlooked the part of the problem about the products, sorry about that. I just added that, see if I am making sense there. $\endgroup$ – Jakub Konieczny Mar 18 '13 at 12:43
  • $\begingroup$ 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? $\endgroup$ – Hazım Türkkan Mar 18 '13 at 14:42
  • $\begingroup$ 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. $\endgroup$ – Hazım Türkkan Mar 18 '13 at 14:54
1
$\begingroup$

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

$\endgroup$

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.