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

Материал из Викиконспекты
Перейти к: навигация, поиск
(final)
Строка 1: Строка 1:
{{В разработке}}
 
 
Пусть задана булева функция <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.   
 
Пусть задана булева функция <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.   
 
То есть
 
То есть
Строка 21: Строка 20:
 
Отсюда ясно, что
 
Отсюда ясно, что
 
   
 
   
: <math> f(x) = \bigoplus _{m(i) \leq i} \alpha _{i} </math>.
+
: <math> f(x) = \bigoplus _{m(i) \leq x} \alpha _{i} </math>.
  
Таким образом видно, что, если применить '''преобразование Мёбиуса''' к функции дважды, то вновь получим исходную функцию. То есть '''преобразование Мёбиуса''' обратно самому себе.
+
Таким образом, если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть '''преобразование Мёбиуса''' обратно самому себе.

Версия 21:06, 5 октября 2010

Пусть задана булева функция [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_{k}[/math]).


Пусть [math] m(i) = (m _{1}, m _{2}, .. m _{n}), \;\;[/math] где для всех индексов [math]t=i _{k}, \;\; m _{t} = 1[/math], а для остальных индексов [math]t \neq i _{k}, \; m _{t} = 0[/math]. Тогда отображение [math]f\rightarrow \alpha _{i} [/math] (то есть такое, которое по заданной функции определяет ее коэффициенты при членах полинома Жегалкина) является:

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

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



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

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

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

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

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