1. Limited time only! Sign up for a free 30min personal 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!

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:


    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


    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


    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:


    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


    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


    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