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 1, 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 1, 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 5, 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 5, 2002
Recent Topics
Fog Creek Home
