Minimum number of NAND gates required to realize EXOR function
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)}$$