this is for holding javascript data
Michela Ceria edited section_Vectorial_Boolean_functions__.tex
about 6 years ago
Commit id: 3b6a069c4b81b1edff7604242a08634e82d9692e
deletions | additions
diff --git a/section_Vectorial_Boolean_functions__.tex b/section_Vectorial_Boolean_functions__.tex
index 4bf000b..77b75fd 100644
--- a/section_Vectorial_Boolean_functions__.tex
+++ b/section_Vectorial_Boolean_functions__.tex
...
\section{Vectorial Boolean functions}
\begin{Definition}\label{VectBool}
A vectorial Boolean function is a function
$$F:(\Fb)^n\rightarrow (\Fb)^m,$$
with $m,n \in \NN$.
\end{Definition}
We can represent a vectorial Boolean function as a vector of Boolean functions:
$$F:(\Fb)^n\Rightarrow (\Fb)^m,$$
$$(x_1,...,x_n)\mapsto \begin{matrix} F1(x_1,...,x_n)\\ \vdots \\ Fm(x_1,...,x_n) \end{matrix},$$
\begin{Example}\label{ExVectBool}
The function $F:(\Fb)^3\rightarrow (\Fb)^2,$
given by $(x,y,z)\mapsto (xy+y, y+z)$
is a vectorial Boolean function.
\end{Example}
We notice that every component of a vectorial Boolean function is a Boolean function, so each component can be represented in its absolute normal form.
\begin{Corollary}\label{VectANF}
Let $$F:(\Fb)^n\rightarrow (\Fb)^m, n,m \in |NN$$ be a vectorial Boolean function. Then
$F=\begin{matrix} F1(x_1,...,x_n)\\ \vdots \\ Fm(x_1,...,x_n) \end{matrix},$ with
$$F_i =\sum_{S \subset \{1,...,n\}} a_S^{(i)}x_S^{(i)},$$
where $a_S^{(i)} \in \Fb$ and $x_S^{(i)}=\prod_{j \in S} x_j$ for every $j \in \{1,...,m\}$.
\end{Corollary}
Since the size of the set of all functions from a set $A$ to a set $B$ i.e. $\mathfrak{F}=\{f:B\rightarrow B\}$ is $\vert \mathfrak{F} \vert = \vert B\vert ^{\vert AQ\vert }$, then the number of all vectorial Boolean functions from $(\Fb)^n$ to $(\Fb)^m$ is
$(2^m)^{2^n}=2^{m2^n}$. We observe that the same number comes from counting all vectors of length $m$ with components which are Boolean functions in $x_1,...,x_n$.
A special case of Boolean functions arise when $m=n$, i.e. the domain and the codomain of the function coincide:
$$F:(\Fb)^n\rightarrow (\Fb)^n, n\in \NN$$
Some of these could be permutations (i.e. bijections). Since a vectorial Boolean function is a
function between two finite sets, then it is a invertible if and only if it is
injective or surjective.
\begin{Theorem}\label{DegVectBoolFunct}
Let $n\in \NN$. If $F:(\Fb)^n\rightarrow (\Fb)^n$ is a permutation, then
$$\deg(F_i)\leq n-1,\, \forall i \in \{1,...,n\}.$$
\end{Theorem}