How to construct XOR gate using only 4 NAND gate?
From that formula? It can be done. But it's easier to start with this one: (using a different notation here)

a ^ b = ~(a &amp; b) &amp; (a | b)


Ok, now what? Eventually we should derive ~(~(~(a &amp; b) &amp; a) &amp; ~(~(a &amp; b) &amp; b)) (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice).

So make something that looks like ~(a &amp; b) &amp; a (and the same thing but with a b at the end) and hope that it'll stick around: (and distributes over or)

(~(a &amp; b) &amp; a) | (~(a &amp; b) &amp; b)


Pretty close now, just apply DeMorgan to turn that middle or into an and:

~(~(~(a &amp; b) &amp; a) &amp; ~(~(a &amp; b) &amp; b))


And that's it.