Michela Ceria edited bits4.tex  about 6 years ago

Commit id: 00bc36215a7713e278552f0cdd2088e9465a6cb8

deletions | additions      

       

Any Boolean function   $$f: (\Fb)^n \rightarrow (\Fb)$$  with $n\in \NN$, can be written as a polynomial in $\Fb[x1,..,x_n]$. More precisely, $f$ can be written as a sum of all the \emph{squarefree monomials} of degree from $0$ to $n$ (with coefficients in $\Fb$), i.e.  $$f(x_1,...,x_n)=a_0+a_1x_1+...+a_n x_n+a_{n+1}x_1x_2+...+a_dx_1x_2...x_n \,,$$ \, ,$$  where $a_0,\ldots,a_n \in \Fb .$$  \end{Theorem}