Polynomial decomposition of Boolean functions by images of homogeneous operators of nondegenerate functions (Q677739): Difference between revisions

A function \(f:\{0,1\}^n\to\{0,1\}\) is said to be degenerate if \(\sum f(\alpha)=0\), where \(\alpha\) runs over \(\{0,1\}^n\) and \(\sum\) denotes the Boolean-ring sum. For each \(i\in\{1,\dots,n\}\), the operators \(p_i\) and \(d_i\) are defined by \[ \begin{aligned} p_if(x_1,\dots,x_n) & = f(x_1,\dots,\overline x_i,\dots, x_n)\qquad\text{and}\\ d_if(x_1,\dots,x_n) & = f(x_1,\dots,x_n)+ f(x_1,\dots,\overline x_i,\dots, x_n),\end{aligned} \] respectively. By a homogeneous operator is meant any composition \(t= t_n\cdots t_1\), where each \(t_i\in\{p_i,d_i,\text{identity}\}\). The authors prove that every Boolean function has a decomposition of the form indicated in the title. The exact result is too technical to be reproduced here. Reviewer's remark. The only non-Russian literature quoted by the authors consists of the well-known papers by Muller and Reed published in 1954.