17
правок
Изменения
м
<tex> A \lor B = AB \oplus A \oplus B </tex> <tex> (1) </tex>.
тикет
'''Полином Жегалкина''' (Zhegalkin polynomial) — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
<tex>P = a_{000...000} \oplus a_{100...0} x_1 \oplus a_{010...0} x_2 \oplus ... \oplus a_{00...01} x_n \oplus a_{110...0} x_1 x_2 \oplus ... \oplus a_{00...011} x_{n-1} x_n \oplus ... \oplus a_{11..1} x_1 x_2 ... x_n </tex>
Исходя из этого, система функций <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex> является полной, так как в ней:
#Не сохраняет <tex>0</tex>: <tex> 1 </tex>;
#Не сохраняет <tex>1</tex>: <tex> \oplus </tex>;
#Немонотонна: <tex> \oplus </tex>;
#Несамодвойственны: <tex> \wedge, \oplus, 1 </tex>.
{| class="wikitable" style="width:8cm" border="1"
|-align="center" bgcolor=#EEEEFF
!<tex>x_0</tex>||<tex>x_1</tex>||<tex>\dots</tex>||<tex>x_n</tex>
|<tex>1</tex>||<tex>\land</tex>||<tex>\oplus</tex>
|-align="center"
!<tex>0</tex>||<tex>0</tex>||<tex>\dots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!<tex>1</tex>||<tex>0</tex>||<tex>\dots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|-align="center"
!<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|-align="center"
!<tex>1</tex>||<tex>1</tex>||<tex>\dots</tex>||<tex>1</tex>
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Сохраняет 0
|<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
|-align="center"
!colspan="4"|Сохраняет 1
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Самодвойственная
|<tex>0</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Монотонная
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Линейная
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|}
На основе этой системы и строятся полиномы Жегалкина.
=== По таблице истинности ===
Пусть для функции <tex>f(x_1,x_2,..\dots,x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.
'''Пример:'''
=== Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]] ===
Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.
=== Метод треугольника === <!-- Да, копипаста с википедии, и что? Метод же прост и удобен -->
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000...00 \dots00</tex> до <tex>111...11\dots11</tex>.
# Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
# Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
# Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
# Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке <tex>111 </tex> соответствует член <tex>ABC</tex>, ячейке <tex>101 </tex> — член <tex>AC</tex>, ячейке <tex>010 </tex> — член <tex>B</tex>, ячейке <tex>000 </tex> — член <tex>1 </tex> и т.д.
# Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных <tex>P(A,B,C) </tex> показан на рисунке.
[[Файл:Преобразование таблицы истинности в полином Жегалкина методом треугольника.gif]]
Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца <tex>''P'' </tex> таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.
Таким образом, в первом столбце сверху записан коэффициент <tex> a_0 = P(0,0,0) </tex>,
Тогда полином Жегалкина можно записать как:
<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot ... </tex><tex>\dots</tex><tex>\cdot x_n^{i_n}</tex>, где <tex>\alpha_i \in \{ 0; 1 \}</tex>.
Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, .. \dots i_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 ... </tex><tex>\dots</tex><tex>\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> <tex> (2) </tex>
Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).
{{Теорема
|statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_x </tex> можно найти по формуле: <tex>\alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex> <tex> (3) </tex>.
||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+...</tex><tex>\dots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.
'''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha_0 </tex>
