Giancarlo Rinaldo edited bits4.tex  about 8 years ago

Commit id: 5929513d0eb030a3b2bb6861cbb49e3d8c2b7a21

deletions | additions      

       

\end{Example}  \begin{Example} In \ref{XorIsNice} we observed that the operator $\OR$ is neither the summand in $\Fb$ (that is $\Xor$) nor the multiplication in $\Fb$ ($\And$). We would like to define a boolean function $or(x,y)$.  We recall the famous De Morgan's laws: Morgan law:  \[  \Not(x\And \Not(x \Or  y)=\Not x \Or \And  \Not y \]  From this follows our function  \[  or(x, y)=\Not(\Not x \And \Not y).  \]  Translating in polynomials with coefficients in $\Fb$ we have the   \[  or(x,y)=(x+1)\times(y+1)+1.  \]  That is after simplifications  \[  or(x,y)=xy+x+y.  \]  An extremely useful boolean function, is the one that recognize if a vector of bits is the null vectors, that is $(0,\ldots,0)$. This function returns $1$ if the vector is null, $0$ otherwise. We observed (see \ref{XorIsNice}) that the multiplications of bits has the same truth table of the $\AND$ operator. So we have $1$ if each bit is $1$, $0$ otherwise. That is the opposite that we want. Adding $1$ we have the function (see \ref{Not}). If $n=3$ we have where $z(x,y,z)=xyz+1$.  \end{Example} 

Let $f:(\Fb)^3 \rightarrow \Fb$ be a polynomial function such that   $f(x,y,z)=xy+yz$.  \\