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

Материал из Викиконспекты
Перейти к: навигация, поиск
(+ Доказательство формулы преобразования. Различные исправления.)
Строка 3: Строка 3:
 
\\ 1, \;\; i _{k}=0
 
\\ 1, \;\; i _{k}=0
 
\end{matrix}\right. </tex>/ &nbsp;&nbsp; Тогда [[Полином_Жегалкина|полином Жегалкина]] можно записать как: <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>.
 
\end{matrix}\right. </tex>/ &nbsp;&nbsp; Тогда [[Полином_Жегалкина|полином Жегалкина]] можно записать как: <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>.
 +
<br/>
 +
Множество коэффициентов <tex>\{\alpha _{i}\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i \in \overline{1..n}</tex>, то есть <tex>\alpha: i \mapsto \alpha_{i}</tex>.
 +
 +
Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_{i} \alpha _{i} \cdot [x _{1} , \; </tex> если <tex> \;\; i _{1}] \cdot [x _{2} , \; </tex> если <tex> \;\; i _{2}] \cdot ... \cdot [x _{n} , \; </tex> если <tex> \;\; i_{n}]</tex>.
 +
 +
Тут запись <tex>[x _{k} , \; </tex> если <tex> \; i _{k}]</tex> означает, что элелемент <tex> x_{k} </tex> присутствует в соответствующем члене полинома только если <tex> i_{k} = 1 </tex>.
 +
Отсюда ясно, что <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} </tex>. &nbsp; <tex> (1) </tex><br/>
 +
Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффциентов).
  
 
{{Теорема  
 
{{Теорема  
|statement=Тогда отображение  <tex>f\rightarrow \alpha _{i} </tex> (то есть такое, которое по заданной функции определяет ее коэффициенты при членах [[Полином_Жегалкина|полинома Жегалкина]]) является: <tex>\alpha _{i} = \bigoplus \limits_{j\preceq  i} f(j)</tex>.
+
|statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_{x} </tex> можно найти по формуле: <tex>\alpha _{x} = \bigoplus \limits_{j\preceq  x} f(j)</tex> &nbsp;&nbsp; <tex> (2) </tex>.
||proof=Докажем с помощью индукции по количеству единичек в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_{1}+x_{2}+...+x_{n}</tex> ). <br/>
+
||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_{1}+x_{2}+...+x_{n}</tex> ) и для удобства обозначим это количество (сумму) <tex> wt(x) </tex>. <br/>
1) База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha _{0} </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>
+
'''2)''' Пускай теорема справедлива для всех сумм <tex>wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>wt(x) = k</tex>. По <tex> (1) </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} = \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ] \oplus \alpha_{x}</tex>
 +
 
 +
Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ]  </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \preceq x </tex>. И для фиксированных <tex> j, x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \prec i \preceq x</tex>. Несложно увидеть, что таких <tex> i </tex> встретится ровно <tex> 2^{wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ] =  \bigoplus \limits_{j\prec  x} f(j) </tex>.
 +
Но тогда <tex> f(x) = \left [ \bigoplus \limits_{j\prec  x} f(j) \right ] \oplus \alpha_{x} \Leftrightarrow f(x) \oplus \bigoplus \limits_{j\prec  x} f(j) = \alpha_{x} \Leftrightarrow \alpha_{x} = \bigoplus \limits_{j\preceq  x} f(j)</tex>. <br/>
 +
То есть при <tex>wt(x) = k</tex> формула также выполняется, значит при любых <tex> x </tex>  выполняется <tex>\alpha _{x} = \bigoplus \limits_{j\preceq  x} f(j)</tex>.
  
 
}}
 
}}
Такое отображение также называется '''преобразованием Мёбиуса'''.
 
----
 
 
<br/>
 
