XOR using NAND (solution)

Assuming that a and b are booleans (truth values)

By definition
 
    XOR(a,b) = (~a & b) | (a & ~b)

Two formulas are needed from elementary logic

    [1]    ~a = ~( a & a)    ( NOT(a) = NAND(a,a)  )

    [2]    a | b = ~ ( ~a & ~b)

So,
 
  XOR(a,b)

      =  (~a & b) | (a & ~b)                                                              (by definition)
      =  ~ ( ~(~a & b)  &  ~(a & ~b) )                                            (by [2])
      =  ~ (  NAND(NOT(a),b)  & NAND(a, NOT(b))                      (by [1])
      =  NAND(  NAND(NAND(a,a),b) ,  NAND(a,NAND(b,b))  )  (by [1])
   

   

Bill Stratford
Wednesday, October 01, 2003

XOR(x,y)

=

( (x NAND (y NAND 1))

NAND

((x NAND 1) NAND y) )


(5 NAND gates in all)

Soham Mehta
Monday, October 20, 2003

XOR(x,y) = NAND(NAND(NAND(x,y),x), NAND(NAND(x,y),y))

4 NAND gates required. Result of NAND(x,y) can be reused.

Anonymous
Thursday, October 30, 2003

  Recent Topics

  Fog Creek Home