Implement f = A' + B'C + B'D using NAND only

Thread Starter

mohireza

Joined Mar 4, 2024
2
I have the answer which uses 5 NANDs but my professor says this circuit only needs 4 (he is skipping on the A' NAND and I don't know why)
 

WBahn

Joined Mar 31, 2012
30,012
I have the answer which uses 5 NANDs but my professor says this circuit only needs 4 (he is skipping on the A' NAND and I don't know why)
First, you need to show your best attempt to solve your homework problem. We can then look for errors and provide hints and suggestions -- we can't just give you the answer.

Second, we need more details about the constraints. For instance, are you restricted to 2-input NAND gates, or are you allowed to use n-input NAND gates? Are you allowed to assume that yo have both the straight and complemented versions of the input signals available, or just the straight signals?
 

WBahn

Joined Mar 31, 2012
30,012
So, it appears that you are able to use arbitrary-input NAND gates. That's an important point, since these types of problems usually limit things to only 2-input gates.

Have you verified that your solution actually works?

We know that if ANY input to a NAND gate is LO, then the output is HI, right?

So what happens if A is HI?

That means that the output of the top NAND gate is LO, which means that the output of the final NAND gate is HI, regardless of the state of the other two inputs.

Does that behavior match the logic equation you are trying to implement?
 

WBahn

Joined Mar 31, 2012
30,012
You say that the instructor is "skipping on the A' input". That implies that you have the instructor's solution in order to know what he is or isn't skipping. What is that solution?

Have you verified that it does or does not work? Remember, all you need to show is one combination of inputs that doesn't produce the correct output and you have proven that that solution is wrong.
 

Irving

Joined Jan 30, 2016
3,860
The TS's solution is correct... almost. You don't need the /A, but you do need A.

Original logic /A + /BC + /BD as given

1709665673792.png

The solution is 4 NAND.. The trick is not to do the obvious and start by applying DeMorgan to the /BC + /BD element as /B(C+D). That leads to a 6 gate solution with no obvious further simplification. Instead, start with /A + /BC. Actully its obvious by inspection of the 5 gate circuit of the original using general DeMorgan on the output gate, ie change OR to NAND and invert the inputs...
 

Irving

Joined Jan 30, 2016
3,860
Unfortunately neither the post #8 circuit nor the post #9 circuit meets the thread title requirements.
The circuit in post #8 - if you read what I wrote, is the original logic statement, implemented as given, to show what the required output actually is. I haven't shown the actual 4 NAND result, but hinted as to how to get to it as I didn't want to give it away - yet!
 

Irving

Joined Jan 30, 2016
3,860
I have the answer which uses 5 NANDs but my professor says this circuit only needs 4 (he is skipping on the A' NAND and I don't know why)
Have you actually tested the truth table for your 5 gate solution? Does it actually give the required output?
 

k1ng 1337

Joined Sep 11, 2020
959
The circuit in post #8 - if you read what I wrote, is the original logic statement, implemented as given, to show what the required output actually is. I haven't shown the actual 4 NAND result, but hinted as to how to get to it as I didn't want to give it away - yet!
Were you able to solve the circuit with a maximum of four 2-input NAND gates? It appears TS has left the building so I'd appreciate the answer. I spent quite a while trying to solve it.
 

Irving

Joined Jan 30, 2016
3,860
Were you able to solve the circuit with a maximum of four 2-input NAND gates? It appears TS has left the building so I'd appreciate the answer. I spent quite a while trying to solve it.
That's what happens if you try to use DeMorgan on the /BC + /BD clause first, like this, /BC + /BD = /B(C + D ) = /B/(/C/D) Call that X and do /A + X = /(A/X) = /(A/(/B/(/C/D))) which requires 5 NAND gates, three to give /B, /C, /D, one for /(/C/D),
another for /(/B/(/C/D)) and the fifth for bringing in the A. I couldn't see how to simplify that to the 4 gate solution, though clearly it must be possible...

The 4 gate solution is this:

1710434038684.png
 

WBahn

Joined Mar 31, 2012
30,012
Were you able to solve the circuit with a maximum of four 2-input NAND gates? It appears TS has left the building so I'd appreciate the answer. I spent quite a while trying to solve it.
The constraint isn't 2-input NAND gates, just NAND gates, as evidenced by the TS's solution attempt, which included a 3-input gate.

His solution was almost correct, but he had an additional NAND gate inverter on the A line. Removing that leaves you with a valid four NAND gate solution involving three 2-input and one 3-input gates.
 

WBahn

Joined Mar 31, 2012
30,012
That's what happens if you try to use DeMorgan on the /BC + /BD clause first, like this, /BC + /BD = /B(C + D ) = /B/(/C/D) Call that X and do /A + X = /(A/X) = /(A/(/B/(/C/D))) which requires 5 NAND gates, three to give /B, /C, /D, one for /(/C/D),
another for /(/B/(/C/D)) and the fifth for bringing in the A. I couldn't see how to simplify that to the 4 gate solution, though clearly it must be possible...

The 4 gate solution is this:

View attachment 317640
As soon as you allow the use of NAND gates with more than two inputs, the solution drops out immediately by applying DeMorgan's to the original expression. This is why I asked, in my original response, whether the solution allowed the use of n-input gates.

Y = A' + B'C + B'D

Now apply DeMorgan's:

Y = ( (A')' · (B'C)' · (B'D)' )'
Y = ( A · (B'C)' · (B'D)' )'

And there you have your four-gate solution.

Using square brackets to highlight the gates:

Y = [( (A')' · [ ([ B' ]C)' ] · [ ([ B' ]D)' ] )']
 

Irving

Joined Jan 30, 2016
3,860
As soon as you allow the use of NAND gates with more than two inputs, the solution drops out immediately by applying DeMorgan's to the original expression
Exactly, and if you construct the original logic with gates, as I did in post #8 its obvious by inspection - convert the ANDs to NANDs. remove the invert on A and replace the OR with a NAND...
 
Top