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?
  • \$\begingroup\$ 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. \$\endgroup\$ – Hearth Feb 13 '19 at 16:56
  • \$\begingroup\$ 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. \$\endgroup\$ – Eugene Sh. Feb 13 '19 at 16:57
  • 2
    \$\begingroup\$ Do your kmap. Do SOP. Take deMorgan's \$\endgroup\$ – StainlessSteelRat Feb 13 '19 at 16:58

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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.