# Minimum number of NAND gates to implement f(x,y,z,w)=x(y+zw)+yz'

As the title states, given a function f(x,y,z,w)=x(y+zw)+yz', what are the minimum number of NAND gates you need to implement f?

My first attempt at a solution was to draw a kmap to see if there was a further simplified boolean expression (technically I first drew the truth table to find the minterms). From the kmap, I found f=xy+yz'+xzw.

I know that you can implement AND using two NAND gates, OR using 3 NAND gates, and NOT using a single NAND gate. Thus, I figured, "well we have 1 NOT,2 ORs, 3 ANDs, so we'd need 1+(2*3)+(3*2)=13 NAND gates... But the correct answer is supposed to be 7!?

1. What's wrong/insufficient with my reasoning?
2. How on earth do you implement the function using just 7 NANDs?
• Putting it in SOP form means you have a minimum number of logic layers and thus minimum propagation time, but it doesn't necessarily mean minimum number of gates as far as I know. But I haven't done digital logic in years, so I could be wrong. – Hearth Feb 13 '19 at 16:56
• I believe there is no formal method for optimal NAND implementation. There are some heuristic-based though, but I doubt you are asked to employ one. Probably you are just asked to use your intuition. – Eugene Sh. Feb 13 '19 at 16:57
• Do your kmap. Do SOP. Take deMorgan's – StainlessSteelRat Feb 13 '19 at 16:58
• The common double inversion and apply DeMorgan's theorem -method converts every sum of products easily to NAND-only formula. Start from the original x(y+zw)+yz' because it has less operations than your minimized version. But user @Shashank V M has already said how it should be done, so I do not write a duplicate answer, this stays as a comment. f=((x(y'(zw)')')'(yz')')' I guess many of us cannot see this as a circuit at the first glance, but if you find how to get the same you have figured out the solution. – user287001 Jun 14 at 11:23

I suggest that you sketch out your proposed solution, just replacing the AND, OR, and NOT gates with NANDs as necessary.

Now, look for places where you have two NANDs in series where both NANDs are connected as NOT gates. There is an opportunity for simplification there...

• Different problem, same general approach in terms of how to think about it.... electronics.stackexchange.com/questions/264105/… – CapnJJ Feb 13 '19 at 18:04
• @ElliotAlderson , the method you use increases the time and efforts required to solve the problem very much as you need to cancel the gates again. Instead, use an algebraic approach. – Shashank V M Jun 14 at 13:58
• @ShashankVM Well, the time and effort required will depend on the skills and background of the student. I find the algebraic approach to be quite error prone and unnecessary for simple cases, but to each their own. – Elliot Alderson Jun 14 at 18:38

An algebraic approach is more straightforward. If you replace gates by NAND equivalent, then your circuit will most likely become redundant and then you need to simplify it again.

I have explained in detail how to convert a Boolean expression to NAND form, algebraically, with the help of an example in this answer

It is interesting to note that you can implement the function in question using just 5 NAND gates, not seven. Here's the algebraic manipulation to convert the expression to NAND form: $$\f(x, y, z, w) = x.(y + z.w) + y.\bar{z} = x.y + x.z.w + y.\bar{z}\$$

Taking double complement, we get

$$\f(x, y, z, w) = \overline{\overline{x.y + x.z.w + y.\bar{z}}}\$$

Applying De Morgan's law:

$$\f(x, y, z, w) = \overline{(\overline{x.y}).(\overline{x.z.w}).(\overline{y.\bar{z}})}\$$

The circuit uses 5 NAND gates.

simulate this circuit – Schematic created using CircuitLab