Fog Creek Software
Discussion Board




XOR gate using NANDS

It's fairly simple. For reference the truthtables are provided here:
XOR:

A | B | O
-----------
T | T | F
F | T | T
T | F | T
F | F | F

NAND

A | B | O
-----------
T | T | F
F | T | T
T | F | T
F | F | T

The gate is pretty simple. You'll need 5 NAND gates. A NAND A is always NOT A (this is the first and the last entry in the truth table).

In the diagram below |)o is a NAND gate.

A -- -
      |)o------
A -- -          |--
B---------------|)o------
                                |--
                                  |)o------ (OUT)
                                |--
A---------------|)o------
B -- -          |--
      |)o------
B -- -

Basically you get:
((NOT A) NAND B) NAND ((NOT B) NAND A)

The logic is straightforward. If you get A and B being of the same kind you will always end up with both (T) on the middle gates. Since A and B are the same and middle gates are essentialy showing (NOT(X) NAND X) which is always true (middle two entries in the NAND table). If you NAND two Truths you will end up with a False on the output.

So we have satisfied the top and bottom entries in the XOR truth table.

The middle entries work similiary. If they are different you will end up with either Truth at the top middle gate and False at the bottom middle gate or the otherway around. If you do T NAND F you always get T. Therefore the middle two entries of the XOR table are satisfied.

Thus we have our gate

Arvin Farahmand
Wednesday, June 04, 2003

Nice!

I got a solution in 6 gates by mapping

a^b => (a||b) && !(a&&b)
        => !(!a && !b) && !(a&&b)

Yours is much cleaner.

Mike G.
Friday, June 13, 2003

I tried the puzzle starting first from a logical point then from a graphical point.

The expression:
(a or b) and not (a and b)
yields the same results as an xor.

I also recognized that: nand(a,a) == not(a)
and using DeMorgan's laws, I also knew that:
nand(a,b) == not(a and b) == not(a) or not(b)

I used these to draw a circuit without doing simplification and ended up with 7 nand gates, but the little "not(a)==nand(a,a)" trick bothered me; I figured a simpler solution must exist...

I looked again, and thought with the inputs, there must be a nand using them, then I tried nanding the ouput with each of the two inputs yielding two values that I then nanded back together.  The resulting circuit has only 4 NAND's, which I thought was cool.

So, I plugged the truth table into it, and got the XOR results.  I'm not certain but fairly willing to bet that it cannot be done with fewer than 4 NAND gates.

The resulting expression looks like this:
NAND(NAND(A,NAND(A,B)),NAND(B,NAND(A,B)))

5 NANDs right? The circuit can reuse the NAND(A,B) expression by drawing it as a fork.  An interesting challenge is to prove symbolically that the the expression is the same as the first expression that I gave using ANDs, ORs, and NOTs.

Les Ramer
Monday, July 07, 2003

You guys are on crack.  It can be done in four:

N1 = a nand b
N2 = a nand N1
N3 = b nand N1
N4 = N2 nand N3.

(no ... I didn't figure this one out ... I just remembered it from back in college).

Alyosha`
Friday, July 11, 2003

*  Recent Topics

*  Fog Creek Home