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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
−
Пусть задана булевая фунция <math>f</math> от <math>n</math> переменных. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.   
+
Пусть задана булева функция <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.   
 
То есть
 
То есть
 
<br/><br/>
 
<br/><br/>
−
<math>f(x_{1},x_{2},...x_{n}) = \bigoplus _{1\leq k \leq n} \left (\bigoplus _{1\leq i_{1}<i_{2}<..<i_{k} \leq n} \alpha _{i_{1}i_{2},..i_{k}}x_{i_{1}}x_{i_{2}}...x_{i_{k}}  \right )</math>
+
: <math>f(x_{1},x_{2},...x_{n}) = \bigoplus _{1\leq k \leq n} \left [\bigoplus _{1\leq i_{1}<i_{2}<..<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_{1}i_{2}..i_{k} \in  \{ 0; 1 \} } </math>
+
:где  <tex>\alpha _{i} \in  \{ 0; 1 \} </tex>    (<tex>i</tex> - вектор из <tex>i_{1}, i_{2},.. i_{n}</tex>).
 
<br/><br/>
 
<br/><br/>
−
Преобразованием <math>f\rightarrow \alpha _{i} </math> будет являться:
+
Отображение <tex>f\rightarrow \alpha _{i} </tex> (то есть такое, которое по заданной функции определяет ее коэффициенты при членах полинома Жегалкина) :
  
−
<math>\alpha _{i} = \bigoplus _{i\preceq  j} f(j)</math>
+
: <math>\alpha _{i} = \bigoplus _{j\preceq  i} f(j)</math>
  
−
Называемое также преобразованием Мёбиуса.
+
Такое отображение также называется '''преобразованием Мёбиуса'''.

Версия 08:41, 2 октября 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_{n}[/math]).



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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Преобразование_Мёбиуса_для_получения_коэффициентов_полинома_Жегалкина&oldid=3032»