I have this equation:

D'B' + C'B' + D'A + D'C

which Wolfram Alpha, search: "DNF (~D && ~B) || (~C && ~B) || (~D && A) || (~D && C)", is telling me is equivalent to:

C'B' + D'A + D'C

which is the same except without the D'B' term. How can I derive the second (smaller) one from the first?

Thanks!

 

Well, the fact that a term is extraneous and can be deleted means that all of the things it does have to be covered by some combination of the remaining terms.

In this case, you have D'B' that is apparently redundanct.

Q1) What other terms involve D'?

Q2) What other terms involve B'?

Q3) Given the list from Q1 and the list from Q2, are there any terms have all the same factors (possible inverted) except for D' and B'?

Q4) Can you generate an additional term for from each of the terms in Q3 such that B'D' is a common factor?

Q5) What happens if you then factor B'D' out?

 

Unfortunately I'm a little confused about what you mean for Q3.

Q1) D'A and D'C
Q2) C'B'
Q3) is there any term that has all the same factors, except for D' and B'? Well, each of the 3 listed terms all include either D' or B', so I would have to say that no, there is no such term

 

Okay, let me see if I can phrase it a bit better, or perhaps just showing an example would be best.

I'm trying to eliminate W'Y' and in my first list I have XY'Z and Y'Z while in the second list I have XW' and Z'W'

So, except for W' and Y' (meaning, ignore them), We have factors of XZ and Z in the first list and X and Z' in the second list. So we have a pair that have Z/Z' as common factors (and none, other than W/Y, that are not common).

So we work with Y'Z and Z'W' for the next step.

 

Ah, I see what you meant for Q3 then. Again though, I'm simply lost at trying to catch the meaning of what you say in Q4. When you say "generate another term such that each has B'D' as a common factor", what do you mean by "generate"? I mean, you could multiply each term with (B + B')(D + D'), because those just equal 1, and your terms would have the right factors then but you'd be adding a bunch of terms to the whole equation, which seems kind of counter-intuitive.

So far, in my specific example:

Q1) D'A and D'C
Q2) C'B'
Q3) D'C and C'B' have the same factors (C) excluding D and B
Q4) ?

 

Ah, I see what you meant for Q3 then. Again though, I'm simply lost at trying to catch the meaning of what you say in Q4.

Which means we are making progress. We'll get there.

When you say "generate another term such that each has B'D' as a common factor", what do you mean by "generate"? I mean, you could multiply each term with (B + B')(D + D'), because those just equal 1, and your terms would have the right factors then but you'd be adding a bunch of terms to the whole equation, which seems kind of counter-intuitive.

Very counter-intuitive. Which is what makes the process hard to get your mind wrapped around. We don't need to get as carried away as you are talking about, but it is definitely the right idea.

So far, in my specific example:

Q1) D'A and D'C
Q2) C'B'
Q3) D'C and C'B' have the same factors (C) excluding D and B
Q4) ?

Q5) The D'C term is missing a B' factor. What happens if we multiply it by (1+B')?

Q6) What do we then need to do with C'B'?

Q7) So the additional terms both have B'D' as a common factor. What happens when you factor this out?

 

Q5/Q6) So we do:
D'C + C'B'
=> D'C(1+B') + C'B'(1+D')
=> D'C + D'CB' + C'B' + C'B'D'
=> D'C + D'B'(C + C') + C'B'
=> D'C + D'B' + C'B'

ok, so we've showed how to generate the extra term, so now to get rid of it I just to the opposite. Interesting. So now my question becomes: if I wasn't told that the redundancy was there and could be removed from the original equation, how would I recognize that I need to do this?

Thank you for all the help!

 

Q5/Q6) So we do:
D'C + C'B'
=> D'C(1+B') + C'B'(1+D')
=> D'C + D'CB' + C'B' + C'B'D'
=> D'C + D'B'(C + C') + C'B'
=> D'C + D'B' + C'B'

ok, so we've showed how to generate the extra term, so now to get rid of it I just to the opposite. Interesting. So now my question becomes: if I wasn't told that the redundancy was there and could be removed from the original equation, how would I recognize that I need to do this?

Thank you for all the help!

You're more than welcome, it has been a pleasure working with you.

You ask an excellent question. It's the one that the instructor would ideally propose to the class if someone such as yourself didn't raise it first. Working with the Boolean algebra expressions alone, it is rather difficult to do, but with practice and experience you can get adept at it. You have to first learn what patterns are important and how to work with them and then how to recognize that those patterns are present in the first place. But, as with so many other areas of science and mathematics (and economics and just about any other subject) people are always trying to figure out ways to make doing this easier and more robust. One of the most common approaches is to somehow visualize the data. Just like, given two horrible equations, if you are asked to identify how many points they intersect at within a region of interest, you could spend lots of time manipulating the equations, but it makes much more sense to just plot the two equations on the same set of axes and simply count how many places they intersect at.

For logic equations, there are two main techniques to achieve this. The first is to draw the schematic using normal gate symbols and then visually see the patterns and visually apply DeMorgan's theorems. With just a bit of practice, you can get quite good at this and it is particularly useful if you are trying to minimize the transistor count or the propagation delay. For fundamental logic optimization, the primary means is the Karnaugh map (or K-map). With the K-map, you lay out the truth table in a grad in such a way that between any two adjacent cells only one variable changes. Thus, if there is a HI in both of those cells, then you do not need that variable in the expression. If you were to lay out the truth table for the one you were working with, you would discover that the term that can be eliminated straddles the groups defined by the other two terms we used and that the one we eliminated included no cells that weren't covered by at least on of those other terms. Thus it is redundant and can be eliminated.

Having said that, in some cases you would not want to eliminate that term and, in fact, would want to add it in if it weren't already there. The reason is that, for logic equations that are sensitive to momentary transitions (called glitches), you don't want any adjacent cells that are both HI to not be covered by the same term. The terms that are used to bridge the other groups are called 'consensus terms' and a K-map makes it trivial to identify them.

The problem with K-maps is that they only work well for systems of no more than 4 variables and are very difficult to work with once you have more than 6 variables.

So, with all of that, you can either go look into K-maps on your own, or simply anticipate getting to them in due time. They are actually easy to understand and fun to work with.