# Converting Boolean expressions to polynomials

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)$.

• If I understand your question correctly, all you need to do is "code" and, or and not into polynomials. Then more complex Boolean expression could be expressed as compositions of these operations. Do you think you could find a way to code and and not into polynomials? – Matija Sreckovic Apr 20 '17 at 22:30

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$.

• Ah of course! Thanks! – TorsionSquid Apr 21 '17 at 0:10

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}).$$

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.

• $OR$ is $x_1+x_2+x_1x_2$? – XL _At_Here_There Nov 3 '17 at 5:16