Fog Creek Software
Discussion Board




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

*  Recent Topics

*  Fog Creek Home