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
Recent Topics
Fog Creek Home
