# Minimum number of NAND gates required to realize EXOR function

While trying to minimize the number of NAND gates for realizing EXOR function, $A\overline{B} \ \cup \ \overline{A} B$,
I used De Morgan's & got the expression $\overline{\overline{\left ( A\overline{B} \right )}\cdot \overline{\left ( \overline{A} B \right )}}$ and hence ended up with $5$ NAND Gates. But my book shows it can be done with $4$ Gates only.
What should be a good approach towards this minimization problem?
Should I avoid using De Morgan's Law here?

• It can be done by 4. But it's a weird simplification. Jan 9, 2016 at 21:19
• Can we reduce 5 gate circuit to a 4 circuit directly or it requires re-simplification from scratch?
– Romy
Jan 9, 2016 at 21:22
• I did once derive it, and from what I remember it was a bit convoluted - I think it requires making it far less simple first but it was about 5 years ago when I studied it, so can't remember off the top of my head. Jan 9, 2016 at 21:51

The 4-gate implementation of the XOR function requires the output of one of the gates to be used twice. As far as I know, there's no direct algorithmic way to come up with such solutions; they must be "discovered".

In a sense, you have to "de-optimize" the solution before optimizing it, and knowing what deoptimization step makes sense is a matter of intuition. In this case, it requires the observation* that

$$A\cdot\overline{B} = A\cdot\overline{(A\cdot B)}$$

and

$$\overline{A}\cdot B = \overline{(A\cdot B)}\cdot B$$

and then realizing that the $\overline{(A\cdot B)}$ term for both right-hand expressions can be generated by the same gate.

*The details:

Since $A\cdot\overline{A} = 0$, you can add this term to any expression without changing it:

$$A\cdot\overline{B} = A\cdot\overline{A} + A\cdot\overline{B}$$

Now, factor out the A

$$\ldots = A\cdot(\overline{A} + \overline{B})$$

and apply DeMorgan's:

$$\ldots = A\cdot\overline{(A\cdot B)}$$