Michela Ceria edited bits4.tex  about 6 years ago

Commit id: fca67584c5d910a39443fc98c45f702cf4fe184a

deletions | additions      

       

\end{Exercise}  \begin{Example}\label{Prodotto1}  We are interested in a function $f$  that returns $1$ if a vector of bits is null, $0$ otherwise. This is a useful Boolean function, since it recognizes whether a vector of bits is the null vector $(0,\ldots,0)$. \\  We now show how to obtain a polynomial representing this function. We observed in Exercise \ref{XorIsNice} that the multiplication of bits has the same truth table of the $\AND$ operator. In particular we have $1$ if each bit is $1$, $0$ otherwise. This is the opposite of what we want and so we can add $1$ to have the sought-after function (see Exercise \ref{Not}). For example, if $n=3$ the function in $\Fb[x,y,z]$ is $$(x,y,z) \mapsto xyz+1.$$ becomes  $$  f:(\Fb)^3 \rightarrow \Fb, \quad (\overline{x},\overline{y},\overline{z})\mapsto \overline{x}\overline{y}\overline{z}+1,  $$  $$f \in \Fb[x,y,z],\qquad f=xyz+1.$$  \end{Example}