A very quick 6 second question about boolean algebra.

[asd1249jf]

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

 

[ranger]

Put it in a k-map and you will see why it can't be minimized.

 

[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 realize 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.

 

[ranger]

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

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.

 

[ecurbian]

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.

"You do realize" 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.

 

[ranger]

"You do realize" 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.

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