<br/>
Множество коэффициентов <tex>\{\alpha _{i}\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i \in \overline{1..n}</tex>, то есть <tex>\alpha: i \mapsto \alpha_{i}</tex>.
+
Отображение <tex> f \mapsto \alpha</tex> отображение также называется '''преобразованием Мёбиуса'''.
 
 
Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_{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}]</tex>.
 
  
Тут запись <tex>[x _{k} , \; \mbox {if} \; i _{k}]</tex> означает, что элелемент <tex> x_{k} </tex> присутствует в соответствующем члене полинома только если <tex> i_{k} = 1 </tex>.  
+
Видно, что <tex> (1) </tex> и <tex> (2) </tex> это одно и тоже преобразование. Значит, если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть '''преобразование Мёбиуса''' обратно самому себе.
Отсюда ясно, что <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} </tex>.
 
  
Таким образом, если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть '''преобразование Мёбиуса''' обратно самому себе.
+
== Литература ==
 +
* Логачёв О.А, Сальников А.А., Ященко В.В. '''Булевы фунции в теории кодирования и криптологии''' — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.

Версия 21:16, 15 октября 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]\{\alpha _{i}\}[/math] можно рассматривать как функцию [math]\alpha[/math], заданной на множестве индексов [math] i \in \overline{1..n}[/math], то есть [math]\alpha: i \mapsto \alpha_{i}[/math].

Очевидно, функцию [math] f [/math] можно записать и следующим образом: [math] f(x) = \bigoplus \limits_{i} \alpha _{i} \cdot [x _{1} , \; [/math] если [math] \;\; i _{1}] \cdot [x _{2} , \; [/math] если [math] \;\; i _{2}] \cdot ... \cdot [x _{n} , \; [/math] если [math] \;\; i_{n}][/math].

Тут запись [math][x _{k} , \; [/math] если [math] \; i _{k}][/math] означает, что элелемент [math] x_{k} [/math] присутствует в соответствующем члене полинома только если [math] i_{k} = 1 [/math]. Отсюда ясно, что [math] f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} [/math].   [math] (1) [/math]
Найдем отображение [math] f \mapsto \alpha[/math] (То есть такое, которое по заданной функции вычисляет значения всех коэффциентов).

Теорема:
Пусть задана функция [math] f [/math]. Тогда функцию [math] \alpha_{x} [/math] можно найти по формуле: [math]\alpha _{x} = \bigoplus \limits_{j\preceq x} f(j)[/math]    [math] (2) [/math].
Доказательство:
[math]\triangleright[/math]

Докажем при помощи индукции по количеству единиц в векторе [math] x [/math] ( иначе говоря, по сумме [math]x_{1}+x_{2}+...+x_{n}[/math] ) и для удобства обозначим это количество (сумму) [math] wt(x) [/math].
1) База: если [math] x = 0 [/math], то, очевидно [math] f(0) = \alpha _{0} [/math]
2) Пускай теорема справедлива для всех сумм [math]wt(x) \lt k[/math]. Покажем, что в таком случае она верна и для [math]wt(x) = k[/math]. По [math] (1) [/math], а далее по предположению индукции видим: [math] f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} = \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] \oplus \alpha_{x}[/math]

Рассмотрим сумму [math] \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] [/math]. Каждый элемент [math] f(j) [/math] содержится в ней, только если [math] j \preceq x [/math]. И для фиксированных [math] j, x [/math] элемент [math] f(j)[/math] встречается ровно столько раз, сколько существует [math] i [/math] , таких, что [math] j \prec i \preceq x[/math]. Несложно увидеть, что таких [math] i [/math] встретится ровно [math] 2^{wt(x)-wt(j)}-1 [/math], то есть нечетное количество раз. Тогда [math] \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] = \bigoplus \limits_{j\prec x} f(j) [/math]. Но тогда [math] f(x) = \left [ \bigoplus \limits_{j\prec x} f(j) \right ] \oplus \alpha_{x} \Leftrightarrow f(x) \oplus \bigoplus \limits_{j\prec x} f(j) = \alpha_{x} \Leftrightarrow \alpha_{x} = \bigoplus \limits_{j\preceq x} f(j)[/math].

То есть при [math]wt(x) = k[/math] формула также выполняется, значит при любых [math] x [/math] выполняется [math]\alpha _{x} = \bigoplus \limits_{j\preceq x} f(j)[/math].
[math]\triangleleft[/math]


Отображение [math] f \mapsto \alpha[/math] отображение также называется преобразованием Мёбиуса.

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

Литература

  • Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.