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

boolean-algebralogic-gatesnand

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?

Best Answer

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