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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
\\ 1, \;\; i _{k}=0
 
\\ 1, \;\; i _{k}=0
 
\end{matrix}\right. </tex> &nbsp;&nbsp; Тогда полином Жегалкина можно записать как:
 
\end{matrix}\right. </tex> &nbsp;&nbsp; Тогда полином Жегалкина можно записать как:
:<math> f(x) = \bigoplus _{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}}</math>,
+
:<math> f(x) = \bigoplus\limits_{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}}</math>,
 
:где  <tex>\alpha _{i} \in  \{ 0; 1 \}</tex>
 
:где  <tex>\alpha _{i} \in  \{ 0; 1 \}</tex>
  

Версия 00:39, 9 октября 2010

Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}[/math]. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом. Пусть [math] i = (i _{1}, i _{2}, .. i _{n}), \;\; i _{k} = \{0 ; 1\}[/math], и введем обозначение [math] x ^{i _{k}} \sim \left\{\begin{matrix} x, \;\; i _{k}=1 \\ 1, \;\; i _{k}=0 \end{matrix}\right. [/math]    Тогда полином Жегалкина можно записать как:

[math] f(x) = \bigoplus\limits_{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}}[/math],
где [math]\alpha _{i} \in \{ 0; 1 \}[/math]

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

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

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



Очевидно, функцию [math] f [/math] можно записать и следующим образом:

[math] f(x) = \bigoplus _{i} \alpha _{i} \cdot [x _{1} , \; \text {if} \;\; i _{1}] \cdot [x _{2} , \; \text {if} \;\; i _{2}] \cdot ... \cdot [x _{n} , \; \text {if} \;\; i_{n}][/math]

Запись [math][x _{k} , \; \text {if} \; i _{k}][/math] означает, что элелемент [math] x_{k} [/math] присутствует в соответствующем члене полинома только если [math] i_{k} = 1 [/math]. Отсюда ясно, что

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

Таким образом, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию [math]f[/math]. То есть преобразование Мёбиуса обратно самому себе.