Boolean Algebraic Manipulation

Discussion in 'Homework Help' started by amishjeb, Sep 9, 2012.

  1. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    I've been working on these problems for a week now and with the due date coming up soon I'm throwing myself at the internet's mercy. I'm just starting out in a freshman level design logic class and am having a terrible time with the algebraic manipulation. Any help would be greatly appreciated.

    For this question the book has asked me to determine whether the function is valid or not.

    1. x'z + xyz' + x'y + xy' = y'z + xz' + yz' + x'yz
    Working on the left, in excruciating detail...
    x'(z + y) + x(yz' + y') =
    x'(z + y) + x(y + z') =
    x'z + x'y + xy + xz' =
    x'y + xy + x'z + xz' =
    y + x'y + xz' =
    y + xz'

    Working on the right, again, in detail...
    y'z + xz' + yz' + x'yz =
    z(y' + x'y) + z'(x' + y) =
    z(x' + y) + z'(x' + y) =
    x'z + yz + x'z' + yz' =
    x'z + x'z' + yz + yz' =
    x' + y

    So they aren't equivalant? If someone could check my work though.

    Also, I keep coming up with terms that look like: a'b + ab'. Is there a proof that simplifies that or is that as simple as it gets? <-- nevermind, just read the exclusive or page...

    I have two other problems that I'm going to keep working at and may post later if I'm still stuck. So stay tuned? Exciting stuff, I know.

    Like I said, any help would be appreciated.
     
    Last edited: Sep 9, 2012
  2. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    Have you tried using Karnaugh maps?
     
    amishjeb likes this.
  3. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    We haven't gone over that, but it looks like it could be helpful. I'll start diving into that. Thanks!
     
  4. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    You may not have covered Karnaugh maps as yet but now is a good time as any to learn how to use it.

    There is a thread here about Karnaugh maps, in particular, showing examples on how to draw a 4-variable map:
    http://forum.allaboutcircuits.com/showthread.php?t=58572

    What is shown is a map for four variables where there are 16 boxes for each outcome or minterm. For three variables x,y,z there will be 8 boxes for 8 minterms.
    The important thing to note is that the boxes follow a Gray code pattern, e.g. 00-01-11-10

    Drawing two K-maps for the two sides of the equation will tell you at a glance if they are equal.

    When one variable is missing, it means that it is a DON'T CARE condition, i.e. it is true for either cases of the missing variable being 0 OR 1.

    For example, the term x'z = x'y'z + x'yz
    You will therefore fill in two boxes.

    I can show you how to draw a K-map for XYZ variables if you wish.
     
    Last edited: Sep 9, 2012
  5. Maxoriley618

    New Member

    Sep 9, 2012
    13
    0
    x'z + xyz' + x'y + xy' = y'z + xz' + yz' + x'yz
    for sake of my simplicity ill replace a=x b=y c=z
    LHS or Left hand side:
    a'c + abc' + a'c + ac'
    here are my steps
    a(bc+c') = a(b+c) = ab + bc
    = ab + ac + a'c + ac'
    = ab + a'c + a(c+c') = ab + a'c + a
    = ab + a + a'c = a + a'c
    a + a'c = A + C + AB
    c + a + ab = C + A
    that is just the left hand side so far -.-
     
  6. Maxoriley618

    New Member

    Sep 9, 2012
    13
    0
    also there was something in the book that was just touched on in words and not example thats REALLY important for the homework we were asigned.

    Example
    F = ABC + AEF + BF
    F’ = (ABC)’(AEF)’(BF)’ = (A’+B’+C’)(A’+E’+F’)(B’+F’)

    Duality
    Every valid statement has a valid dual. The dual is found by complementing every variable and interchanging the operators ´ and +.

    This makes problems B and C doable by the way.
     
  7. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    The other way of doing it is to expand all terms to minterms

    x'z + xyz' + x'y + xy'

    = x'y'z + x'yz + xyz' +x'yz' + x'yz + xy'z' + xy'z

    and remove any redundancies (i.e. duplicates).

    Then draw a table of all 8 minterms from 000 to 111 and check off which ones are present.
     
    anhnha likes this.
  8. Maxoriley618

    New Member

    Sep 9, 2012
    13
    0
    could you show me how that would prove it was equal or not?

    and how did you expand everything? I thought it was expanded already.
     
  9. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    Do the same for the other side of the equation. If the two tables match then they are equal.
     
    Maxoriley618 likes this.
  10. Maxoriley618

    New Member

    Sep 9, 2012
    13
    0
    I had no idea it was that simple. thank you!
     
  11. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    You're welcome.
    And welcome to AAC, the best electronics forum on the web.
     
  12. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    Let me make sure I'm thinking of this correctly, I may not be as bright as my classmate here:

    This is the left side of the original equation x'z + xyz' + x'y + xy'. If we consider these to me minterms, we can assume that for each of these combinations, the output of the function is 1. So I made the following truth table:

    x y z output
    0 0 0 0
    0 0 1 1
    0 1 1 1
    0 1 0 1
    1 1 0 1
    1 1 1 0
    1 0 1 1
    1 0 0 1

    And the following Karnaugh table (xy along the top and z on the side)

    00 01 11 10
    0 0 1 1 1
    1 1 1 0 1

    Now for the right side y'z + xz' + yz' + x'yz

    x y z output
    0 0 0 0
    0 0 1 1
    0 1 1 1
    0 1 0 1
    1 1 0 1
    1 1 1 0
    1 0 1 1
    1 0 0 1

    At this point I think they're the same. But just for completions sake the Karnaugh table, same thing (xy along the top and z on the side)

    00 01 11 10
    0 0 1 1 1
    1 1 1 0 1

    Does this look right to you guys?
     
  13. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    Max,

    Just to vent to someone in the same situation, I sent the teacher a long email showing my work, what I've tried, etc. and expressing my frustration. He ended up sending back a one line reply telling me to ask the TA. Wouldn't upset me so much if he didn't flat out say "I'm the most helpful person you'll meet" on the first day of class.
     
  14. Maxoriley618

    New Member

    Sep 9, 2012
    13
    0
    Yes I do agree his wording is quite difficult to understand and his teaching style is straight edge with the book but the TA thing did anger me. I'm not sure what to expect or if I can even get a tutor for the class until I'm failing it. Gota love this!
     
  15. Maxoriley618

    New Member

    Sep 9, 2012
    13
    0

    its interesting i've done this a hundred times by hand and cant get it to equal out. but doing it the way you did it it equaled out the first time.
     
  16. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    Are you using the "Gray Code"? I'm not sure why it makes a difference, but MrChips said it was important and the tutorial on here says to use it as well. Also, when I was doing the truth table I wrote the values x'y + xyz' + x'y +xy' and then tried to figure out their values. For instance, x'y I wrote as "01X" and then simply looked at any where in the truth table where x was 0 and y was one, I think you end up finding two lines that meet that condition. I repeated that for each term and then did the same process for the right side.
     
    Last edited: Sep 9, 2012
  17. MrChips

    Moderator

    Oct 2, 2009
    12,437
    3,360
    For a simple table as you have shown you do not need to use the Gray code.

    For the Karnaugh map, you need the Gray code if you want to be able to reduce the expression to its simplest form. That's another lesson.

    You're both on the right track.

    Edit: From your last post you probably meant "01X" for x'y
     
  18. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    Yeah... That's totally what I wrote. *whistles innocently*
     
  19. WBahn

    Moderator

    Mar 31, 2012
    17,736
    4,789
    While enumerating the truth table will show whether they are equal or not, it sheds little light on why the two expressions are equal. A K-map, once you understand how to use it to do logic minimization, will reveal a lot about why the terms in the two expressions end up covering the same set of states, but in different ways. However, there is still something to be said for being able to manipulate the Boolean expressions directly to prove they are equal. If nothing else, it adds that many more tools to your toolbox.

    As others have said, if all you are trying to do is prove they are equal, you can flesh them all out into product terms involving all three variables, eliminate duplicates, and then show that they are the same. But this is really nothing more than enumerating the truth table. Instead, let's do what we were always told to do when doing proofs - manipulate one side until it is transformed into the other side.

    There are several approaches you can use, but I think the one that makes the most fundamental sense, as far as providing a generic strategy, is to recognize the following:

    If I am starting out with f(x,y,z), such as the expression on the left-hand side, then if it really is equal to the g(x,y,z) that is the expression on the right hand side, I have to be able to show that adding any one of the terms from g() to f() changes nothing. I can do this by showing that I can manipulate the terms in f() to produce each of the terms in g() as an additional term. So my first goal is to manipulate f() until it is expressed as f()+g(). Next, if this expanded expression really is equal to g(x), I have to be able to show that I can remove any and all terms that are not in g(x) without affecting the expression. Thus my second goal is to absorb f() from f()+g() to leave me with just g().

    So let's do a bit of this to see how it goes:

    f() = x'z + xyz' + x'y + xy'

    The first term in g() is y'z, so let's see if I can squeeze that term out of f(), meaning that two or more terms in f() are covering y'z making it redundant.

    Our first candidates are pairs of terms that have y' in one and z in the other. There are only two such terms, x'z + xy', so let's start there.

    x'z + xy' = [x'(y+y')z + xy'(z+z')]
    x'z + xy' = [x'yz + x'y'z + xy'z + xy'z']
    x'z + xy' = [x'yz + x'y'z + xy'z + xy'z']

    I am keeping a term in square brackets on the RHS that is identically equal to the LHS so that I can collapse it later without having to backtrack. Because A = A + A, I can duplicate any of the terms in the square brackets outside of them. Since I am trying to generate the term y'z, I will duplicate terms containing that as a factor.

    x'z + xy' = [x'yz + x'y'z + xy'z + xy'z'] + x'y'z + xy'z
    x'z + xy' = [x'yz + x'y'z + xy'z + xy'z'] + (x' + x)y'z
    x'z + xy' = [x'yz + x'y'z + xy'z + xy'z'] + y'z

    I can now collapse the square brackets to get:

    x'z + xy' = [x'z + xy'] + y'z
    x'z + xy' = x'z + xy' + y'z

    So I can replace the terms that make up the LHS above in f() with the terms that make up the right hand side, having the effect of giving me":

    f() = f() + y'z

    You proceed like that to add the rest of the terms of g(), eventually having:

    f() = f() + g()
    f() = x'z + xyz' + x'y + xy' + {y'z + xz' + yz' + x'yz}

    Where I have the terms of g() in {} and will want to keep them intact; my goal is to eliminate all of the others.

    Now you just have to show that each and every term outside the {} is redundant and can be removed. So let's do the first term, x'z. Look in g() and see which terms cover portions of the term we are trying to eliminate. Here we are in immediate luck because one of the terms is x'yz, so that covers us when y is HI. Now we need to get some coverage when y is LO. The only term that can do that is y'z. So let's try those two terms:

    x'yz + y'z = (x'y + y')z
    x'yz + y'z = (x'y + (x'+1)y')z
    x'yz + y'z = (x'y + x'y' + y')z
    x'yz + y'z = (x'(y+y') + y')z
    x'yz + y'z = (x' + y')z
    x'yz + y'z = x'z + y'z

    Notice that, unlike in normal algebra, this expression does NOT mean that x'yz is the same as x'z (i.e., we can't 'subtract' y'z from both sides, because Boolean algebra has no 'subtraction' operation). But we can do the following:

    f() = x'z + xyz' + x'y + xy' + {y'z + xz' + yz' + x'yz}
    f() = xyz' + x'y + xy' + {y'z + xz' + yz' + x'yz + x'z}
    f() = xyz' + x'y + xy' + {y'z + xz' + yz' + x'yz + (x'z + y'z)}

    Which, in light of

    x'yz + y'z = x'z + y'z

    can be written as

    f() = xyz' + x'y + xy' + {y'z + xz' + yz' + x'yz + (x'yz + y'z)}
    f() = xyz' + x'y + xy' + {y'z + xz' + (yz' + y'z) + (x'yz + x'yz)}
    f() = xyz' + x'y + xy' + {y'z + xz' + yz' + x'yz}

    So we have gotten the expression in {} back to the exact form of g() we need. Now we can move on to the next term, and so one. Once we have eliminated the remaining terms, we are done.

    Note that I've been a lot more explicit in the steps that is normally needed.
     
    amishjeb likes this.
  20. amishjeb

    Thread Starter New Member

    Sep 9, 2012
    14
    0
    Thank you for the help WBahn!

    So, now I'm on to a problem that actually asks us to use algebraic manipulation to find the minimum sum-of-products. After reading about Karnaugh maps, I figured I would try to use this to find the simplest form. MrChips, WBahn, or any one else who would be able to look over my work, I'd really appreciate it.

    The function xz + xy' + x'yz + x'y'z'

    My K-Map (xy on the top, z on the vertical)

    00 01 11 10
    0 1 0 0 1
    1 0 1 1 1

    x'y'z' + xy'z' simplifies to y'z'
    xy'z' + xy'z simplifies to xy' and
    x'yz + xyz simplifies to yz.

    So I get xy' + zy + z'y' as the simplest form. Look good?

    PS. I apologize if it seems like I want AAC to do my homework. I promise its not, I'm really just checking to make sure I'm doing things correctly.
     
Loading...