Boolean algebra: Simplifying logical expression

[Bipolarity]

I was trying a while ago to prove associativity of the XOR operator. That led me to the following problem:

I am trying to prove \overline{(\overline{A}*B+\overline{B}*A)}*B + \overline{B}*(\overline{A}*B+\overline{B}*A) = B


Obviously it can be solved by just creating a truth table and plugging in the four possibilities, but I was wondering whether it can be done without resorting to truth tables. In other words, can the expressions be simplified without plugging in values for A and B?

Please don't give me a complete solution, just tell me hint. I would like to figure this out on my own. I considered using De Morgan's Laws but I then had a feeling it would only complicate the expressions further.

All help is appreciated. Thanks!

BiP

 

[chiro]

Hey BiPolarity.

You have two opportunities to use the distributive law of which one form is (A + B)C = AC + BC where + is OR and AC is just A AND C. You should cancellations (and recall that Not B + B = 1).

 

[Bipolarity]

Thanks chiro.

So boolean addition is associative, distributive and also commutative? Can this be proven? I assume in the case of two inputs we would use a truth table to prove these properties, but with 'n' inputs we can use mathematical induction?

BiP

 

[chiro]

For the rules regarding commutativity, you just use the truth table and show that A + B = B + A and that AB = BA. For associativity, just use commutativity (since anything that is commutative has to be associative).

For distributivity just do it on (A + B)C through a truth table and then the general situation like (A + B + C + D)E or (A + B)(C + D) and so on can be done by induction (you basically just group two variables as one and do it that way).

So like you proposed with induction, you have (A + B + C)D and you let B + C = F in which you have (A + F)D = AD + BF = AD + (B + C)F and since you proved the three variable case you're done.

 

[Preno]

For associativity, just use commutativity (since anything that is commutative has to be associative).

That's not true. Commutativity is: a*b = b*a. Associativity is: (a*b)*c = a*(b*c). There is no reason why one should entail the other and indeed there are counter-examples to that.

 

[chiro]

That's not true. Commutativity is: a*b = b*a. Associativity is: (a*b)*c = a*(b*c). There is no reason why one should entail the other and indeed there are counter-examples to that.

Commutativity implies associativity, for this example. You can re-arrange the terms in any order and you will always get the same result with or without brackets.

It's a form of scalar multiplication not some exotic algebra. (AND is multiplication of bits and OR is basically max of (a + b) and both have the above property.

 

[micromass]

Commutativity implies associativity, for this example.

No, both are axioms for Boolean algebra's. Commutativity doesn't imply associativity as we need it to be a separate axiom.

 

[chiro]

I'm referring to associativity for a single operation: how is this not true? Consider a binary operation AND and a separate one for OR: how are they not associative? You can just arrange them in any order!

 

[micromass]

I'm referring to associativity for a single operation: how is this not true? Consider a binary operation AND and a separate one for OR: how are they not associative? You can just arrange them in any order!

Sure, but this requires a proof or an axiom. And the proof of associativity does not use commutativity. The two conditions are independent.

 

[chiro]

If it's binary, just use a truth table.

XOR is usually used in the context of binary operations and not in sets (we use a symmetric difference for the same thing).

Once you do proof for two or three variables via a truth table, the rest can be shown via induction.

You're not using the Peano axioms or constructing the naturals or ZFC here!

 

[micromass]

If it's binary, just use a truth table.

XOR is usually used in the context of binary operations and not in sets (we use a symmetric difference for the same thing).

Once you do proof for two or three variables via a truth table, the rest can be shown via induction.

OK, if you are proving associativity using a truth table, how exactly are you using commutativity?

Furthermore, you do understand that a boolean algebra is an algebraic object that does not necessarily coincide with the AND and OR from logic, right?

 

[chiro]

OK, if you are proving associativity using a truth table, how exactly are you using commutativity?

Furthermore, you do understand that a boolean algebra is an algebraic object that does not necessarily coincide with the AND and OR from logic, right?

Well you just use a*b = b*a and then make one of them a sub-variable c*d. So you get the fact that all permutations of AND or OR are the same (i.e. using the same operation) and you're done.

You could of course just use a truth table only for associativity and then compare the results in each appropriate column: that would work as well. The above just shows how commutivity in this case allows you multiply them in any order which has a subset of results that prove associativity. (So that basically you get as subset of all possible permutations of multiplications the associative property).

Also I know that binary operations for bits are different than logic, but the guy mentioned a truth table in his first post! He didn't mention a set result.

The stuff the OP mentioned is really basic 101 notation for binary digits: it's what they introduce in 1st year elec engineering or computer science.

 

[micromass]

Well you just use a*b = b*a and then make one of them a sub-variable c*d. So you get the fact that all permutations of AND or OR are the same (i.e. using the same operation) and you're done.

OK, then you get a*(c*d)=(c*d)*a. I don't see how that proves associativity.

 

[chiro]

OK, then you get a*(c*d)=(c*d)*a. I don't see how that proves associativity.

No what I mean is that you generate all permutations of the order of operations for the three variables: So basically (a)(b)(c) = (a)(bc) = (ab)(c). Since (a)(b) = (ab) = (ba) = (b)(a) and (b)(c) = (bc) = (cb) = (c)(b), then you exhaust the small space you need to exhaust to show that it holds.

The commutativity helps intuitively since (a)(b) = (b)(a) and ab = ba which helps understand that any kind of grouping (not only ordering which commutativity specifically shows) in this case won't change a thing.

We know that if (a)(x) = (a)(y) then x = y.

You generate more information in the above, but a subset of this shows associativity when you look at the specific permutations.

 

[micromass]

So basically (a)(b)(c) = (a)(bc) = (ab)(c).

I don't see how that follows from commutativity.

We know that if (a)(x) = (a)(y) then x = y.

This is not true in Boolean algebras.

 

[chiro]

I don't see how that follows from commutativity.

I think I'm just taking the trivial intuition I have for granted with binary arithmetic. I think I have screwed up the connection with commutativity, but basically my thinking process was that any permutation of applying things in both order and in terms of composition are always the same.

This is not true in Boolean algebras.

Yeah I screwed that one up as well.

Bottom line though: just use a truth table since we are dealing with 1's and 0's that are easily exhaustible and if you want to prove all the other stuff (distributive laws and all that) just use truth table for simplest case and then apply induction for the rest.