Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
Практически 100%-ая копия полюбившегося многим инстаграм, идеально подойдет для портфолио, презентации работ своим клиентам или как отклик на понравившуюся вакансию. Молодой ресурс, но администраторы оперативно реагируют на предложения и вопросы.
Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
Полином Жегалкина — многочлен над кольцом $\mathbb < Z >_2$, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой < АНФ >.
Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина.
Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также < если необходимо >константы
Формально полином Жегалкина можно представить в виде
или в более формализованном виде как:
$P = a \oplus \bigoplus_ < \begin
Примеры полиномов Жегалкина:
- $ P = B \oplus AB;$
- $ P = X \oplus YZ \oplus ABX \oplus ABDYZ;$
- $ P = 1 \oplus A \oplus ABD.$
Полнота
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
- Хотя бы одна функция, не сохраняющая $0$;
- Хотя бы одна функция, не сохраняющая $1$;
- Хотя бы одна нелинейная функция;
- Хотя бы одна немонотонная функция;
- Хотя бы одна несамодвойственная функция.
Исходя из этого, система функций $\bigl\langle \wedge, \oplus, 1 \bigr\rangle$ является полной:
| $x_0$ | $x_1$ | $\dots$ | $x_n$ | $1$ | $\land$ | $\oplus$ |
| $0$ | $0$ | $\dots$ | $0$ | $1$ | $0$ | $0$ |
| $1$ | $0$ | $\dots$ | $0$ | $1$ | $0$ | $1$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $1$ | $1$ | $\dots$ | $1$ | $1$ | $1$ | $0$ |
| . | . | . | сохраняет 0 | $0$ | $1$ | $1$ |
| . | . | . | сохраняет 1 | $1$ | $1$ | $0$ |
| . | . | . | самодвойственная | $0$ | $0$ | $0$ |
| . | . | . | монотонная | $1$ | $1$ | $0$ |
| . | . | . | линейная | $1$ | $0$ | $1$ |
На основе этой системы и строятся полиномы Жегалкина.
Существование и единственность представления
Теорема Жегалкина: Каждая булева функция единственным образом представляется в виде полинома Жегалкина.
Заметим, что различных булевых функций от $n$ переменных $2^ < 2^n >$ штук. При этом конъюнкций вида $x_ < i_1 >\ldots x_ < i_k >$ существует ровно $2^n$, так как из $n$ возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит $0$ или $1$, то есть существует $2^ < 2^n >$ различных полиномов Жегалкина от $n$ переменных.
Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него < любой один, если таких несколько >. Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
Построение полинома Жегалкина
Существует несколько способов построения полинома Жегалкина.
По таблице истинности
Пусть для функции $f(x_1,x_2,\dots,x_n)$ задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что $ a \oplus 1 = \bar < a >$, а $ a \oplus 0 = a$. За каждую подстановку находим только один коэффициент.
Пример: Дана функция $f(x_1,x_2,x_3,x_4)$ и её таблица истинности:
| $x_1$ | $x_2$ | $x_3$ | $x_4$ | $f(x_1,x_2,x_3,x_4)$ |
| 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 |
Построим для неё полином Жегалкина:
$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 \\ \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 \\ \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$
Так как $f(0,0,0,0) = 0$, то $a_ < 0000 >= 0$.
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:
$f(1,0,0,0) = a_ < 0000 >\oplus a_ < 1000 >= 1 \Rightarrow a_ < 1000 >= 1$
$f(0,1,0,0) = a_ < 0000 >\oplus a_ < 0100 >= 0 \Rightarrow a_ < 0100 >= 0$
$f(0,0,1,0) = a_ < 0000 >\oplus a_ < 0010 >= 0 \Rightarrow a_ < 0010 >= 0$
$f(0,0,0,1) = a_ < 0000 >\oplus a_ < 0001 >= 0 \Rightarrow a_ < 0001 >= 0$
$f(1,1,0,0) = a_ < 0000 >\oplus a_ < 1000 >\oplus a_ < 0100 >\oplus a_ < 1100 >= 1 \Rightarrow a_ < 1100 >= 0$
$f(1,0,1,0) = a_ < 0000 >\oplus a_ < 1000 >\oplus a_ < 0100 >\oplus a_ < 1010 >= 0 \Rightarrow a_ < 1010 >= 1$
$f(1,0,0,1) = a_ < 0000 >\oplus a_ < 1000 >\oplus a_ < 0100 >\oplus a_ < 1001 >= 0 \Rightarrow a_ < 1001 >= 1$
$f(0,1,1,0) = a_ < 0000 >\oplus a_ < 0100 >\oplus a_ < 0010 >\oplus a_ < 0110 >= 1 \Rightarrow a_ < 0110 >= 1$
$f(0,1,0,1) = a_ < 0000 >\oplus a_ < 0100 >\oplus a_ < 0001 >\oplus a_ < 0101 >= 0 \Rightarrow a_ < 0101 >= 0$
$f(0,0,1,1) = a_ < 0000 >\oplus a_ < 0010 >\oplus a_ < 0001 >\oplus a_ < 0011 >= 0 \Rightarrow a_ < 0011 >= 0$
$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$
$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$
$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$
$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$
$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 \\ \oplus a_ < 1110 >\oplus a_ < 1101 >\oplus a_ < 1011 >\oplus a_ < 0111 >\oplus a_ < 1111 >= 0 \Rightarrow a_ < 1111 >= 1$
Таким образом, полином Жегалкина выглядит так:
$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$
Преобразование дизъюнктивной нормальной формы
Этот способ основан на том, что $ X \oplus 1 = \bar < X >$. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю < так как $ X \oplus X = 0 $ >, а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу: $ A \lor B = AB \oplus A \oplus B $ $ (1) $.
Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.
Пример: Дана функция в ДНФ $ 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 $, построим полином Жегалкина.
Запишем функцию так:
$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$;
Сгруппируем слагаемые и воспользуемся преобразованием (1):
$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 \oplus x_1 x_2 x_2)$
Воспользуемся свойствами конъюнкции $A \land A = A$ и $\neg A \land A = 0$, а также тем, что $A \oplus A = 0$, и упростим выражение:
$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$
Ещё раз воспользуемся преобразованием (1):
$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$
Раскроем скобку по алгебраическим правилам:
$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$
Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:
$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$
Заменим отрицание на прибавление $1$:
$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)$
$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$
Выкинем парные слагаемые и получим окончательную формулу:
$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$
Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
- Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от $000\dots00$ до $111\dots11$.
- Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
- Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
- Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
- Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке $111$ соответствует член $ABC$, ячейке $101$ — член $AC$, ячейке $010$ — член $B$, ячейке $000$ — член $1$ и т.д.
- Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных $P(A,B,C)$ показан на рисунке.
Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца $»P»$ таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.
Таким образом, в первом столбце сверху записан коэффициент $ a_0 = P(0,0,0) $,
во втором — $ a_1 = P(0,0,0) \oplus P(0,0,1) $,
в третьем — $ 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) $,
$ 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), $
и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.
Преобразование Мёбиуса
Пусть задана булева функция $f: B^n \rightarrow B, \;\; B=\ < 0; 1 \ >$. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
Пусть $ i = (i_1, i_2, .. i_n), \;\; i_k \in \ < 0 ; 1\ >$, и введем обозначение $ x ^ < i_k >\sim \left[\begin < matrix >x,\;\; i_k=1 1, \;\; i_k=0\end < matrix >\right. $
Тогда полином Жегалкина можно записать как: $ f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^ < i_1 >\cdot x_2^ < i_2 >\cdot$$\dots$$\cdot x_n^ < i_n >$, где $\alpha_i \in \ < 0; 1 \ >$.
Множество коэффициентов $\ < \alpha _i\ >$ можно рассматривать как функцию $\alpha$, заданной на множестве индексов $ i = (i_1, i_2, \dots i_n)$, то есть $\alpha: i \mapsto \alpha_i$.
Очевидно, функцию $ f $ можно записать и следующим образом: $ f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; $ если $ \;\; i_1] \cdot [x_2 , \; $ если $ \;\; i_2] \cdot$$\dots$$\cdot [x_n , \; $ если $ \;\; i_n]$.
Тут запись $[x_k , \; $ если $ \; i_k]$ означает, что элелемент $ x_k $ присутствует в соответствующем члене полинома только если $ i_k = 1 $. Тогда если для какого-то $x$, $i \succ x$* ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет. Отсюда ясно, что $ f(x) = \bigoplus \limits_ < i \preceq x >\alpha_i $ $ (2) $ Найдем отображение $ f \mapsto \alpha$ < То есть такое, которое по заданной функции вычисляет значения всех коэффициентов >.
$*$ $i \succ x$ обозначает, что $x$ "меньше" $i$ как последовательность бит
Теорема: Пусть задана функция $ f $. Тогда функцию $ \alpha_x $ можно найти по формуле: $\alpha_x = \bigoplus \limits_ < j\preceq x >f(j)$ (3)
Докажем при помощи индукции по количеству единиц в векторе $ x $ < иначе говоря, по сумме $x_1+x_2+\dots +x_n$ >и для удобства обозначим это количество единиц < сумму >$ wt(x) $.
1) База: если $ x = 0 $, то, очевидно $ f(0) = \alpha_0 $
2) Пускай теорема справедлива для всех сумм $wt(x) < k$. Покажем, что в таком случае она верна и для $wt(x) = k$. По $ (2) $, а далее по предположению индукции видим: $ 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$ .
Рассмотрим сумму $ \left [ \bigoplus \limits_ < i \prec x >\bigoplus \limits_ < j\preceq i >f(j) \right ] $. Каждый элемент $ f(j) $ содержится в ней, только если $ j \prec x $, и для фиксированных $ j, x $ элемент $ f(j)$ встречается ровно столько раз, сколько существует $ i $ , таких, что $ j \prec i \prec x$. Несложно увидеть, что таких $ i $ существует ровно $ 2^ < wt(x)-wt(j) >-1 $, то есть нечетное количество раз. Тогда $ \left [ \bigoplus \limits_ < i \prec x >\bigoplus \limits_ < j\preceq i >f(j) \right ] = \bigoplus \limits_ < j\prec x >f(j) $. Но тогда $ 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)$. То есть при $wt(x) = k$ формула также выполняется, значит при любых $ x $ выполняется $\alpha_x = \bigoplus \limits_ < j\preceq x >f(j)$.
Отображение $ f \rightarrow \alpha$ также называется преобразованием Мёбиуса.
Видно, что $ (2) $ и $ (3) $ — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию $f$. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
2.6. Полиномы Жегалкина
Полиномом (многочленом) Жегалкина от п переменных называется функция, в которой для получения ее значений (из набора значений аргументов) используется фиксированная цепочка операций 3 видов: конъюнкций, сложений по модулю 2 и констант (т. е. нулей и единиц).
Ясно, что любой полином Жегалкина можно (после преобразований) записать в виде
P 0 1 x 1 2 x 2
n x n n 1 x 1 x 2
n C 2 x n 1 x n
2 n 1 x 1 x 2 x n . (2.6)
Всего здесь 2 п слагаемых. Напомним, что + сейчас означает сложение по модулю 2, коэффициенты 0 , 1 , , 2 n 1 являются константами (рав-
ными нулю или единице).
Например, полином Жегалкина от 3 переменных всегда можно привести к виду
P ( x , y , z ) 0 1 x 2 y 3 z 4 xy 5 xz 6 yz 7 xyz . (2.7)
Замечание . При помощи сложения по модулю 2 легко записать отрицание любой логической функции: K K 1 , в частности, х + 1 = x
Теорема . Любая логическая функция может быть представлена полиномом Жегалкина.
Доказательство . Любую функцию можно записать в виде ДНФ. Запишем двойное отрицание этой ДНФ (что не меняет функции). При помощи нижнего отрицания и правила Де Моргана избавимся от дизъюнкций. В оставшейся записи данной функции будут присутствовать только конъюнкции и отрицания. Каждое отрицание заменим на прибавление единицы. В получившейся записи функции на переменные будут действовать только конъюнкции, сложения по модулю 2 и присутствовать константы. Это и значит, что функция записана в виде полинома Жегалкина, и теорема доказана.
Замечания : 1) в доказательстве приведен алгоритм перехода от записи функции в виде ДНФ к ее записи в виде полинома Жегалкина.
f ( x , y , z ) = xy x y y z xy x y y z = ( xy + 1)(( x + 1)( y + 1) + 1)(( y + 1) z + 1) + 1 =
= ( xy + 1)( xy + x+ y) ( yz + z + 1) + 1 = ( x+ y) ( yz + z + 1) + 1 =
= xyz + yz + xz + yz + x + y + 1 = xyz + xz + x + y + 1;
2) напоминаем, что при сложении (по модулю 2) 1 + 1 = 0. Поэтому сумма четного числа одинаковых слагаемых всегда равна 0. Например, xyz + xyz + xyz = xyz ;
3) надо уметь переходить к полиному Жегалкина не только от ДНФ (по алгоритму, приведенному в доказательстве теоремы), но и от таблицы истинности данной функции. Для такого перехода надо знать 2 алгоритма: метод неопределенных коэффициентов и «метод бабочки».
Метод неопределенных коэффициентов. Запишем сначала нашу функ-
цию в виде полинома Жегалкина с неопределенными коэффициентами, т. е. перепишем формулу (2.6), в частности, для функции 3 переменных – формулу (2.7). Затем в написанную формулу по очереди подставляем всевозможные наборы значений переменных и приравниваем полученные выражения соответствующим значениям функции из ее таблицы истинности.
Из полученных равенств, в которых неизвестными являются коэффициенты полинома Жегалкина, находим эти коэффициенты. Легко видеть, что за каждую подстановку мы находим ровно один коэффициент. Так как
число наборов равно числу коэффициентов (и равно 2 п ), то мы сможем найти все коэффициенты и, подставляя их в исходную формулу (2.6) (в частности, в формулу (2.7)), получим полином Жегалкина данной функции.
Метод бабочки. Пусть дана функция z = f ( x 1 , x 2 , … , x п ) от п переменных. В ее таблице истинности записаны 2 п ее значений. Алгоритм метода бабочки заключается в последовательном проведении п операций, обычно называемых итерациями. 1-я итерация: рядом со столбцом значений данной функции записывается новый столбец; в верхнюю его половину (т. е. от 1-й строчки до строчки с номером 2 п– 1 ) переписываются числа из столбца значений функции, т. е числа f (0, x 2 , … , x п ), а в нижнюю его половину (т. е. в строчках с номерами от 2 п– 1 + 1 до 2 п ) записываются суммы по модулю 2 соответствующих значений данной функции из верхней и нижней
половины таблицы, т. е. числа f (0, x 2 , … , x п ) + f (1, x 2 , … , x п ) . Во 2-й итерации ту же процедуру проделывают отдельно с верхней и отдельно с ниж-
ней частью столбца, полученного в результате проведения 1-й итерации. В результате проведения второй итерации появляется новый столбец, у которого в верхней четверти записаны числа f (0, 0, x 3 , … , x п ), во второй четверти – числа f (0, 0, x 3 , … , x п ) + f (0, 1, x 3 , … , x п ), в третьей четверти – числа f (0, 0, x 3 , … , x п ) + f (1, 0, x 3 , … , x п ), а в нижней четверти – числа
f (0, 0, x 3 , … , x п ) + f (1, 0, x 3 , … , x п ) + f (0, 1, x 3 , … , x п ) + f (1, 1, x , … , x п ) .
Эта процедура повторяется п раз. При проведении последней, п -й, итерации в последнем, п -м, столбце в строках с номерами 1, 3, 5, … , 2 п – 1 переписываются значения из предыдущего, п – 1 — го столбца, а в строках с номерами 2, 4, 6, … , 2 п записывается сумма (по модулю 2) того, что было записано в этой строке в п – 1 — м столбце со значением, записанном в этом же п – 1 — м столбце в предыдущей строке. По полученному п- му столбцу составляется полином Жегалкина данной функции: каждой единице этого столбца сопоставляется конъюнкция тех переменных, значения которых в строке с рассматриваемой единицей тоже равны единице, а затем эти конъюнкции переменных складываются по модулю 2. Последнее выражение и есть полином Жегалкина данной функции.
В последнем столбце – 3 единицы, которым соответствуют наборы значений аргументов (0, 0, 1), (0, 1, 0) и (1, 0, 1) соответственно. Значит, в полиноме Жегалкина этой функции складываются три простых конъюнкции, каждая из которых содержит всего по одной переменной – x , y и z соответственно, и поэтому искомый полином имеет вид: f ( x , y , z ) = x+ y+ z.
Обоснование метода бабочки. Докажем по индукции, что указанный метод действительно приводит к полиному Жегалкина.
База индукции. Для всех 4 функций одной переменной (т. е. для 0, 1, х , x ) это утверждение проверяется непосредственно при помощи одной итерации над их таблицами истинности. Индукционный переход. Пусть это утверждение уже доказано для всех логических функций от п переменных ( х 1 , х 2 , … , х п ). Докажем, что тогда оно верно и для функции f от п+ 1 переменной, т. е. для z = f ( х 1 , х 2 , … , х п , х п + 1 ). Считаем, что таблица истинности этой функции записана стандартным образом, т. е. по возрастанию двоичных чисел, соответствующих наборам значений аргументов. Тогда в п- м столбце, полученном в результате п- й итерации, в строках с номерами 1, 3, 5, … , 2 п – 1 стоят числа, соответствующие значению 0 последнего аргумента: х п+ 1 = 0 . Иными словами, в них стоят значения, соответствующие z = f ( х 1 , х 2 , … , х п , 0), т. е. функции от п переменных. По индукционному предположению, по их значениям можно записать полином Жегалкина для этой функции, поэтому мы записываем этот полином (у которого простые конъюнкции не содержат переменной х п+ 1 ), а значения из этих строк переписываем без изменений в последний, ( п + 1)-й столбец (т. е. для ( п + 1)-й итерации). В том же п -м столбце в строках с номерами 2, 4, 6, … , 2 п стоят числа, соответствующие тем же наборам значений аргументов, что и
в строках с номерами 1, 3, 5, … , 2 п– 1 (так как наборы значений аргументов
в строках с номерами 2 k– 1 и 2 k отличаются только значениями последнего
аргумента: х п+ 1 = 0 и х п+ 1 = 1 соответственно). Поэтому, если мы уже получили для полинома Жегалкина простую конъюнкцию x k 1 x k 2 . x k m ( k m < n + 1),
рассматривая строку с нечетным номером для f ( х 1 , х 2 , … , х п , 0) = 1, то в строке со следующим номером в последнем, ( п + 1)-м, столбце должен стоять 0, так как иначе в полиноме Жегалкина нужно будет записать сумму (по модулю 2) 2 простых конъюнкций x k 1 x k 2 . x k m + x k 1 x k 2 . x k m x n 1 , которая
при х п+ 1 = 1 и при любом наборе значений остальных переменных равна 0 (даже для тех наборов значений переменных, у которых соответствующая простая конъюнкция входит в полином Жегалкина с коэффициентом 1) . Иными словами, если в столбце, соответствующем предпоследней итерации, стоят подряд две единицы, то в столбце последней итерации должны стоять 1 и 0. Это достигается сложением двух единиц предпоследнего столбца, что и требуется для доказательства индукционного перехода (так как 1 + 0 = 0 + 1 = 1, а 0 + 0 = 0, то рассуждения в остальных вариантах расположения значений в предпоследнем столбце очевидны).
Многочлены Жегалкина
Любую булеву функцию можно представить в виде многочлена от своих переменных и такой многочлен называется многочленом Жегалкина.
Многочленом Жегалкина называется многочлен, являющийся суммой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени.
Многочлен Жегалкина константы равен самой же константе; многочлен Жегалкина булевой функции одной переменной f(x) = 
многочлен Жегалкина булевой функции двух переменных
f(x1,x2) = 
;
многочлен Жегалкина булевой функции трех переменных
f(x1,x2,x3)= 
и т.д. Коэффициенты a1. i и свободный член ао принимают значения О или 1, а число слагаемых в формуле равно 2 п , где п — число переменных. Знак 
— сумма Жегалкина или сумма по модулю два.
| Теорема | 3 (Жегалкина). | Каждая булева функция | f(x1,x2. хп) | может |
| быть представлена в виде | многочлена Жегалкина и | единственным | ||
| образом, | с точностью до порядка слагаемых. |
Сформулируем алгоритм построения многочлена Жегалкина. Выше было указано, что любую функцию, отличную от константы О, можно представить в виде СДНФ. Если сравним таблицы истинности
дизъюнкции и суммы по модулю два, видим, что они отличаются только последней строкой, т. е. на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю два. Кроме того, известно, что 
. На этом и основан первый алгоритм построения многочлена Жегалкина:
1. Находим множество тех двоичных наборов, на которых функция принимает значение 1.
2. Составляем СДНФ.
3. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегалкина.
4. Упрощаем, если можно, полученное выражение, используя тождество 
.
5. В полученной формуле каждое отрицание 
заменяем на 
.
6. Раскрываем скобки в полученной формуле, содержащей только
функции 
и 
и константу 1.
7. Приводим подобные члены, используя тождество 
.
Используя метод неопределенных коэффициентов, получаем второй алгоритм определения многочлена Жегалкина:
1. Составляем систему линейных уравнений относительно 2 п неизвестных коэффициентов, содержащую 2 п уравнений, решением которой являются коэффициенты ао, а1, …,а1,2…n многочлена Жегалкина.
Многочлен Жегалкина называется нелинейным, если он содержит конъюнкции переменных, а если он не содержит конъюнкции переменных, то он называется линейным.
Функция f(x1,х2. хп) называется линейной, если ее многочлен Жегалкина имеет вид 
и нелинейной в противном случае.
Из определения многочлена Жегалкина следует, что для любой булевой функции коэффициенты при переменных x1,х2. хп и свободный член вычисляются по формулам:
,
,
.
На этом основан алгоритм определения линейности (или нелинейности) булевой функции.
1. По таблицам истинности булевой функции f(x1,х2. хп) и выше указанным формулам находим коэффициенты: (ао, а1, …,а1,…n)
2. Выписываем многочлен Ф(x1. хп)= 
и проверяем, задает ли он эту функцию. Для этого строим таблицу истинности многочлена Ф(x1,х2. хп) и сравниваем ее с таблицей истинности функции f(x1,x2. хп).
Задача. Задана булева функция трех переменных:
;
а) постройте таблицу истинности, найдите двоичную форму F булевой функции и приведите функцию к СДНФ и СКНФ,
б) найдите двумя способами многочлен Жегалкина.
а) 
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Двоичная форма F= 11000100
Наборы 
=(000, 001, 101), где 
.
СДНФ функции 
.
Наборы =(010, 011, 100, 110, 111), где 
.
б) Построим многочлен Жегалкина первым способом:
выписываем СДНФ функции
;
заменяем знак дизъюнкции на знак суммы Жегалкина 
,
вынесем из первой и второй конъюнкции 
:
;
проделаем замены: 
, получим:
.
Далее раскроем скобки:
.
Итак, мы получим многочлен Жегалкина:
.
Построим многочлен Жегалкина методом неопределенных коэффициентов, для этого составим следующие восемь уравнений:
;
;
;
;
;
;
;
;
.
Составим многочлен Жегалкина:
.
Задача. Задана булева функция трех переменных
.
С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.
Решение. Заменяем, 
,
.
, тогда
ДНФ 
,
КНФ 
.
Строим СДНФ, для этого из ДНФ удаляем вторую конъюнкцию 
, а в третью конъюнкцию добавляем 
, тогда:
, т.е. получили СДНФ функции
.
Строим СКНФ, для этого из КНФ удаляем третью дизъюнкцию, а к первой добавляем 
:
,
добавляем к первой и второй дизъюнкциям 
.
Получили СКНФ функции
.
ГЛАВА III. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Теория графов, являясь разделом дискретной математики, используется для описания и изучения отношений между дискретными объектами. При этом объекты геометрически можно представить в виде множества точек, называемых вершинами графа, некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами). Обозначается G=(V,X).
Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, так же называется смежными (или соединенными). Ребро (дуга) и любая из его двух вершин называется инцидентными.
Граф называется ориентированным (или орграфом), если ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.
Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т.е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежный ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, на не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Последовательности вершин (рис. 2): 1-2-3-4-2-5 не простой путь, а маршрут; последовательности 1-2-3-4-7-5 и 1-2-5 — простые пути; 1-2-3-4-2-5-6-1 – это цикл (но не контур); 1-2-5-6-1 – это контур.
Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i,j),то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).
Граф называется связанным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 1 изображен связный граф.
Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.
Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).
Степень вершины (валентность) –это число ребер, входящих в эту вершину число инцидентных вершине ребер. Вершина называется висячей если ее степень равна единице. Обозначают di или deg vi.
Петля добавляет 2 в степень вершины.
(число ребер).
Сумма степень вершин графа G всегда равна 2m, где m – число ребер графа G/в любом графе число вершин с нечетными степенями четно.
Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.
Два графа G=(V, X) и H=(W, Y) называют изоморфными, если между их множествами вершин V и W существует взаимнооднозначное соответствие, сохраняющее смежность. Изоморфизм есть отношение эквивалентности на графах. Из определения следует, что изоморфные графы отличаются лишь обозначением вершин.
Пример 2. Графы G и H, изображенные на рис. 3, изоморфны.
Для того, чтобы доказать их изоморфность достаточно пометить их вершины в соответствующем порядке (рис. 4):
Инвариант графа G – это число, связанное с G, которое принимает одно и то же значение на любой графе, изоморфном G. Числа n (число вершин графа) и m (число ребер) являются инвариантами графа. Полный набор инвариантов определяет граф с точностью до изоморфизма. Например, числа n и m образуют полный набор инвариантов для всех графов с n<4.
Подграфом G=(V, X) графа G=(V, X) называется граф, у которого все вершины и ребра (дуги) принадлежат G: V, />V, X />X, каждое из ребер xi инцидентно только вершинам из V. Если G – подграф G,то G – надграф (super-graf) графа G. Основной подграф – это подграф G, содержащий все его вершины.
Для компьютерной обработки используется матричная форма представления структурных свойств графа.
Это следующие матрицы:
1. Матрица смежности. Это квадратная матрица порядка n (n – число вершин), в которой нули стоят по главной диагонали (если в графе нет петель, а если петли есть в вершине k (и число этих петель равно p), то на главной диагонали в строчке с номером k стоит число p). Если вершина i связана с вершиной одним ребром, то элемент матрицы смежности aij равен 1, если эти вершины связаны s ребрами, то aij= s. Аналогичным образом строятся матрицы смежности для орграфов и для мультиграфов.
Матрица смежности A(G) определяет граф G с точностью до изоморфизма; она является симметричной матрицей с нулями по главной диагонали. Сумма элементов по строкам матрицы A(G) равна степеням вершин графа G.
Так как у графа G 5 вершин, то размер матрицы A (G), будет 5х5:
a12=1, т.к. в графе G есть ребро, соединяющее вершины v1 и v2; a42=0, т.к. в графе G нет ребра, соединяющего вершины v4 и v2 и т.д.
Если A – матрица смежности графа G, то элемент матрицы A n , стоящий в i-той строке и j-том столбце, будет равен числу маршрутов длины n из вершины vi и vj.
Для примера 6 имеем:
существует 2 маршрута длины 2 из вершины v2 в вершину v5: v2-v1-v5 и v2-v3-v5;
существует 7 маршрутов длины 3 из вершины v5 в вершину v3: v5-v1-v2-v3, v5-v1-v5-v3, v5-v4-v5-v1, v5-v3-v5-v3, v5-v3-v1-v3, v5-v3-v2-v3, v5-v3-v4-v3.
Матрицей смежности орграфа D называется квадратная матрица A(D) порядка n (n- число) с вершинами элемента:
Матрица смежности орграфа в общем случае не будет симметричной.
Пример 7. Дан орграф D:
Так как у графа D 6 вершин, то размер матрицы A(D) будет 6х6:
Сумма всех элементов i-ой строки равна числу равна числу дуг, выходящий из вершины vi; сумма всех элементов j-го столбца равен числу дуг, направленных в вершину vj. Если А – матрица смежност орграфа D, то элемент матрицы A n , стоящий в i-ой и ом столбце, будет равен числу путей (не обязательно оргцепей и простых оргцепей) длины n, идущих из вершины vi в вершину vj.
Легко видеть, что матрица B=A 2 = AA составлена из целых чисел bij, которые равны числу путей длины 2, соединяющих вершины i и j. Понятно, что А 3 составлена из чисел, равных числу путей длины 3 (т.е. путей из 3-х ребер) из вершины i в вершину j и т.д.
Матрица инциденций – это матрица размера nхm, где n – число вершин, а m- число ребер графа, при этом ее элементы kij равны 1, если вершина с номером i является для ребра с номером j начальной или конечной (если ребро неориентировано) и начальной для ориентированных ребер
Матрица B(G)определяет граф Gс точностью до изоморфизма.
Пример 8. Для графа G изображенного на рис. 1.8 матрица B(G) приводится в табл. 1.1
| x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| v1 | ||||||
| v2 | ||||||
| v3 | ||||||
| v4 | ||||||
| v5 |
Матрицей инцидентности орграфа D называется (nxm) – матрица B(D)=(bij), у которой:
Пример 9. Для орграфа D, изображенного на рис. 8, матрица B(D) приводится в табл. 2
| x1 | x2 | x3 | x4 |
| v1 | -1 | ||
| v2 | -1 | -1 | |
| v3 | -1 |
По матрице смежности графа (орграфа) всегда можно определить ребра графа (дуги орграфа) как пары инцидентных им вершин, а для псевдографов, кроме того, и кратности ребер (дуг). Однако, если ребра (дуги) были пронумерованы, то восстановить их номера по матрице смежности невозможно невозможно. В этом смысле матрица инцидентности оказывается более информативной, чем матрица смежности, поскольку позволяет получить точную информацию о ребра (дугах), включая их нумерацию.
Заметим, что матрица инциденций сравнительно редко используется, так как в современных условиях (где число ребер часто очень велико) она имеет слишком большое число столбцов.
Пример 10. Для неориентированного графа, изображенного на рис. 9,постройте матрицу смежности и матрицу инцидентности.
рис.9
Решение. Матрица смежности
Матрица инцидентности
Структурная матрица. Именно эта матрица имеет особое значение в теории сетей связи. Структурная матрица – это символьная матрица порядка n. Она составляется следующим образом: на главной диагонали стоит 1, т. е. aij =1, остальные элементы – это символьные обозначения ребер (если вершины i и j не соединены ребром, то aij =0). При этом, если при i<j вершины i и j соединены ребром a, то элемент sij=a, при i>j – это отрицание a, которое обычно отмечаться чертой сверху. Если связи вершины i с вершиной j нет, то соответствующий элемент равен 0, структурная матрица может составляться и для орграфа и для мультиграфа без петель (здесь если два ребра a и b соединяются две вершины, то соответствующий элемент при i <j равен a v b, а при i>j этот элемент равен 
).
Теорема. Для того чтобы найти все пути (прости) из вершины i в вершину j достаточно раскрыть минор M(j,i) структурой матрицы методами булевой алгебры. При этом раскрытие минора производится обычными действиями с определителями, но при этом сложение заменяется дизъюнкцией, умножение – конъюнкцией, знаки умножения на числа не используются.
Пример 11. Пусть дан ориентированный граф (рис. 10), причем ребра a, b, h являются ориентированными (их направление указано стрелками), а остальные ребра не ориентированы. Требуется методами булевой алгебры найти пути и сечения между вершинами 2 и 4.
Составляем структурную матрицу Sзатем вычеркиваем из нее 4-ю строчку и 2-й столбец (тем самым получаем минор M(4,2)):
,
Раскрытие определителей производится по известному правилу: определитель равен сумме (в данном случае дизъюнкции) произведений элементов, умноженных на свои алгебраические 3-го порядка можно пользоваться и правилом треугольника.
Искомые пути, расположенные в порядке прохождения ребер:
Сечения же получатся отрицанием этих путей. Применяя правила да\е Моргана (заменяя конъюнкцию на дизъюнкцию и наоборот), затем раскрывая скобки, получаем: (знаки отрицания опущены во всех равенствах, кроме 1-го):
,
Что нам стоит полином Жегалкина построить…
Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.
Главная особенность этих многочленов состоит в том, что любую булеву функцию можно представить полиномом Жегалкина, причем единственным образом.
Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.
Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.
Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».
Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).
Метод треугольника Паскаля
Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования .
Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.
Шаг 2. Построение треугольника.
Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:
Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.
Продолжаем вычисления, пока в строке не останется лишь одна цифра.
Шаг 3. Построение полинома Жегалкина.
Нас интересует левая сторона треугольника (значения выделены жирным):
Числа на левой стороне (выделены жирным шрифтом) треугольника есть коэффициенты полинома при монотонных конъюнкциях, соответствующих наборам значений переменных.
Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.
Если принцип получения конъюнкций понятен, то столбец с ними можно (даже лучше) не выписывать, а сразу переходить к построению полинома.
Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.
Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
Если переменных в функции не 3, а 4 или больше, то метод работает без изменений, только увеличатся размеры таблиц. Тем не менее, в отличие от метода неопределенных коэффициентов, расчеты можно без особых усилий выполнить на листе бумаги.