Boolean Algebra Simplification

1. Jan 12, 2012

valastar

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. Jan 12, 2012

Staff: Mentor

So it looks like the output will be HIGH if any two (or more) inputs are HIGH?

3. Jan 12, 2012

valastar

Yes, that is correct.

4. Jan 13, 2012

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.

5. Jan 14, 2012

valastar

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
6. Jan 14, 2012

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.

7. Jan 15, 2012

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.