Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Boolean Algebra Simplification

  1. Jan 12, 2012 #1
    1. The problem statement, all variables and given/known data

    Hey PF!

    I'm supposed to "Optimize the equation for minimal input-output delay with 3-input NAND gates of 1.8ns delay each." It'll become much clearer at my attempt at a solution, I hope.

    2. Relevant equations

    De Morgan's laws, K-maps, the sort...


    3. The attempt at a solution


    So this is part of a homework assignment I've been struggling with for a while now. We were given a word problem and had to simplify it using three input NAND gates.

    I've simplified the actual word problem to :

    F(ABCD)= AB + CD + BD + BC + AD + AC

    As you can see this doesn't use any NAND gates, so I simplified it further to:

    (A NAND B) NAND (A NAND C) NAND (A NAND D) NAND (B NAND C) NAND (B NAND D) NAND (C NAND D)

    Sorry for typing out the NANDS, I thought it would be easier to see than those pesky ' marks.

    How do I go about simplifying this further to 3 INPUT NANDS?

    I appreciate any guidance!
     
  2. jcsd
  3. Jan 12, 2012 #2

    NascentOxygen

    User Avatar

    Staff: Mentor

    So it looks like the output will be HIGH if any two (or more) inputs are HIGH?
     
  4. Jan 12, 2012 #3
    Yes, that is correct.
     
  5. Jan 13, 2012 #4

    NascentOxygen

    User Avatar

    Staff: Mentor

    Were you given the answer? I get two different implementations, each using 8 gates.

    One uses three as inverters, and ends up with a maximum of 4 gates in series.
    The other uses four as inverters, but has a maximum of 3 gates in series.

    The latter would have least delay. I have no idea whether there is any better implementation, though.
     
  6. Jan 14, 2012 #5
    Wow 8 gates! Is that inclusive or exclusive of the inverters that you used?

    The solution has not been given out yet, so I'm still working on it.

    I was able to demorgan the solution down to:

    -(-a*-b*-c)*-(-a*-c*-d)*-(-a*-b*-d)*-(-b*-c*-d)

    Is that the minimized equation that you used?

    I mapped it using a total of 9 gates, of which 3 were inverters. The maximum gate delay was 4 though, so the idea of a solution with a lesser delay seems attractive.
     
    Last edited: Jan 15, 2012
  7. Jan 14, 2012 #6

    NascentOxygen

    User Avatar

    Staff: Mentor

    Is this a notation that you invented? I thought there were enough notations already...
    = A•(B+C) + D•(A+B) + C•(B+D)

    Replace each red + with a NAND (and inverters), and finally implement the three black + with a NAND.

    I haven't checked it, so no guarantees.
     
  8. Jan 15, 2012 #7

    NascentOxygen

    User Avatar

    Staff: Mentor

    Now, I have checked it. I discovered I blundered. :grumpy:

    I can't implement it in fewer gates than you managed. So it's 9, with up to 4 in series.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook