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. Sep 17, 2017 at 12:26
• Did you apply all the Rules of Logic? ( e.g. distributive) Sep 17, 2017 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?
– user16324
Sep 17, 2017 at 12:58
• Brian, I tried , but I just can't figure it out ... Sep 17, 2017 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, 2017 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! Sep 29, 2017 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, 2017 at 15:13
• Yes it's made with that tool which implements it Sep 17, 2017 at 15:15