Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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. –  Feanor 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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