XOR using NAND gates I solved it using 6 NAND gates (might be possible with less). XOR: 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0 NAND: 0 0 - 1 0 1 - 1 1 0 - 1 1 1 - 0 Difficult to describe in text but i'll try. Call the two inputs A and B. Connect A to a 1 and call this gate (A1). Same with (B1). The third nand is with A and B, lets call it (AB). Connect (A1) and (B1) and call it ((A1)(B1)). Connecting this to (AB) will give us (((A1)(B1))(AB)). (((A1)(B1))(AB)): 0 0 - 1 0 1 - 0 1 0 - 0 1 1 - 1 Which is the inverse of XOR. This is fixed by using a 6th nand and connecting it to (((A1)(B1))(AB)) and 1. ((((A1)(B1))(AB))1) Fredrik Olsson Monday, January 3, 2005 I've seen it before, so I won't give it away.  But a hint:  It can be done with four. Keith Neufeld Monday, January 3, 2005 Yes 4 gates, and you don't need any constant inputs Hint:  not(AB) = not(A) + not(B) Cheers. Will Smith Thursday, January 6, 2005 Ah, finally solved it. The solution is very symmetrical and pretty. I guess my hint will be: Remember that you can use the output from one gate as input to two different gates. Fredrik Olsson Friday, January 7, 2005 I managed to get it in 5 nand gates and it took a while to whittle it down to 4 nand gates. The solution is very pretty. Another hint: not(A) or B = not(A) or (A and B) the LHS gives a 5 nand gate solution, but the RHS allows a 4 nand gate solution. WanFactory Monday, March 21, 2005   Fog Creek Home