   XOR gate using NAND gates This question was actually part of an interview I had with Intel slightly over two years ago. It's a fairly straightforward approach using boolean algebra as our guide, mainly making use of the following boolean relations: 1. not(A . B)  = notA + notB, 2. not(notA) = A, and 3. notA . A = 0 We may then begin expanding A xor B: (eq 1)    A xor B = (A . notB) + (notA . B) (eq 2)    A xor B = not(not((A . notB) + (notA . B)) = (eq 3)    not((not (A . notB) . (not(notA . B)))) = (eq 4)    not((notA + B) . (A + notB)) Thus, (eq 4) may be representative of the output of a NAND gate with the two inputs (not A + B) and (A + notB). In order to obtain the two terms in (eq 4) as themselves outputs of NAND gates, we may break down the terms much like the original expression in (eq 1). (eq 5)    notA + B = not (not(notA + B)) = (eq 6)    not(A . notB) and (eq 7)    A + notB = not(not(A + notB)) = (eq 8)    not(notA . B) Where the expressions in (eq 6) and (eq 8) may themselves be outputs of respective NAND gates. That's three NAND gates so far.  Only remaining question is how to obtain the expressions in (eq 6) and (eq 8) without using an inverter or "cheating" by connecting NAND gates as inverters (which would be a rather awkward and non-elegant solution). If we expand the expressions in (eq 6) and (eq 8), we get, respectively (eq 9)    not(A . notB) = not((notA . A) + (A . notB)) = (eq 10)  not(A . (notA + notB)) = (eq 11)  not(A . (not(A . B))) and (eq 12)  not(notA . B) = not((notB . B) + (notA . B)) = (eq 13)  not(B . (notB + notA)) = (eq 14)  not(B . (not(A . B))) As we can see from (eq 11), (eq 6) may be obtained as the output of a nand gate whose inputs are A and not(A . B), the latter itself being the output of a NAND gate whose inputs are A and B. Similarly, from (eq 14), (eq 8) may be obtained as the output of a nand gate whose inputs are B and not(A . B), the latter again the output the NAND gate whose inputs are A and B. Thus, by substituting (eq 11) and (eq 14) into (eq 4), we may obtain: A xor B = not ((not (A . (not (A . B) ) )) . (not (B . (not (A . B) ) )) )           ^^^  ^^^      ^^^                ^^^      ^^^         NAND4  NAND2    NAND1              NAND3    NAND1               That's four NAND gates in all. Tamas Kovacs Monday, July 12, 2004 IMO, using a '1' input isn't cheating, since the problem statement expressly noted its availability. Moreover, what seems academically elegant may or may not be physically elegant when comes time to build something. Aesthetics aside, here's a similar solution using a (hopefully self-explanatory) notation that might be simpler to absorb: A^B = A~B + B~A (by defiinition) A^B = ~~[A~B + B~A ] (double inversion) A^B = ~[~(A~B) ~(B~A) ] (DeMorgan's theorem) This represents a pair of NAND gates driving a NAND gate output. Note: all gates are dual input. It remains to generate ~B and ~A with NAND gates.  We could tie one input 'high' ( ~B = ~(B1) ) or tie both inputs together( ~B = ~(BB) ).  If we tie inputs together to generate ~A and ~B, we get a 5-gate solution: A^B = ~{ ~[A ~(BB)]  ~[B ~(AA)] } where braces and brackets replace some parentheses for clarity.  If minimum gate count is a design goal, then one gate can be eliminated as follows: Consider the '~(A~B)' gate inputs.  When the 'A' input is 0, It doesn't matter what appears at the '~B' input; all we require is for that input resolve to ~B whenever A is 1. Math wise, ~(A~B) = ~(A~B + A~A) (this is the math equivalent of cheating by using a '0' input to a NOR gate) ~(A~B) = ~(A (~B + ~A) ) ~(A~B) = ~(A ~(BA) ) i.e., using ~(BA) instead of ~B  is preserves logical behavior. Likewise, one can use ~(AB) in place of the ~A input to the sibling NAND. Since ~(AB) = ~(BA), one of these NAND gates is redundant and the final equation becomes: A^B = ~{ ~[A ~(AB)] ~[B ~(AB)] } Personally, I find a graphical presentation using gates and bubbles easier to comprehend. :) Chuck Boyer Thursday, August 5, 2004 Actually, in this case the emphasis was not on elegance per se, academic or otherwise, though it was mentioned.  It was on using only NAND gates, and as few NAND gates as possible.  Also note that "cheating" appears in quote marks, thus not to be taken literally. In the end the solutions are the same. I am not very good at ASCII art so I couldn't provide gates and bubbles.  I do have a .pdf file of the diagram available should anyone need it.  Cheers! Tamas Kovacs Thursday, August 19, 2004 I want it plant Marwa Aly Monday, October 11, 2004 Please provide us the logic circuit for implementing XOR gate using NAND and NOR gate. Senthil Murugan Thursday, October 14, 2004 You guys are genius !!! G Thursday, November 4, 2004 Recent Topics Fog Creek Home