1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A very quick 6 second question about boolean algebra.

  1. Feb 8, 2007 #1
    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. jcsd
  3. Feb 8, 2007 #2

    ranger

    User Avatar
    Gold Member

    Put it in a k-map and you will see why it cant be minimized.
     
    Last edited: Feb 8, 2007
  4. Feb 10, 2007 #3
    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
  5. Feb 10, 2007 #4

    ranger

    User Avatar
    Gold Member

    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
  6. Feb 11, 2007 #5
    "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.
     
  7. Feb 11, 2007 #6

    ranger

    User Avatar
    Gold Member

    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: Feb 11, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A very quick 6 second question about boolean algebra.
Loading...