Fog Creek Software
Discussion Board

XOR using NAND gates

We know that xor means

(x' ^ y) v (x ^ y')

So I tried rearranging this equations. Distributing a little, I got.

(x v y) ^ (y' v y) ^ (x' v x) ^ (y' v x')

(y' v y) is always true, as is ('x v x)

So we get

(x v y ) ^ (y' v x')

or, by De Morgans laws

(x' ^ y')' ^ (y ^ x)'

But we must use all nands! We can use this boolean equation

(z' ^ 1)' = z

to get

(((x' ^ y')' ^ (y ^ x)')' ^ 1)'

Ben Brinckerhoff
Monday, October 13, 2003

That does solve the problem, but not optimally.  Only 4 NAND gates are required.  This is a problem from the days of old when NAND gates came 4 to a DIP.

Andrew P. Lentvorski, Jr.
Thursday, December 4, 2003

*  Recent Topics

*  Fog Creek Home