XOR using NAND gates If I am correct, the puzzle can be solved with 4 gates.  In a few minutes I worked out that: XOR = ( (X NAND Y) NAND X) NAND ( (X NAND Y) NAND Y) Using the output of one gate twice allows for four gates. x -------------+-- NAND -+                   |                | x,y - NAND -+              +-- NAND --> RESULT                   |                | y -------------+-- NAND -+ Devlin Friday, March 01, 2002 Damn, the fomatting failed to show: X NAND Y = OUTPUT1 X NAND OUTPUT1 = OUTPUT2 Y NAND OUTPUT1 = OUTPUT3 OUTPUT2 NAND OUTPUT3 = RESULT = X XOR Y Devlin Friday, March 01, 2002 What logic reduction are you using? I got a slon with 5 gates in them, A exor B = ABbar + AbarB was my starting point Sh Tuesday, March 05, 2002 When I solved it the first time, it was by starting at the same point and observing the inputs.  Afterwards, I decided to prove it and came up with the following. Realizing that: 1. A exor B = ABbar + AbarB 2. A nand B = Abar + Bbar 3. ABbar = A(Abar + Bbar) 4. AAbar = 0 Starting from (1) A exor B = AbarB + ABbar and applying (2) A exor B = ( (AbarB)bar (ABbar)bar )bar results in one NAND gate with the inputs (AbarB)bar and (ABbar)bar.  Realizing that these two inputs look alot like outputs from NAND gates in parallel, we have two more NAND gates in the solution.  Factoring the two equations using the logic in (3) results in the equations ( A(Abar + Bbar) )bar and ( B(Abar + Bbar) )bar Since Abar + Bbar = A nand B (from 2) we have our final NAND gate. Conversely, A nand B = Abar + Bbar A nand (Abar + Bbar) = (A(Abar + Bbar))bar = (ABbar)bar = Abar + B B nand (Abar + Bbar) = (B(Abar + Bbar))bar = (AbarB)bar = A + Bbar (Abar + B) nand (A + Bbar) = ((Abar + B)(A + Bbar))bar = (Abar + B)bar + (A + Bbar)bar = ABbar + AbarB QED Devlin Tuesday, March 05, 2002   Fog Creek Home