Полином Жегалкина — полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики. Полином Жегалкина имеет следующий вид:
[math]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 [/math]
Предпосылки
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
- Хотя бы одна функция, не сохраняющая 0;
- Хотя бы одна функция, не сохраняющая 1;
- Хотя бы одна нелинейная функция;
- Хотя бы одна немонотонная функция;
- Хотя бы одна несамодвойственная функция.
Исходя из этого, система функций [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] является полной, так как в ней:
- Не сохраняет 0: [math] 1 [/math];
- Не сохраняет 1: [math] \oplus [/math];
- Нелинейна: [math] \wedge [/math];
- Немонотонна: [math] \oplus [/math];
- Несамодвойственны: [math] \wedge, \oplus, 1 [/math].
На основе этой системы и строятся полиномы Жегалкина.
Построение полинома Жегалкина
Существует несколько способов построения полинома Жегалкина.
По таблице истинности
Пусть для функции [math]f(x_1,x_2,..,x_n)[/math] задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что [math] a \oplus 1 = \bar{a}[/math], а [math] a \oplus 0 = a[/math]. За каждую подстановку находим только один коэффициент.
Пример:
Дана функция [math]f(x_1,x_2,x_3,x_4)[/math] и её таблица истинности:
| [math]x_1[/math]
|
[math]x_2[/math]
|
[math]x_3[/math]
|
[math]x_4[/math]
|
[math]f(x_1,x_2,x_3,x_4)[/math]
|
| 0 |
0 |
0 |
0 |
0
|
| 0 |
0 |
0 |
1 |
0
|
| 0 |
0 |
1 |
0 |
0
|
| 0 |
0 |
1 |
1 |
0
|
| 0 |
1 |
0 |
0 |
0
|
| 0 |
1 |
0 |
1 |
0
|
| 0 |
1 |
1 |
0 |
1
|
| 0 |
1 |
1 |
1 |
0
|
| 1 |
0 |
0 |
0 |
1
|
| 1 |
0 |
0 |
1 |
0
|
| 1 |
0 |
1 |
0 |
0
|
| 1 |
0 |
1 |
1 |
1
|
| 1 |
1 |
0 |
0 |
1
|
| 1 |
1 |
0 |
1 |
0
|
| 1 |
1 |
1 |
0 |
1
|
| 1 |
1 |
1 |
1 |
0
|
Построим для неё полином Жегалкина:
[math]f(x_1,x_2,x_3,x_4) = a_{0000} \oplus a_{1000} x_1 \oplus a_{0100} x_2 \oplus a_{0010} x_3 \oplus a_{0001} x_4 \oplus a_{1100} x_1 x_2 \oplus a_{1010} x_1 x_3 \oplus a_{1001} x_1 x_4 \oplus a_{0110} x_2 x_3 \oplus a_{0101} x_2 x_4 \oplus a_{0011} x_3 x_4 \oplus a_{1110} x_1 x_2 x_3 \oplus a_{1101} x_1 x_2 x_4 \oplus a_{1011} x_1 x_3 x_4 \oplus a_{0111} x_2 x_3 x_4 \oplus a_{1111} x_1 x_2 x_3 x_4[/math]
Так как [math]f(0,0,0,0) = 0[/math], то [math]a_{0000} = 0[/math].
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:
[math]f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1 \Rightarrow a_{1000} = 1[/math]
[math]f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0 \Rightarrow a_{0100} = 0[/math]
[math]f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0 \Rightarrow a_{0010} = 0[/math]
[math]f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0 \Rightarrow a_{0001} = 0[/math]
[math]f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1 \Rightarrow a_{1100} = 0[/math]
[math]f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1010} = 0 \Rightarrow a_{1010} = 1[/math]
[math]f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1001} = 0 \Rightarrow a_{1001} = 1[/math]
[math]f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1 \Rightarrow a_{0110} = 1[/math]
[math]f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0 \Rightarrow a_{0101} = 0[/math]
[math]f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0 \Rightarrow a_{0011} = 0[/math]
[math]f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1 \Rightarrow a_{1110} = 0[/math]
[math]f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0 \Rightarrow a_{1101} = 0[/math]
[math]f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1 \Rightarrow a_{1011} = 0[/math]
[math]f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0 \Rightarrow a_{0111} = 1[/math]
[math]f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0 \Rightarrow a_{1111} = 1[/math]
Таким образом, полином Жегалкина выглядит так:
[math]f(x_1,x_2,x_3,x_4) = x_1 \oplus x_1 x_3 \oplus x_1 x_4 \oplus x_2 x_3 \oplus x_2 x_3 x_4 \oplus x_1 x_2 x_3 x_4[/math]
Этот способ основан на том, что [math] X \oplus 1 = \bar{X} [/math]. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как [math] X \oplus X = 0 [/math]), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
[math] A \lor B = AB \oplus A \oplus B [/math] [math] (1) [/math].
Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.
Пример:
Дана функция в ДНФ [math] f(x_1,x_2,x_3,x_4) = (x_1 \land x_2 \land \neg x_3 \land x_4) \lor (\neg x_1 \land \neg x_4) \lor (x_1 \land x_2) \lor x_2 [/math], построим полином Жегалкина.
Запишем функцию так:
[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 + \neg x_1 \neg x_4 + x_1 x_2 + x_2[/math];
Сгруппируем слагаемые и воспользуемся преобразованием (1):
[math]f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_1 x_2 \neg x_3 x_4 \neg x_1 \neg x_4) + (x_1 x_2 \oplus x_2 \oplus x_1 x_2 x_2)[/math]
Воспользуемся свойствами конъюнкции [math]A \land A = A[/math] и [math]\neg A \land A = 0[/math], а также тем, что [math]A \oplus A = 0[/math], и упростим выражение:
[math]f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) + x_2 [/math]
Ещё раз воспользуемся преобразованием (1):
[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4)x_2[/math]
Раскроем скобку по алгебраическим правилам:
[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus x_1 x_2 x_2 \neg x_3 x_4 \oplus \neg x_1 x_2 \neg x_4 [/math]
Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:
[math]f(x_1,x_2,x_3,x_4) = \neg x_1 \neg x_4 \oplus x_2 \oplus \neg x_1 x_2 \neg x_4 [/math]
Заменим отрицание на прибавление [math]1[/math]:
[math]f(x_1,x_2,x_3,x_4) = (x_1 \oplus 1) (x_4 \oplus 1) \oplus x_2 \oplus (x_1 \oplus 1) x_2 (x_4 \oplus 1)[/math]
Раскроем скобки:
[math]f(x_1,x_2,x_3,x_4) = x_1 x_4 \oplus x_1 \oplus x_4 \oplus 1 \oplus x_2 \oplus x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_2 x_4 \oplus x_2[/math]
Выкинем парные слагаемые и получим окончательную формулу:
[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 \oplus x_4 \oplus 1[/math]
Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
- Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000...00 до 111...11.
- Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
- Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
- Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
- Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
- Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.
Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца P таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.
Таким образом, в первом столбце сверху записан коэффициент [math] a_0 = P(0,0,0) [/math],
во втором — [math] a_1 = P(0,0,0) \oplus P(0,0,1) [/math],
в третьем — [math] a_2 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) = P(0,0,0) \oplus P(0,1,0) [/math],
в четвёртом —
[math] a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1), [/math]
и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.
Преобразование Мёбиуса
Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}[/math].
Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
Пусть [math] i = (i_1, i_2, .. i_n), \;\; i_k \in \{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 = (i_1, i_2, .. i_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]x[/math], [math]i \succ x[/math] ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.
Отсюда ясно, что
[math] f(x) = \bigoplus \limits_{i \preceq x} \alpha_i [/math]. [math] (2) [/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] (3) [/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] (2) [/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 \rightarrow \alpha[/math] также называется преобразованием Мёбиуса.
Видно, что [math] (2) [/math] и [math] (3) [/math] — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию [math]f[/math]. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
Литература и источники информации
