# 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}$
• $\overline{C}$
• $\overline{(\overline{A}.\overline{C})}$ (used twice in the equation)
• $\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}$
• $\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

So I was wrong twice!!!

Problem 2
Another problem gave truth table of the function and asked to implement it with NOR gate. I prepared truth table for it and grouped zeroes as follows:

Knowing that I have to use NOR, I thought I should form product of sum equation of this and then take double negation to get NOR friendly equation. So, I formed equation for it as follows:

$f=(x+\overline y)(\overline x + y)$
$=\overline{\overline{(x+\overline y)(\overline x + y)}}$ (taking double complement)
$=\overline{\overline{(x+\overline y)}+\overline{(\overline x + y)}}$

Now this looks perfect NOR equation as thought and it requires five NORs. But when I checked the solution, I came to know that this is indeed ExNOR equation. The solution formed sum of product equation of K map:

$xy+\overline x \overline y$

and then implemented ExNOR with four NORs, something like this:

Doubt

I have solved many other problems. It almost always turned out that I have followed one approach and the solution followed another to further reduce the GATE count. I feel there should be some steps / methods to get idea how many minimum number of gated are required. I know this problem is NP complete. However I feel that there has to some definite patterns on k map which can lead us / give direction / provide hint to correct final answer.

Can there be any such method? trick?

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.