Simplifying 4 NAND Gates Into 1 XOR Gate Boolean Algebra?

boolean, boolean-logic, xor

Solution

Your translation of the schematic on Wikipedia is a little bit off. I translated it into

!(!(A!(AB))!(B!(AB)))

Notice that !(XY) and !X!Y are different and that the schematic does not have any or gates (so no `+` operators). From there we can simplify using various boolean logic:

(!(!(A!(AB))) + !(!(B!(AB))))
(A!(AB) + B!(AB))
(A(!A + !B) + B(!A + !B))
(A!B + B!A)

Problem

I am trying to understand with boolean algebra how using 4 NAND Gates can be equivalen to 1 XOR gate. If we look at this picture from wikipedia http://en.wikipedia.org/wiki/XOR_gate#Alternatives There is a schematic of the gate. This is the large expression I came up with to express the schematic. Perhaps it is wrong and that may be my issue? But still I cannot see how to transform the equation into the XOR expression I expect. I have: `!X!Y + X(!X!Y) + Y(!X!Y) + XY(!X!Y)` I know XOR logic looks like this: `X!Y + !XY`. Can anyone clear up my confusion?

Original source