On positive, linear and quadratic Boolean functions

Sergiu Rudeanu

Kragujevac Journal of Mathematics, Tome 36 (2012) no. 2, p. 177

Résumé

In [1], [2] it was proved that a function $f:\{0,1\}^n\longrightarrow\{0,1\}$ is positive if and only if it is increasing, it is linear if and only if it satisfies \begin{equation}abel{(*)} f(X)\+f(Y)=f(XY)\+f(X\+Y) ag{*} \end{equation} and it is quadratic if and only if it satisfies \begin{equation}abel{(**)} f(XY\+XZ\+YZ)eq f(X)\+f(Y)\+f(Z).ag{**} \end{equation} In this paper we work with an arbitrary Boolean algebra $\B$ and with arbitrary Boolean functions $f:\B^n\longrightarrow\B$, that is, algebraic functions over $\B$. We prove a refined generalization of the characterization of positive functions, we prove that a Boolean function satisfies \eqref{(*)} if and only if it is linear in each variable, and we prove that every quadratic Boolean function satisfies \eqref{(**)}. Moreover, a Boolean function $f:{\B}^2\longrightarrow\B$ is linear if and only if it satisfies \eqref{(*)} and a Boolean function $f:\B^3\longrightarrow\B$ is quadratic if and only if it satisfies \eqref{(**)}.

Détail

Classification : Primary06E30
Keywords: Boolean function, positive linear function, linear Boolean function, quadratic Boolean function