XOR using NAND Ah.  Back to Intro to Computer Engineering. 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   Fog Creek Home