Fog Creek Software
Discussion Board




XOR using NAND gates

XOR(i, j) = NAND(x, y) where

k = NAND(i, j), x = NAND(i, k), y = NAND(j, k).

proof below:

(i, j)    XOR(i,j)      k      x      y    NAND(x, y)
1, 0    1     1      0      1    1
0, 1    1     1      1      0    1
1, 1    0     0      1      1    0
0, 0    0     1      1      1    0

Raj
Wednesday, May 04, 2005

Sorry about the alignment of the values above.....

Raj
Wednesday, May 04, 2005

NAND(NAND(a,NAND(b,b)),NAND(b,NAND(a,a)))

Note that NAND(a,a) = NOT(a)

a b NAND(a,NAND(b,b)) NAND(b,NAND(a,a))  Full
0 0      1                            1                          0
0 1      1                            0                          1
1 0      0                            1                          1
1 1      1                            1                          0

Anonymous
Friday, May 06, 2005

Let X = NAND(A, B)
Then,
XOR(A, B) = NAND(NAND(X, A), NAND(X, B))

Chaitanya Atreya
Saturday, May 28, 2005

*  Recent Topics

*  Fog Creek Home