Closed-form expression for this Boolean polynomial?

82 Views Asked by At

If we represent T with -1 and F with 1, the polynomial corresponding to the Boolean AND function $x_1 \land x_2$ is:

$p(x_1, x_2) = \dfrac{1}{2} \left( x_1 + x_2 - x_1 x_2 + 1 \right)$

We can verify by checking that $p(-1, -1) = -1$, while $p(-1, 1) = p(1, -1) = p(1, 1) = 1$.

Similarly, the polynomial for the AND function over three variables $x_1 \land x_2 \land x_3$ is:

$p(x_1, x_2, x_3) = \dfrac{1}{4} \left( x_1 + x_2 + x_3 - x_1 x_2 - x_1 x_3 - x_2 x_3 + x_1 x_2 x_3 + 3 \right)$

And for four variables $x_1 \land x_2 \land x_3 \land x_4$, we have:

$p(x_1, x_2, x_3, x_3) = \dfrac{1}{8} \left( x_1 + x_2 + x_3 + x_4 - x_1 x_2 - x_1 x_3 - x_1 x_4 - x_2 x_3 - x_2 x_4 - x_3 x_4 + x_2 x_3 x_4 + x_1 x_3 x_4 + x_1 x_2 x_4 + x_1 x_2 x_3 - x_1 x_2 x_3 x_4 + 7 \right)$

How can we express this pattern as a closed form? I have the basic framework

$p(x_1, \cdots, x_n) = \dfrac{1}{2^{n-1}} \left( \sum_{i=1}^n x_i + \cdots + 2^{n-1} - 1 \right)$

but am unsure what to put in the middle in order to capture the changes of sign and the increasing number of variables.

1

There are 1 best solutions below

3
On BEST ANSWER

We can use the fact that, if we represent the booleans as elements of $\{0,1\}$ instead of $\{-1,1\}$ (with TRUE=$0$ and FALSE=$1$), and is equivalent to simple multiplication. Using the map $f(x)=\frac{1-x}{2}$ sending $-1\to 1$ and $1\to 0$, we may write \begin{align}\text{AND}(x_1,x_2,\dots,x_n) &=f^{-1}\big(f(x_1)f(x_2)\cdots f(x_n)\big)\\ &=f^{-1}\left(\prod_{i=1}^n \frac{1-x_i}{2}\right)\\ &=1-2\prod_{i=1}^n \frac{1-x_i}{2}. \end{align} You can write this in many different forms.