Fog Creek Software
Discussion Board




XOR using NAND

Ah.  Back to Intro to Computer Engineering. <shudder>

given inputs x and y you would

(x NAND (y NAND 1)) NAND (y NAND (x NAND 1)) ~ x XOR y
                    a                                        b
              c                                          d
                                    e

Truth Table to Prove this
        Solution e must match x XOR y

x y  x XOR y    x y a b c d e    i j  i NAND j(for the curious)
---------------  ----------------  --------------
1 1        0      1 1 0 0 1 1 0  1 1    0
1 0        1      1 0 1 0 0 1 1  1 0    1
0 1        1      0 1 0 1 1 0 1  0 1    1
0 0        0      0 0 1 1 1 1 0  0 0    1

How to go about solving this
x XOR y is said (x AND (NOT y)) OR ((NOT x) AND y)

now we need to transform the AND OR and NOT gates into NANDs

AND to NAND is fairly simple need to put a NOT after it this can be shown with another truth table but I'll skip those from here on out i NAND j is NOT(i AND j)

OR to NAND is a little harder have to put NOTs before it
i NAND j is (NOT i) OR (NOT j)

adding in NOTs so we can replace we get
(NOT(NOT(x AND (NOT y)))) OR (NOT (NOT (y AND (NOT x))))
since NOTs cancel each other we have the same equation

rewrite as
(NOT(x NAND (NOT y))) OR (NOT (y NAND (NOT x)))
again as
(x NAND (NOT y)) NAND (y NAND (NOT x)))

now how to do NOT?

i NOT i              i  i NAND 1
1 0                  1    0
0 1                  0    1

and there you have it

(x NAND (y NAND 1)) NAND (y NAND (x NAND 1))

comments: I don't think this would be on an interview unless you're interviewing for a hardware job

Rob Spieldenner
Friday, June 21, 2002

Well besides the fact that the truth tables didn't come out formatted like I expected.

Rob Spieldenner
Friday, June 21, 2002

Truth tables again

x y x XOR y

1 1 0
1 0 1
0 1 1
0 0 0

a = y NAND 1
b = x NAND 1
c = x NAND a
d = y NAND b
e = c NAND d

x y a b c d e

1 1 0 0 1 1 0
1 0 1 0 0 1 1
0 1 0 1 1 0 1
0 0 1 1 1 1 0

Rob Spieldenner
Friday, June 21, 2002

This is actually possible with only 4 Nand gates...

a = x NAND y
b = x NAND a
c = y NAND a
d = b NAND c

xy abcd
00 1110
01 1101
10 1011
11 0110

The trick is to use the output of a twice.  You don't need to ever worry about having a constant 0 or 1 input.

--- Charles

Charles Ofria
Wednesday, July 24, 2002

*  Recent Topics

*  Fog Creek Home