223
правки
Изменения
Нет описания правки
{{В разработке}}
Пусть задана булева функция <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>. Любая булева функция представима в виде [[Полином_Жегалкина|полинома Жегалкина]], притом единственным образом. Пусть <tex> i = (i _{1}, i _{2}, .. i _{n}), \;\; i _{k} = \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i _{k}} \sim \left\{\begin{matrix} x, \;\; i _{k}=1
\\ 1, \;\; i _{k}=0
\end{matrix}\right. </tex>/ Тогда [[Полином_Жегалкина|полином Жегалкина]] можно записать как: <tex> f(x) = \bigoplus\limits_{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}}</tex>, где <tex>\alpha _{i} \in \{ 0; 1 \}</tex>.
{{Теорема |statement=Тогда отображение <tex>f\rightarrow \alpha _{i} </tex> (то есть такое, которое по заданной функции определяет ее коэффициенты при членах [[Полином_Жегалкина|полинома Жегалкина]]) является: <tex>\alpha _{i} = \bigoplus \limits_{j\preceq i} f(j)</tex>.||proof=Докажем с помощью индукции по количеству единичек в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_{1}+x_{2}+...+x_{n}</tex> ). <br/>1) База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha _{0} </tex><br/>2) Пускай теорема справедлива для всех сумм <tex>x_{1}+x_{2}+...+x_{n} < k</tex>. Покажем, что в таком случае она верна и для <tex>x_{1}+x_{2}+...+x_{n} = k</tex>. По определению <tex> f </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus\limits_{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}} = </tex>
}}
Такое отображение также называется '''преобразованием Мёбиуса'''.
----
