Изменения

Перейти к: навигация, поиск

Полином Жегалкина

5746 байт добавлено, 04:37, 15 октября 2011
Перенёс статью «Преобразование Мёбиуса»
Существует несколько способов построения полинома Жегалкина.
Первый способ — по === По таблице истинности. ===Пусть для функции <tex>f(x_{1},x_{2},..,x_{n})</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты. Можно показать, что за каждую подстановку находим только один коэффициент.
Второй способ — преобразование === Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]]. ===Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.
Третий способ — === Преобразование Мёбиуса ===Пусть задана [[Определение_булевой_функции|булева функция]] <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>.Любая булева функция представима в виде [[Полином_Жегалкина|полинома Жегалкина]], притом единственным образом. Пусть <tex> i = (i _{1}, i _{2}, .. i _{n}), \;\; i _{k} \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i _{k}} \sim \left\{\begin{matrix} x, \;\; i _{k}=1\\ 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>.<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>x</tex>, <tex>i \succ x</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 </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> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>. <br/>'''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha _{0} </tex><br/>'''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/>Отображение <tex> f \rightarrow \alpha</tex> также называется '''преобразованием Мёбиуса'''. Видно, что <tex> (1) </tex> и <tex> (2) </tex> — это одно и тоже преобразование. Значит, если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть '''преобразование Мёбиуса''' обратно самому себе, иными словами, является инволюцией.
== Литература и источники информации ==
* [http://www.stat-mat.com/?p=330 Cтатистика | Математика НГУ]<br>* [http://ru.wikipedia.org/wiki/Полином_Жегалкина Википедия]<br>* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика]<br>* Логачёв О.А, Сальников А.А., Ященко В.В. '''Булевы фунции в теории кодирования и криптологии''' — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.

Навигация