Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form). Modulo 2, AND is multiplication and XO

Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form). Modulo 2, AND is multiplication and XOR is addition. We also have the useful properties 1+1=0, x+x=0, and x^2 = x. Thus: NAND(0, 0) = 0*0 + 1 = 1 NAND(x, y) = x*y + 1 AND(x, y) = NAND(NAND(x, y), NAND(x, y)) = (x*y + 1)*(x*y + 1) + 1 = x*y + x*y + x*y + 1 + 1 = x*y XOR(x, y) = NAND(NAND(x, NAND(x, y)), NAND(y, NAND(x, y))) = (x * (x*y + 1) + 1) * (y * (x*y + 1) + 1) + 1 = (x*y + x + 1) * (x*y + y + 1) + 1 = x*y + x*y + x*y + x*y + x*y + x + x*y + y + 1 + 1 = x + y Since both AND and XOR can be obtained from NAND, any polynomial can be constructed. It also becomes obvious that you can't get x*y from x+y and vice-versa, so neither XOR nor AND can be universal gates on their own. NOR's algebraic form is x*y + x + y + 1, from which you can similarly derive AND and XOR. XNOR is x + y + 1, from which AND cannot be obtained.