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 Problem.

  1. Sep 7, 2009 #1
    Ok, I am having a difficult time with the following problem. I am to show that the two sides are equal.

    x1'x3 + x1x2x3' +x1'x2+x1x2' = x2'x3+x1x3'+x2x3'+x1'x2x3

    For the LHS I can simplify it to:
    x2(x1'+x1x3') + x1'x3 + x1x2'
    x2x1' + x2x3' + x1'x3 + x1x2'
    x1'x3 + x2x3' + x1x2'

    For the RHS I can simplify to:
    x2(x3' + x1'x3) + x2'x3 + x1x3'
    x2x3' + x2x1' + x2'x3 + x1x3'
    x1'x3 + x1'x2 + x2x3

    At this point I am stuck. I know that both sides should be equal. I have to do this algebraically, so using a truth table is out of it.
  2. jcsd
  3. Sep 8, 2009 #2
    In order to show two Boolean expressions to be equal, it suffices to show they can be transformed into equivalent forms. The most rudimentary way is to find their complete-sum-of-products form (aka disjunctive normal form DNF).

    When the number of variable is small, a Karnaugh map is also useful.

    Removing the distraction of subscripts by letting x = x1, y = x2, and z = x3:

    You need to show that x'z + xyz' + x'y + xy' = y'z + xz' + yz' + x'yz.

    When finding the "completed" version of a fundamental product recall that

    ab = ab(1) = ab(c + c') = abc + abc'

    and then delete extra identical summands.

    Or show that both expressions have the same Karnaugh map.

    & yz & yz' & y'z' & y'z \\
    x & & \checkmark & \checkmark & \checkmark \\
    x' & \checkmark & \checkmark & & \checkmark \\

    When the number of variables increases things get more difficult.

  4. Sep 12, 2009 #3
    I hope this isn't too late.
    Also, I agree with ELUCIDUS about removing subscripts and making it easier, so I'll use his.

    You don't always have to minimize first. You can start out by expanding terms, such as:

    X'Z = X'YZ + X'Y'Z
    Then you can re-combine terms, then minimize. Try it!~

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook