How to prove the identity of the following Boolean equations?

Discussion in 'Homework Help' started by Alice., Feb 2, 2013.

  1. Alice.

    Thread Starter New Member

    Jan 18, 2012
    9
    0
    Using boolean manipulation, how could I prove these two sides are equal? For number one, I was considering manipulating both sides until they match. I can't seem to manipulate it correctly though.

    1. wy + w'yz' + wxz + w'xy' = wy + w'xz' + x'yz' + xy'z
    2. ad' + a'b + c'd + b'c = (a' + b' + c' + d')(a + b + c + d)

    The notation I'm using is: ( ' = NOT ) ( + = OR ) ( * or multiplication = AND )
    Here is a link to the basic boolean manipulation rules: Boolean Algebra Laws
    Thanks for any help or input!
     
    Last edited: Feb 2, 2013
  2. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    You need to show us the work you have done so far so that we can look things over and help you identify where you are going wrong or give you some hints on where to go next.
     
  3. Alice.

    Thread Starter New Member

    Jan 18, 2012
    9
    0
    My work so far hasn't lead to anything correct though.
    For number one, so far I have:

    LEFT:
    wy + w'yz' + wxz + w'xy'......given
    w'(yz' + xy') + wy + wxz......distributive
    w'(y'+zx'+y)' + wy + wxz..... de morgan
    w'(zx)' + wy + wxz..............identity
    w'(z'+x') + wy + wxz............de morgan
    w'z' + w'x' + wy + wxz.........destributive
    w'x' + z + w'z' + wy.............x + x' · y = x + y
    w' + z + wy + w'x'..............."
    w' + x + wy.......................x + x · y = x

    RIGHT:
    wy + w'xz' + x'yz' + xy'z........given
    wy + z'(w'x + x'y) + xy'z.......distributive
    wy + z'(xw' + yx') + xy'z.......associative
    wy + z'(x' + wy' + x)' + xy'z...de morgan
    wy + z'(wy')' + xy'z..............identity
    wy + z'(w' + y) + xy'z...........de morgan
    wy + z'w' + z'y + xy'z...........distributive
    wy + z'w' + x + z'y...............x + x' · y = x + y
    wy + x + z'(w'+y)................distributive
    ?????

    __________________________________________________________________

    for number two:

    LEFT:
    ad' + a'b + c'd + b'c .................................given
    (a'+d)' + (a + b')' + (c + d')' + (b + c')'.........de morgan
    ???


    RIGHT:
    (a' + b' + c' + d')(a + b + c + d)
    (abcd)'(a'b'c'd')'........................................de morgan
    ????
     
    Last edited: Feb 2, 2013
  4. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    That's fine. It let's us see how you are approaching the problem and get a feel for your style and the level at which you are working. I haven't got time to look at it right now, but wanted to get back and let you know that you haven't been abandoned. I am going to look at it, probably in a few hours.
     
  5. Alice.

    Thread Starter New Member

    Jan 18, 2012
    9
    0
    Thanks!

    Okay, I managed to prove number one with truth tables generated online.
    I'm sure that's not what the professor wants though.

    [​IMG]
     
  6. Alice.

    Thread Starter New Member

    Jan 18, 2012
    9
    0
    And I tried redoing number two:

    LEFT:
    ad' + a'b + c'd + b'c .................................given
    ((ad')' * (a'b)' * (c'd)' * (b'c)')'...................de morgan
    (a'+d * a + b' * c + d' * b + c)'..................de morgan
    (a'+da + b'c + d'b + c)'..............................cleaned it up
    (a'+d + b'c + d'b + c)'................................x + x' · y = x + y
    (a'+d + b + b'c + c)'.................................."
    (a'+d + b + c + c)'...................................."
    (a'+d + b + c)'..........................................identity
    (ad'b'c')...................................................de morgan
    ???


    RIGHT:
    (a' + b' + c' + d')(a + b + c + d)
    (abcd)'(a'b'c'd')'................................ ........de morgan
    ????
     
  7. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    You're right, it's not what the professor wants if they specified that you are to prove it using Boolean manipulation. But starting with the truth tables will (1) let you see that they really ARE the same and that your not chasing a wild goose, and (2), let you see the structure and how the two sides relate.

    But to get at that last part, I'd recommend using online truth generators and other tools like that for problems like this (as in, problems where the point is for you to learn a set of skills as opposed to problems where you are designing a circuit for a customer).

    Instead, do it by hand so that you can see where the pieces parts from the two sides relate:

    LHS: wy + w'yz' + wxz + w'xy'
    RHS: wy + w'xz' + x'yz' + xy'z

    w x y z LHS RHS
    0 0 0 0
    0 0 0 1
    0 0 1 0 w'yz' x'yz'
    0 0 1 1
    0 1 0 0 w'xy' w'xz'
    0 1 0 1 w'xy' xy'z
    0 1 1 0 w'yz' w'xz'
    0 1 1 1
    1 0 0 0
    1 0 0 1
    1 0 1 0 wy wy,x'yz'
    1 0 1 1 wy wy
    1 1 0 0
    1 1 0 1 wxz xy'z
    1 1 1 0 wy wy
    1 1 1 1 wy,wxz wy


    You can immediately see that the term they have in common, namely wy, covers part of one of terms on each side. That can be useful. You can also see which terms on one side are covered by which combination of terms on the other.

    Now remember some of the games you can play with Boolean algebra, like:

    wy = w(x+x')y = wxy + wx'y

    to generate terms that you need.

    Your goal then is to start on one side and generate the terms on the other side. In doing so, you will probably have to generate some additional terms that you don't want to survive. That's fine. Once you have all of the terms on the other side generated, now proceed to absorb all of the unwanted terms into the one that you do want to keep. If the sides are equal, you are guaranteed that this is possible.

    As an example, let's start with the LHS and generate the term x'yz' from the RHS:

    wy + w'yz' + wxz + w'xy'

    If we want x'yz', we can first expand this to get

    x'yz' = (w+w')x'yz' = wx'yz' + w'x'yz'

    If we can generate BOTH of the four-input terms from the LHS, then we know we can combine them to get the single three-input term we want.

    All we need is a term on the LHS that is a subset of one of the terms we want to generate. Since wy is a subset of wx'yz' -- arguably, it is a superset if we are thinking in terms of the states it covers, but it is a subset in terms of how it is written down -- we can do this:

    wy = wy(1 + x'z') = wy + wx'yz'

    Similarly, w'yz' is a subset of w'x'yz', so

    w'yz'(1 + x') = w'x'yz'

    The end result is that my steps look like:

    Code ( (Unknown Language)):
    1.  
    2. LHS = wy + w'yz' + wxz + w'xy'
    3.     = wy(1 + x'z') + w'yz' + wxz + w'xy'          // dominance
    4.     = wy + wx'yz' + w'yz' + wxz + w'xy'           // distributive - AND over OR
    5.     = wy + wx'yz' + w'yz'(x' + 1) + wxz + w'xy'   // dominance
    6.     = wy + wx'yz' + w'x'yz' + w'yz' + wxz + w'xy' // distributive - AND over OR
    7.     = wy + (w+w')x'yz' + w'yz' + wxz + w'xy'      // distributive - AND over OR
    8.     = wy + (1)x'yz' + w'yz' + wxz + w'xy'         // complementarity
    9.     = wy + x'yz' + w'yz' + wxz + w'xy'            // AND identity
    10.  
    Note that I have take liberaties with using commutivity and associativity to reorder terms and factors within terms without showing the process step by step. This is commonly allowed in proofs, but not always.

    I meant to note earlier that I like that you are showing which properties you are using at each step. That is the proper way to to a proof. But keep in mind that while it is useful to manipulate both sides until you get them to agree in order to figure out how to proceed, this is generally considered not appropriate in the final proof. You want to manipulate one side (generally the left side) until you get it to match the original version of the other side. But once you get the LHS to match a manipulated version of the RHS, you can simply work your manipulations backward to the original RHS.
     
    Alice. and djsfantasi like this.
Loading...