Content deleted Content added
→Standard Boolean ___domain: General formula |
→Real polynomial form: headings |
||
Line 88:
== Real polynomial form ==
===
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]]).
Line 98:
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|parity functions]]. The polynomial form of a Boolean function can also be used as its natural extension to [[fuzzy logic]].
===
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|monomials]] (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).
| |||