this is for holding javascript data
Michela Ceria edited bits4.tex
about 6 years ago
Commit id: 043e89f4f05cce64b25a5fb42bc1c3d7eb386140
deletions | additions
diff --git a/bits4.tex b/bits4.tex
index 98c135a..a09136e 100644
--- a/bits4.tex
+++ b/bits4.tex
...
Indeed, you can check that $f$ and $g$ take the same values in \emph{all}
vectors of $(\Fb)^3$, so
that
$$f
(x, y, z) (\overline{x}, \overline{y}, \overline{z}) =
g(x, y, z), g(\overline{x}, \overline{y}, \overline{z}), \; \forall
(x, y, z) (\overline{x}, \overline{y}, \overline{z}) \in (\Fb)^3.$$
Hence, $f$ and $g$ are \textbf{distinct} as
polynomials, polynomials in $\Fb[x,y,z]$, but they are \textbf{equal} as
boolean functions, since given an input, they return the same output!
\\
\smallskip
The unexpected behaviour of the above functions $f$ and $g$ comes from the fact that
$u^2 = u$ for any $u \in \Fb $.
More generally, Therefore, every polynomial function
from $(\Fb)^3$ to $\Fb$ can be written as a polynomial
$h \in \Fb[x,y,z]$ where
the degree of
every variable is at most one, $0 \leq \deg_x(h),\deg_y(h),\deg_z(h) \leq 1$, for example,
$x^3 y^2 + z^{10} xy^2 = xy + zxy$, when evaluated at $3$-tuples of bits.
\begin{Definition}\label{ANF}
A \emph{squarefree} monomial is a monomial where each variable appears with exponent at most one.