Trick/insight to I implement given boolean function with minimum numbers of given gate

I solved bunch of questions which give some function and then ask to implement it with minimum number of gates of specific type, each having specific number inputs. I was making mistakes in all those problems by not implementing given function with minimum number of gates.

Let me give those problems one by one and explain my point.


Problem 1


What is minimum number of two input NAND gates required to implement the function:

$f=\overline A \overline C+\overline A\overline B+\overline B \overline C$

I translated the function directly to the circuit as follows:

Then I converted this to NAND-only implementation as follows:

But when I checked the answer, it was saying lesser NAND gates. So I tried something different. I solved equation as follows:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}$

$=\overline{\overline{\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}}}$

$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

And realized that I will need seven NAND gates for following:

• $\overline{A}$

• $\overline{B}$

• $\overline{C}$

• $\overline{(\overline{A}.\overline{C})}$

• $\overline{(\overline{A}.\overline{B})}$

• $\overline{(\overline{B}.\overline{C})}$

• $=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

But then I checked detailed solution and found that the solution has come up with following equation:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}\overline{C}$

$=\overline{A}.\overline{C}+\overline{B}(\overline{A}+\overline{C})$

$=\overline{A}.\overline{C}+\overline{B}\overline{(\overline{A}.\overline{C})}$

$=\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

This requires six NANDs:

• $\overline{A}$

• $\overline{B}

There is no trick. There is no efficient method. The circuit minimization problem is NP-hard (in fact $\Sigma_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-hard, too. That should tell you that there is no systematic approach that always works and is reasonably efficient. Instead, you will have to use heuristics and trial-and-error. For instance, you might have to try multiple methods and take the best circuit you can find among all of them.

StackExchange Computer Science Q#96354, answer score: 4