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

Question

As the title states, given a function \$f(x, y, z, w) = x.(y + z.w) + y.\bar{z}\$, 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(x, y, z, w) = x.y + y.\bar{z} + x.z.w\$

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?

Answer 1

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.

Answer 2

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}