Editing Boolean function (section)

== Real polynomial form ==
=== On the unit hypercube ===
Any Boolean function <math>f(x): \{0,1\}^n \rightarrow \{0,1\}</math> can be uniquely extended (interpolated) to the [[Real number|real domain]] by a [[multilinear polynomial]] in <math>\mathbb{R}^n</math>, constructed by summing the truth table values multiplied by [[Lagrange polynomial|indicator polynomials]]:<math display="block">f^*(x) = \sum_{a \in {\{0,1\}}^n} f(a) \prod_{i:a_i=1} x_i \prod_{i:a_i=0} (1-x_i)</math>For example, the extension of the binary XOR function <math>x \oplus y</math> is<math display="block">0(1-x)(1-y) + 1x(1-y) + 1(1-x)y + 0xy</math>which equals<math display="block">x + y -2xy</math>Some other examples are negation (<math>1-x</math>), AND (<math>xy</math>) and OR (<math>x + y - xy</math>). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated [[Modular arithmetic|modulo 2]] one obtains the [[algebraic normal form]] ([[Zhegalkin polynomial]]).

Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative:<math display="block">\begin{array}{lcl} f^*(00) & = & (f^*)(00) & = & f(00) \\ 
f^*(01) & = & (\partial_1f^*)(00) & = & -f(00) + f(01) \\
f^*(10) & = & (\partial_2f^*)(00) & = & -f(00) + f(10) \\
f^*(11) & = & (\partial_1\partial_2f^*)(00) & = & f(00) -f(01)-f(10)+f(11) \\
\end{array}</math>this generalizes as the [[Möbius transform|Möbius inversion]] of the [[partially ordered set]] of bit vectors:<math display="block">f^*(m) = \sum_{a \subseteq m} (-1)^{|a|+|m|} f(a)</math>where <math>|a|</math> denotes the weight of the bit vector <math>a</math>. Taken modulo 2, this is the [[Zhegalkin polynomial|Boolean ''Möbius transform'']], giving the [[algebraic normal form]] coefficients:<math display="block">\hat f(m) = \bigoplus_{a \subseteq m} f(a)</math>In both cases, the sum is taken over all bit-vectors ''a'' covered by ''m'', i.e. the "one" bits of ''a'' form a subset of the one bits of ''m''.

When the domain is restricted to the n-dimensional [[hypercube]] <math>[0,1]^n</math>, the polynomial <math>f^*(x): [0,1]^n \rightarrow [0,1]</math> gives the probability of a positive outcome when the Boolean function ''f'' is applied to ''n'' independent random ([[Bernoulli distribution|Bernoulli]]) variables, with individual probabilities ''x''. A special case of this fact is the [[piling-up lemma]] for [[parity function]]s. The polynomial form of a Boolean function can also be used as its natural extension to [[fuzzy logic]].

=== On the symmetric hypercube ===
Often, the Boolean domain is taken as <math>\{-1, 1\}</math>, with false ("0") mapping to 1 and true ("1") to −1 (see [[Analysis of Boolean functions]]). The polynomial corresponding to <math>g(x): \{-1,1\}^n \rightarrow \{-1,1\}</math> is then given by:<math display="block">g^*(x) = \sum_{a \in {\{-1,1\}}^n} g(a) \prod_{i:a_i=-1} \frac{1-x_i}{2} \prod_{i:a_i=1} \frac{1+x_i}{2}</math>Using the symmetric Boolean domain simplifies certain aspects of the [[Analysis of Boolean functions|analysis]], since negation corresponds to multiplying by −1 and [[Parity function|linear functions]] are [[monomial]]s (XOR is multiplication). This polynomial form thus corresponds to the ''Walsh transform'' (in this context also known as ''Fourier transform'') of the function (see above). The polynomial also has the same statistical interpretation as the one in the standard Boolean domain, except that it now deals with the expected values <math>E(X) = P(X=1) - P(X=-1) \in [-1, 1]</math> (see [[piling-up lemma]] for an example).