# Create a circuit with max 6 NAND gates

We need to make a logic circuit, the given function is:

f= (AB) + (not(C)) + (not(A)D)

I already tried a bit, and I can manage to make a circuit with 7 NAND gates but not with less... Could anyone help me with that, please? I also added a 3 NAND input gate, which is not allowed...

simulate this circuit – Schematic created using CircuitLab

• Then at least show what you have and how you got there. Use the schematic entry tool to draw the schematic of your solution. – Bimpelrekkie Sep 17 '17 at 12:26
• Did you apply all the Rules of Logic? ( e.g. distributive) – Tony Stewart Sunnyskyguy EE75 Sep 17 '17 at 12:28
• Have you studied combinational logic design. covering logic minimisation, De Morgan's rules, and Karnaugh mapping? Have you tried any of them here? – Brian Drummond Sep 17 '17 at 12:58
• Brian, I tried , but I just can't figure it out ... – Maarten Sep 17 '17 at 13:04
• Your example circuit can't work. That final 3-in NAND is the same as an OR gate with inverted inputs, so I don't think you are ORing in not-C there (in fact, the whole thing looks wrong to me on its face.) – jonk Sep 17 '17 at 14:26

I take it that this is early in a class and that you've not yet been taught enough logic manipulation to be able to rigorously develop a desired result here.

Let me start with something quite simple. A NAND is the exact same thing as an OR, with inverted inputs. You can work this out for yourself once you know De Morgan's two laws:

1. the negation of a disjunction is the conjunction of the negations.
2. the negation of a conjunction is the disjunction of the negations.

So: $F_0=\overline{X\cdot Y}=\overline{X}+\overline{Y}$. Handy to know.

From the above, now:

\begin{align*} \overline{X\cdot Y}&=\overline{C} + \left(A\cdot B + \overline{A}\cdot D\right)\\\\ &=\overline{\overline{\overline{C} + \left(A\cdot B + \overline{A}\cdot D\right)}}\\\\ &=\overline{C\cdot\overline{A\cdot B + \overline{A}\cdot D}}\\\\ & & \therefore X &= C\\\\ & & Y&=\overline{A\cdot B + \overline{A}\cdot D} \end{align*}

So that is one NAND, as follows:

simulate this circuit – Schematic created using CircuitLab

The problem has been reduced. Continue, by focusing on the remaining unresolved portion:

\begin{align*} \overline{X\cdot Y}&=\overline{A\cdot B + \overline{A}\cdot D}\\\\ &=\overline{\overline{\overline{A\cdot B + \overline{A}\cdot D}}}\\\\ &=\overline{\overline{\overline{A\cdot B}\:\cdot\:\overline{\overline{A}\cdot D}}}\\\\ & & \therefore X &= \overline{A\cdot B}\\\\ & & Y&=\overline{\overline{A}\cdot D} \end{align*}

Clearly, the double-negation we are left with means we need to invert the output of the NAND (to make an AND.) So now:

simulate this circuit

Then quickly:

simulate this circuit

Now, the remainder is also obvious:

\begin{align*} \overline{X\cdot Y}&=\overline{\overline{A}\cdot D}\\\\ & & \therefore X &= \overline{A}\\\\ & & Y&=D \end{align*}

So:

simulate this circuit

Now, this process works. And it can work for fairly complex expressions, too. But it won't necessarily find optimal solutions. There are methods to help with that process.

• Thanks! Definitely a good documentation for the community! – Maarten Sep 29 '17 at 7:35

Here is the circuit made using Quine–McCluskey algorithm which is functionally identical to Karnaugh map. Function mapped using the tool below.

P.S. You may find this useful https://sontrak.com/

• Looks like that is straight out of Logic Friday's logic diagram display generator, too. – jonk Sep 17 '17 at 15:13
• Yes it's made with that tool which implements it – Knight Sep 17 '17 at 15:15