Homework Help: A very quick 6 second question about boolean algebra.

1. Feb 8, 2007

l46kok

I was doing a problem, and the distributive problem hit my head, as I kind of blanked out on this one.

Can B'D' + BD be simplified into a smaller equation? Because I'm thinking it's impossible to do so.

(You may be able to apply Demorgan's theorem, but that doesn't really simplify the equation).

[+ is or, * is and, ' is inversion.]

Last edited: Feb 8, 2007
2. Feb 8, 2007

ranger

Put it in a k-map and you will see why it cant be minimized.

Last edited: Feb 8, 2007
3. Feb 10, 2007

ecurbian

IMHO, putting it in a k-map shows visually THAT it cannot be minimized, and then only as a sum of products expression. It does not show "why". Also, if simplifying (x^2+2x+1) to (x+1)^2 is acceptable, then AB+A'B' = (A+B')(A'+B) is also simplifying in some sense. I think that "why" in this case is rather
similar to "why" is 7 a prime number. Since the proof and the question are about the same size, there is no "why".

I realise that SOP is fairly standard form, and that that was probably what the question was about but strictly speaking the question needed clarification on what sort of expressions were being considered, and what was considered simple. For understanding of the question, it should be noted that the formula is not-xor, and simple xor expressions (such as parity) are often difficult to express simply using sop format.

Last edited: Feb 10, 2007
4. Feb 10, 2007

ranger

You do realize that AB+A'B' works out better for design reasons rather than (A+B')(A'+B) right? The latter requires two extra gates (inverters). So for this case, it is in its simplest form.

Last edited: Feb 10, 2007
5. Feb 11, 2007

ecurbian

"You do realise" that each expression when DIRECTLY implemented requires exactly the same number of gates (A.B)+(A'.B') requires two 'and's, two
inverters, and one 'or', while (A+B').(A'+B) requires two 'or's, two inverters and one 'and'. At least if we are speaking of direct and-or-not gate
implementation.

If you are speaking of some other set, such as nand-only, then neither expression is directly implementable. If we have xor, then (A xor B)'
is simpler than either of the above expressions.

In a "design" situation you often have the inverse of a line available anyway, without having to ask for it, and optimisation of the system as a whole can lead to many decisions that seem strange locally. Also, often a solution involving more gates turns out to be better because it happens to match the particular gates left over in the PGA from building the other parts.

6. Feb 11, 2007

ranger

Yup, youre right. For some reason when I was reading you're reply, I was thinking of (AB)' instead of what you wrote - (A'B').

Last edited: Feb 11, 2007