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!

 

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

 

k maps allowed?

 

k maps allowed?

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.

 

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.

 

...how often does this sort of simplification by hand have to be done in a real job environment[?]

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.

 

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]

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

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.

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.

 

Oops, that was a typo. It should have been

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

I thought B'=B'(AND)1

 

Oops, that was a typo. It should have been

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

I thought B'=B'(AND)1

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?

 

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.

 

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

 

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.

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

 

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

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.

 

Cool. Thanks for all of the help with this.

 

Cool. Thanks for all of the help with this.

Anytime.

 

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'

 

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'

So... what are your issues?

 

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?

 

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')

What rule is allowing you to make that first step?

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

 

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.