Comment by kragen

for those wondering about the and/xor thing, well, of course a nand b is just 1 xor (a and b), but you can do enormously better than that!

it turns out there's a very pretty formulation of boolean combinational logic (i can't bring myself to say 'circuits') called zhegalkin polynomials, in which arbitrary boolean functions are just polynomials in gf(2). i wrote a simple implementation of them in http://canonical.org/~kragen/sw/dev3/zhegalkin.py.