Fog Creek Software
Discussion Board

XOR using NAND gates

Create an XOR gate using only NAND gates.  (BTW, mostly all circuit problems assume you have two inputs plus 0 and 1 also as inputs).

* * *

Don't know if somebody has posted the answer yet, but it's not on the question page.

a XOR b
== (a AND NOT b) OR (b AND NOT a)
(Definition of XOR)

== (a NAND NOT b) NAND (b NAND NOT a)
(By De Morgan's Law)

== (a NAND (b NAND b)) NAND (b NAND (a NAND a))
(NOT x is equivalent to x NAND x)

I guess this is the simplest solution with 5 NAND gates.

Friday, February 7, 2003

Here's my solution:

[((a NAND b) NAND a) NAND ((a NAND b) NAND b)]

As you can see, you can share the a NAND b.  So, you only need 4 NAND gates.  Sorry, but I don't have a derivation, but this can easily be proved using truth tables.  This solution came naturally to me!  I just wanted to convert the truth table for a NAND to the XOR and noticed that there is only one difference (0,0 case).

Monday, March 3, 2003

*  Recent Topics

*  Fog Creek Home