Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean algebra: Simplifying logical expression

  1. Sep 11, 2012 #1
    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 [tex] \overline{(\overline{A}*B+\overline{B}*A)}*B + \overline{B}*(\overline{A}*B+\overline{B}*A) = B [/tex]


    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
     
  2. jcsd
  3. Sep 11, 2012 #2

    chiro

    User Avatar
    Science Advisor

    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).
     
  4. Sep 11, 2012 #3
    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
     
  5. Sep 11, 2012 #4

    chiro

    User Avatar
    Science Advisor

    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.
     
  6. Sep 12, 2012 #5
    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.
     
  7. Sep 12, 2012 #6

    chiro

    User Avatar
    Science Advisor

    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.
     
  8. Sep 12, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

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

    chiro

    User Avatar
    Science Advisor

    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!
     
  10. Sep 12, 2012 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

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

    chiro

    User Avatar
    Science Advisor

    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!
     
  12. Sep 12, 2012 #11

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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?
     
  13. Sep 13, 2012 #12

    chiro

    User Avatar
    Science Advisor

    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.
     
  14. Sep 13, 2012 #13

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, then you get a*(c*d)=(c*d)*a. I don't see how that proves associativity.
     
  15. Sep 13, 2012 #14

    chiro

    User Avatar
    Science Advisor

    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.
     
  16. Sep 13, 2012 #15

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I don't see how that follows from commutativity.

    This is not true in Boolean algebras.
     
  17. Sep 13, 2012 #16

    chiro

    User Avatar
    Science Advisor

    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.

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Boolean algebra: Simplifying logical expression
  1. Boolean Algebra (Replies: 1)

Loading...