• Support PF! Buy your school textbooks, materials and every day products Here!

A very quick 6 second question about boolean algebra.

  • Thread starter l46kok
  • Start date
  • #1
296
0
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:

Answers and Replies

  • #2
ranger
Gold Member
1,676
1
Put it in a k-map and you will see why it cant be minimized.
 
Last edited:
  • #3
11
0
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:
  • #4
ranger
Gold Member
1,676
1
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.
 
Last edited:
  • #5
11
0
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 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
ranger
Gold Member
1,676
1
"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.
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'). :biggrin:
 
Last edited:

Related Threads on A very quick 6 second question about boolean algebra.

  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
3K
Replies
1
Views
1K
Replies
2
Views
3K
Replies
4
Views
867
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
635
  • Last Post
Replies
3
Views
3K
Top