Help understanding how two boolean equations were reduced

Discussion in 'Homework Help' started by jakk, Oct 24, 2015.

  1. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Hello,

    I am attempting to teach myself/re-learn some basic digital logic design. As part of this, I am currently reading a chapter about boolean algebra. There are two problems which I have the solution to, but I cannot understand what reduction was done to achieve the solutions. Using a k map, I can deduce the same final answers, but I want to understand algebraically what I am missing.

    Problem 1:Y=('A'B'C)+('AB'C)+(A'B'C)+A'BC)+(ABC)

    Problem 2:Y=('A'BC)+('AB'C)+('ABC)+(A'BC)+(ABC)

    I can get problem one down to

    Y=('A'C)+(A'B)+(ABC)

    and problem two down to

    Y=AC+('AB+)+('A'BC)

    However, the solutions I have say problem one should end up being

    Y=('A'C)+(A'B)+(AC)

    and problem two should end up being

    Y=C+('AB)

    Could someone please explain to me how I get from the point I am at now to the final solution? I feel that I must be missing some pretty obvious rules, but I cannot figure out what. Thanks for the help!
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    The usual convention is to place the inverting tick after the symbol, so your 'A would normally be written as A'.

    Also, switching back and forth between two problems is confusing. I understand the flow of the discussion that lead you to presenting it as you did, but it still creates confusing context switches for people reading it.

    How about something like this (keeping the inverting tick marks where you have them and fixing a couple of typos):

    Problem 1: Y = ('A'B'C) + ('AB'C) + (A'B'C) + (A'BC) + (ABC)
    I get: Y = ('A'C) + (A'B) + (ABC)
    Answer: Y = ('A'C) + (A'B) + (AC)

    Problem 2: Y = ('A'BC) + ('AB'C) + ('ABC) + (A'BC) + (ABC)
    I get: Y = AC + ('AB) + ('A'BC)
    Answer: Y = C + ('AB)

    I think one thing you are missing is an understanding of consensus terms.

    This might help: http://forum.allaboutcircuits.com/blog/boolean-logic-working-with-consensus-terms.663/

    In the first one, you have A'B + ABC.

    Expand that to
    A'B + ABC = A'B + A'B + ABC
    = A'B + A'B(C+'C) + ABC
    = A'B + A'BC + A'B'C + ABC
    = (A'BC + ABC) + (A'B + A'B'C)
    = AC('B + B) + A'B(1 + C)
    = AC + A'B
     
    Michael Lake likes this.
  3. shteii01

    AAC Fanatic!

    Feb 19, 2010
    3,388
    497
    k maps allowed?
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    This isn't a homework assignment, but something that the TS is doing on their own. They indicated that they can get the final answers using K-maps, but want to understand how to get those same answers using only Boolean algebra.
     
  5. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Thanks for the info. I had actually considered using consensus and had attempted a bit with it, but I think I gave up a bit too early. I looked at it again and this is what I ended up doing for the first problem (now putting the ticks in the correct place, thanks for the clarification)

    AB'+ABC
    =A(B'+BC)
    =A[(B*1)+BC]
    =A(BC+B'+C)
    =ABC+AB'+AC
    =ABC+A(B'+C)
    =A[BC+(B'+C)]
    =A[BC+C+B']
    =A[C(B+1)+B']
    =A[C+B']
    =AC+AB'

    Was that a correct way of doing that problem as well? I know it was more steps then what you did, but I feel better if I can solve it in a way that I think of as then I know I really understand the concept. This is a problem I have always had, even back with algebra-I can get an answer usually, and sometimes I can simplify it a bit, but I always have a hard time coming up with the full simplification. I guess it just "doesn't click" or something when it comes to me being able to see that I can still simplify things further.

    Regarding K maps-I am teaching myself so I suppose they are "allowed". I was able to get the final answer using k maps of course, but I wanted to see what I was missing at the algebraic level.

    Anyways, I'll take a look at that second problem and see if I can get anywhere. Like I said, I have a real hard time determining when I can/cannot simplify something further. Just out of curiosity, how often does this sort of simplification by hand have to be done in a real job environment vs. using k maps or computer programs to simplify something? I have a computer engineering degree that I obtained a few years ago and really like the idea of designing embedded systems, although right now I work in the IT/networking field. I have always wondered how much my lack of ability to do algebra/math by hand would hold me back should I decide to to apply for an actual engineering job at some point.

    In school, I was always able to do quite well in my EE/control systems classes because I could generate nodal/loop analysis and transfer function equations and then use my calculator to actually solve them. My problem generally wasn't coming up with or generating the equations-it was solving them by hand if need be. I don't have any "real world" experience with doing actual digital logic or embedded systems design outside of some really light hobby stuff I have done, so I always wondered how much of this stuff was just being able to recognize and generate equations and use some computer aid to solve them vs actually needing to sit down and do the simplification by hand.
     
  6. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    2,677
    2,729
    Pretty much never. Discrete logic is rarely used anymore, except in the simplest designs. Mostly, its all compiled now via hardware description languages -- and the reduction is done for you.

    I, though, am a great proponent of understanding fundamentals. When confronted with a seemingly intractable problem, it's always beneficial to have 'first principles' in your pocket from which to start.

    Edit: It's also helpful to know when something is possible -- even when the computer tells you it's not.
     
  7. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    I don't follow this. How is A(B'+BC) equal to A[(B*1) + BC)]

    A(B' + BC) = A[B'(1+C) + BC] = A[B' + B'C + BC] = A[B' + (B'+B)C = A(B' + C) = AB' + AC

    Hard to say. It will depend on the specifics of what you are doing and the tools you have available to you. As an IC designer working for a small company that did full-custom mixed-signal ASIC designs, I did almost all logic design and optimization by hand. But our chips were mostly analog chips using mostly well-structured digital hierarchy and relatively little random logic. We didn't have the money for the high-end tools, plus our designs were very sensitive to things that the high-end tools ignored anyway.
     
  8. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Oops, that was a typo. It should have been

    =A(B'+BC)
    =A[(B'*1)+BC]

    I thought B'=B'(AND)1
     
    jjw likes this.
  9. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    Okay. But then your next step isn't obvious (to me):

    =A[(B'*1)+BC]
    =A(BC+B'+C)

    While it's true, it isn't obvious how you went from the first to the second. A clearer way would be:

    = A(B' + BC)
    = A[B'(1+C) + BC]
    = A(B' + B'C + BC)
    = A(B' + (B' + B)C)
    = A(B' + C)

    Do you see how the leap from each step to the next is small and obvious?
     
    jakk likes this.
  10. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    I have a sheet of theorems from this textbook that I am reading. I used the theorem of "consensus" that you mentioned to make that jump. The theorem in the book just says "(BC)+(B'D)=(BC)+(B'D)+(CD)", so in my case I treated 1 as "D", and I got (B'*1) via the "identity" theorem in the book which states "B*1=B". I then also simplified (B'*1) and (C*1) to B and C, respectively. I do completely understand what you mean about that not being obvious, though.

    The way you wrote it is much more clear. However, I am wondering how you were able to go from the first statement to the second, specifically what allows B' to become B'(1+C). Is this because the "identity theorem" states that "B*1=B", and the "null element" theorem states that "B+1=1", so in this case B'(1+C) is equivalent to B'*1=B'? Thanks for all of the help.
     
  11. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Apparently my edit time limit has been exceeded. I tried the second problem using a method similar to what I had done with the first problem and also a method similar to what you had shown. I got the correct answer both times. Using your method for the second problem

    AC+A'B+A'B'C
    =AC+A'(B+B'C)
    =AC+A'(B(1+C)+B'C)
    =AC+A'(B+BC+B'C)
    =AC+A'(B+C(B+B'))
    =AC+A'(B+C)
    =AC+A'B+A'C
    =AC+A'C+A'B
    =C(A+A')+A'B
    =C+A'B
     
  12. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    You got it. To be truly rigorous it should be done in the two steps that you indicate. First use identity to expand B to B·1 and then use dominance (what you called the "null element", though that doesn't seem to fit with what I think of as "null" anything) to expand 1 to (1+C).
     
  13. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    I'm not aware of any edit time limit -- I've had edit windows open for days without problems. But glad you got it and, more important, understand it.
     
  14. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Cool. Thanks for all of the help with this.
     
  15. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    Anytime.
     
  16. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Sorry to bring this up again, but I have a new equation that I am having issues with

    Y=A'B'+C'D'(A'B+AB')

    The answer should be Y=A'B'+A'C'D'+B'C'D'
     
  17. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    So... what are your issues?
     
  18. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Actually, I think I may have figured it out

    Y=A'B'+C'D'(A'B+AB')

    Y=A'B'+C'D'(A'(B+B')+AB')
    Y=A'B'+C'D'(A'B+A'B'+AB")
    Y=A'B'+C'D'(A'(B+B')+AB')
    Y=A'B'+C'D'(A'+AB')
    Y=A'B'+C'D'(A'(B'+1)+AB')
    Y=A'B'+C'D'(A'B'+A'+AB')
    Y=A'B'+C'D'(B'(A'+A)+A')
    Y=A'B'+C'D'(B'+A')
    Y=A'B'+A'C'D'+B'C'D'

    Is that correct?
     
  19. WBahn

    Moderator

    Mar 31, 2012
    17,737
    4,789
    What rule is allowing you to make that first step?

    You seem to be claiming that B = B + B'.
     
  20. jakk

    Thread Starter New Member

    Nov 6, 2012
    12
    1
    Hmm,looking at that now it looks like perhaps I jumped the gun a bit on that and messed up. I should have still had the second "B" term in there. Back to the drawing board...I'm having a hard time figuring out the first step required to simplify or expand that XOR term which would allow me to get somewhere. Everything I have tried ends up with me back where I started with the same XOR term.
     
    Last edited: Oct 30, 2015
Loading...