Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина

Эта статья находится в разработке!

Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}[/math]. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом. То есть

[math]f(x_{1},x_{2},...x_{n}) = \bigoplus _{1\leq k \leq n} \left [\bigoplus _{1\leq i_{1}\lt i_{2}\lt ..\lt i_{k} \leq n} \alpha _{i_{1}i_{2},..i_{k}}x_{i_{1}}x_{i_{2}}...x_{i_{k}} \right ],[/math]

где [math]\alpha _{i} \in \{ 0; 1 \} [/math] ([math]i[/math] - вектор из [math]i_{1}, i_{2},.. i_{n}[/math]).

Отображение [math]f\rightarrow \alpha _{i} [/math] (то есть такое, которое по заданной функции определяет ее коэффициенты при членах полинома Жегалкина) :

[math]\alpha _{i} = \bigoplus _{j\preceq i} f(j)[/math]

Такое отображение также называется преобразованием Мёбиуса.