…in the integers mod 2 (a.k.a. the finite field of order 2). Multiplication mod 2 is AND:
| A | B | (AB) | A B AND |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Adding one mod 2 is NOT:
| A | (A+1) | A NOT |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 0 |
So, multiplication plus one is NAND:
| A | B | (AB+1) | A B NAND |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Since NAND is universal, and any finite composition of polynomials is a polynomial, any finite boolean circuit is a polynomial. Here’s all 16 two-input functions:
| Lookup table | Boolean function (RPN) | Polynomial | Polynomial bitmap |
|---|---|---|---|
| 0000 | 0 | 0 | 0000 |
| 0001 | A B AND |
AB | 0001 |
| 0010 | A (B NOT) AND |
AB+A | 0101 |
| 0011 | A | A | 0100 |
| 0100 | (A NOT) B AND |
AB+B | 0011 |
| 0101 | B | B | 0010 |
| 0110 | A B XOR |
A+B | 0110 |
| 0111 | A B OR |
AB+A+B | 0111 |
| 1000 | A B OR NOT |
AB+A+B+1 | 1111 |
| 1001 | A B XOR NOT |
A+B+1 | 1110 |
| 1010 | B NOT |
B+1 | 1010 |
| 1011 | A (B NOT) OR |
AB+B+1 | 1011 |
| 1100 | A NOT |
A+1 | 1100 |
| 1101 | (A NOT) B OR |
AB+A+1 | 1101 |
| 1110 | A B AND NOT |
AB+1 | 1001 |
| 1111 | 1 | 1 | 1000 |
It’s interesting that in many cases, including those corresponding to the “basic” functions of AND, OR, XOR and NOT, the polynomial bitmap is identical to the lookup table.
It’s also interesting that these polynomials are either multilinear (linear in each variable) or the sum of a multilinear polynomial with 1.
Naturally, I’m not the first person to notice this. It was first noticed by I. I. Zhegalkin in 1927. And I haven’t yet found any especially compelling uses of the representation. (If you actually want to represent boolean functions, you’re probably better served by ZDDs.) But I found it an interesting discovery which might just come in handy someday.