Fog Creek Software
Discussion Board

XOR using NAND gates

The formula for the solution, only using x and y as inputs:

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

In order to solve my problem, first I constructed the simpler AND and OR gates using NAND:

x OR y = (x NAND x) NAND (y NAND y)
x AND y = (x NAND y) NAND (x NAND y)

Since I've never really done this before, the above was just done by playing around.

Second, I looked at the truth tables of x NAND y and x OR y and realized that AND'ing them together would produce an XOR:

x XOR y = (x NAND y) AND (x OR y)

From there it was just substitution to get the answer, which involves 6 NAND gates:

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

The output from f is the solution.

Anthony Mills
Tuesday, February 24, 2004

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

If you actually draw the gates you only need four, x NAND y is used twice.

Friday, February 27, 2004

What about "NAND using XOR gates" ?  Any ideas?

Monday, March 15, 2004

The NAND gate is universal (you can construct every logic gate using only NAND gates), but the XOR gate is not. So you can't construct a NAND gate using XOR gates (otherwise the XOR gate would be universal, which it isn't).

My solution to the problem is much more complicated, unfortunately:


requires 6 NAND gates. But I'm glad that I was able to do it at all.

Friday, April 9, 2004

see it exaplained there

Wednesday, May 5, 2004

*  Recent Topics

*  Fog Creek Home