# 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.