Converting Boolean expressions to polynomials

Question

Is there a simple way to convert a general Boolean expression composed of variables $x_1,\cdots,x_n)$; ands; ors; and nots to a polynomial in $p\in\mathbb{F}_2[x_1,\cdots,x_n]$ in such a way that the truth table is preserved? For example, we could identify "$x_1\text{or } x_2$" with $1-(1-x_1)(1-x_2)$.

Answer 1

It seems to me you did all the hard work by coming up with an expression for the $\lor$. Because $\neg x$ is simply $1-x$, and $x \land y$ is $xy$.

Answer 2

As you said, or can be coded as $D(x_{1}, x_{2}) = 1-(1-x_{1})(1-x_{2})$, and it can be easily shown that and can be coded as $C(x_{1}, x_{2})=x_{1}x_{2}$, and not can be coded as $N(x_{1})=1-x_{1}$. Complex expressions are, as I said, compositions of these operations.

For example, consider $$P(x_{1}, x_{2}, x_{3}) = \neg(x_{1} \land x_{3}) \lor(x_{2}\land x_{3}).$$

We can code it using $C, D$ and $N$ as $$ 1-(1-(1-x_{1}x_{3}))(1-x_{2}x_{3})=1-x_{1}x_{3}(1-x_{2}x_{3}).$$

Answer 3

If you perform the arithmetic in the two element field GF(2) then XOR is addition, AND is multiplication, NOT is still $1-x$, and OR can be defined as $x_1 + x_2 + x_1x_2$.

I lifted this almost verbatim from Wikipedia article on boolean algebra. Also see Zhegalkin polynomial. And googling for "boolean polynomial" produces a lot of relevant hits.

In fact a number of common computing tasks are defined based on boolean polynomials, CRCs and linear feedback shift register to name a couple.