http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Kozhevnikov&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T12:33:13ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%81%D0%B0%D0%B8_%D0%B8_%D0%B4%D1%80.&diff=26427Алгоритм Касаи и др.2012-06-21T20:24:31Z<p>Kozhevnikov: /* Факт №2 */</p>
<hr />
<div>'''Алгоритм Касаи''' (Аримуры-Арикавы-Касаи-Ли-Парка) {{---}} алгоритм, позволяющий за линейное время вычислить<br />
длину наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом<br />
порядке (largest common prefix, далее <tex>LCP</tex>).<br />
<br />
==Обозначения==<br />
Задана строка <tex>S</tex>. Тогда <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив <tex>Suf</tex>. Для вычисления <tex>LCP</tex> будем использовать промежуточный массив <tex>Suf^{-1}</tex>. Массив <tex>Suf^{-1}</tex> определен как обратный к массиву <tex>Suf</tex>. Он может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.<br />
<br />
<tex>Height[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).<br />
<br />
==Некоторые свойства <tex>LCP</tex>==<br />
===Факт №1===<br />
<tex>LCP</tex> между двумя суффиксами {{---}} это минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min_{x < y \le z}(LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.<br />
Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.<br />
<br />
{{Утверждение<br />
|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \ge LCP(S_{Suf[x]},S_{Suf[z]}), x < y \le z</tex><br />
}}<br />
<br />
===Факт №2===<br />
Если значение <tex>LCP</tex> между парой суффиксов, соседних в массиве <tex>Suf</tex>, больше <tex>1</tex>, то можно удалить первый символ каждого суффикса и лексикографический порядок суффиксов сохранится.<br><br />
{{Утверждение<br />
|statement=<br />
Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 1]</tex><br />
}}<br />
[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к факту 2 и 3]]<br />
<br />
===Факт №3===<br />
В этом же случае, значение <tex>LCP</tex> между <tex>S_{Suf[x-1]+1}</tex> и <tex>S_{Suf[x]+1}</tex> на один меньше значения <tex>LCP</tex> между <tex>S_{Suf[x-1]}</tex> и <tex>S_{Suf[x]}</tex>.<br><br />
{{Утверждение<br />
|statement=Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>LCP(S_{Suf[x-1]+1} , S_{Suf[x]+1}) = LCP(S_{Suf[x-1]} , S_{Suf[x]} ) - 1</tex><br />
}}<br />
<br />
===Вспомогательные утверждения===<br />
<br />
Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседних суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>Height[q]</tex>, когда задано <tex>Height[p]</tex><br />
<br />
{{Лемма|statement=<br />
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \ge LCP(S_j,S_i)</tex><br />
|proof=<br />
Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из факта №2. Так как <tex>Suf^{-1}[j] \le Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \ge LCP(S_{j} , S_{i})</tex> из факта №1<br />
}}<br />
<br />
{{Теорема|statement=<br />
Если <tex>Height[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>Height[q] = LCP(S_{k}, S_{i}) \ge Height[p] - 1</tex><br />
|proof=<br />
<tex>LCP(S_{k}, S_{i}) \ge LCP(S_{j} , S_{i})</tex>(из Леммы) = <tex>LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта №3).<br />
}}<br />
<br />
==Описание алгоритма==<br />
Таким образом, начиная проверять <tex>LCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>LCP</tex>.<br />
Покажем, что построение <tex>LCP</tex> таким образом действительно требует <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>LCP</tex> может быть не более<br />
чем на единицу меньше предыдущего. Таким образом, значения <tex>LCP</tex> в сумме могут увеличиться не более, чем на <tex>2N</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>LCP</tex> за <tex>O(N)</tex>.<br />
<br />
==Источники==<br />
1. [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%81%D0%B0%D0%B8 Алгоритм Касаи].<br/><br />
2. [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.8221 T.Kasai, G.Lee, H.Arimura, S.Arikawa, K.Park - Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application].<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Суффиксный массив]]</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Kasai.png&diff=26423Файл:Kasai.png2012-06-21T19:56:21Z<p>Kozhevnikov: Илюстрация к алгоритму Касаи</p>
<hr />
<div>Илюстрация к алгоритму Касаи</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3578Полином Жегалкина2010-10-11T00:14:46Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{..n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3577Полином Жегалкина2010-10-11T00:13:21Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{..n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.//<br />
2.Хотя бы одна функция, не сохраняющая 1.//<br />
3.Хотя бы одна нелинейная функция.//<br />
4.Хотя бы одна немонотонная функция.//<br />
5.Хотя бы одна несамодвойственная функция.//<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3576Полином Жегалкина2010-10-11T00:12:41Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0. \\<br />
2.Хотя бы одна функция, не сохраняющая 1. \\<br />
3.Хотя бы одна нелинейная функция. \\<br />
4.Хотя бы одна немонотонная функция. \\<br />
5.Хотя бы одна несамодвойственная функция. \\<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3575Полином Жегалкина2010-10-11T00:10:22Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3574Полином Жегалкина2010-10-11T00:08:32Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
\begin{enumerate}<br />
\item 1.Хотя бы одна функция, не сохраняющая 0.<br><br />
\item 2.Хотя бы одна функция, не сохраняющая 1.<br><br />
\item 3.Хотя бы одна нелинейная функция.<br><br />
\item 4.Хотя бы одна немонотонная функция.<br><br />
\item 5.Хотя бы одна несамодвойственная функция.<br><br />
\end{enumerate}<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3573Полином Жегалкина2010-10-11T00:05:35Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<nowiki><br />
1.Хотя бы одна функция, не сохраняющая 0.<br><br />
2.Хотя бы одна функция, не сохраняющая 1.<br><br />
3.Хотя бы одна нелинейная функция.<br><br />
4.Хотя бы одна немонотонная функция.<br><br />
5.Хотя бы одна несамодвойственная функция.<br><br />
</nowiki><br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3572Полином Жегалкина2010-10-11T00:04:53Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<nowiki><br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
</nowiki><br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3571Полином Жегалкина2010-10-11T00:04:06Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<list> <br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
</list><br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3570Полином Жегалкина2010-10-11T00:03:26Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3569Полином Жегалкина2010-10-10T23:59:39Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно использовать [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]].</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3568Полином Жегалкина2010-10-10T23:58:49Z<p>Kozhevnikov: </p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.<br />
<br />
Третий способ - можно воспользоваться Преобразованием Мёбиуса для получения коэффициентов полинома Жегалкина.[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]</div>Kozhevnikovhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC_%D0%96%D0%B5%D0%B3%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0&diff=3567Полином Жегалкина2010-10-10T23:56:55Z<p>Kozhevnikov: Новая страница: «'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения бе…»</p>
<hr />
<div>'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:<br />
<br />
<br />
<math>P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} </math><br />
== Предпосылки ==<br />
<br />
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:<br />
<br />
1.Хотя бы одна функция, не сохраняющая 0.<br />
2.Хотя бы одна функция, не сохраняющая 1.<br />
3.Хотя бы одна нелинейная функция.<br />
4.Хотя бы одна немонотонная функция.<br />
5.Хотя бы одна несамодвойственная функция.<br />
<br />
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.<br />
<br />
== Cуществование и единственность представления (теорема Жегалкина) ==<br />
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от <math>n</math> переменных <math>2^{2^n}</math> штук. При этом конъюнкций вида <math>x_{i_1}\ldots x_{i_k}</math> существует ровно <math>2^n</math>, так как из <math>n</math> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <math>2^{2^n}</math> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.<br />
<br />
<br />
== Построение полинома Жегалкина ==<br />
<br />
Существует несколько способов построения полинома Жегалкина. <br />
<br />
Первый способ - по таблице истинности. Пусть для функции <math>f(x_{1},x_{2},..,x_{n})</math> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент.<br />
<br />
Второй способ - преобразование Дизъюнктивной нормальной формы. Этот способ основан на том, что <math> X \oplus 1 = \bar{X} </math>. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как <math> X \oplus X = 0 </math>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.</div>Kozhevnikov