Proving the identity of Boolean Equations with algebraic manipulation

Discussion in 'Homework Help' started by SumTingWong, Jan 22, 2015.

  1. SumTingWong

    Thread Starter New Member

    Jan 22, 2015
    I've been stuck on this for about 4 hours and im starting to get really frustrated and lost, so I'm really hoping you guys can help me out.

    WY + W'YZ' + WXZ + W'XY' = WY + W'XZ' + X'YZ' + XY'Z
    So far ive got W(Y + XZ) + W'(YZ' + XY') on the left side but im not sure thats correct

    Also other equations ive solved with the help of the internet that I would really appreciate if you guys could check over:

    X'Y' + X'Y + XY = X' + Y
    X'Y' + (X'Y + X'Y) + XY
    (X'Y' + X'Y) + (X'Y + XY)
    X'(Y' + Y) + (X' + X)Y
    X'(1) + (1)Y
    X' + Y

    ABC' + BC'D' + BC + C'D = B + C'D
    ABC' + BC' + BC + C'D
    B(AC' + C' + C) + C'D
    B(AC' + 1) + C'D
    B(1) + C'D
    B + C'D
  2. SumTingWong

    Thread Starter New Member

    Jan 22, 2015
    WY + W'(x+X')YZ' + WX(Y+Y')Z + W'XY'(Z+Z')
    WY + W'XYZ + W'X'YZ' + WXYZ + WXY'Z + W'XY'Z + W'XY'Z'

    Is that right so far? im not exactly sure what to do now. Group them up?
  3. MrAl

    Distinguished Member

    Jun 17, 2014

    Lets start with the shorter one first:
    X'Y' + X'Y + XY = X' + Y

    You can try inverting both sides of this expression, then simplifying. You have to use the rules of Boolean Logic and that means for one example if you get a pair like X'*X you know that is equal to 0, so that reduces the complexity.
    Remember when inverting you have to invert each variable and any logical connectives.
    For reference, this expression is true, and for simple expressions like this (only contain two variables) you can check your results by running through all the possible combinations of X and Y and see if both sides are always equal, no matter what the (boolean) value of X or Y is. For example, if X=0 and Y=0 we have:
    which is:
    which is:
    which is:
    So we've proved that the statement is true for the combination X=0 and Y=0. Next we would do the other three combinations. You can do three variables like this too, but as you get to four or more variables it helps to use a computer program to run through all the combinations. Once we get beyond a certain number of variables however the program would take too long to run so this only works up to maybe 16 variables or something like that, before the program starts to take too long to complete.

    Symbolically, lets do a simple one:

    Lets pretend we dont know the answer to this one, and invert both sides, we get:

    You can see how by inverting the left side in particular it turned into a summation.

    Now a slightly harder one:

    and here we end up with a more complicated expression on the left, so we expand the left side and get:

    Next we use Boolean identities to reduce this to:

    so the original statement is true.
    Last edited: Jan 23, 2015
  4. WBahn


    Mar 31, 2012
    A general rule is doing proofs is that you make all of your manipulations to one side (usually the right) and each line is maintained as an equality, not just a dangling expression. If you keep one side of the equality the same (particularly the left side) then it is generally acceptable to not repeat that static expression but to carry down an equals sign directly below the original one. Also, particularly in proofs, it is useful to note the identity or property that you are using to get from the previous line to the current line. Finally, you stop when you have gotten one equation manipulated to match the other -- don't go any further as now you are back to something that is not an exact match.

    So, following the steps you've done above, you might do something like:

    Code (Text):
    2.           X'Y' + X'Y + XY = X' + Y
    3.   X'Y' + (X'Y + X'Y) + XY =           Indempotence
    4.   (X'Y + X'Y) + X'Y' + XY =           Commutative
    5. (X'Y' + X'Y) + (X'Y + XY) =           Associative
    6.   X'(Y' + Y) + (X'Y + XY) =           Distributive
    7.        X'(1) + (X'Y + XY) =           Complementarity
    8.           X' + (X'Y + XY) =           Identity
    9.              X' + (X'+X)Y =           Distributive
    10.                 X' + (1)Y =           Complementarity
    11.                    X' + Y = X' + Y    Identity (QED)
    Applying the same rule multiple times in different places in the same step is usually acceptable depending on how rigorous and formal you are expected to be.
  5. WBahn


    Mar 31, 2012
    You are headed down the right path, but be aware that you may need to expand WY in order to get the necessary consensus terms to make things work out.

    What you are trying to do is generate pairs of terms that allow you to combine them in order to get one of the terms on the right.
  6. SumTingWong

    Thread Starter New Member

    Jan 22, 2015
    I think im way too far down the wrong path right now, i could be wrong though. WY + X'YZ + X'YZ' + W'XYZ' + W'XY'Z' + WXY'Z + W'XY'Z
  7. WBahn


    Mar 31, 2012
    Disembodied expressions are very much use. Don't make readers scroll between one post and another in order to see what you started with, where you are, and where you need to get to. Also, show the work that you did in order to get from where you started to where you are.