Полином Жегалкина. Методы построения.
$$f\left(x_1,\ x_2,\ x_3\right)=a_0\bigoplus a_1x_1\bigoplus a_2x_2\bigoplus a_3x_3\bigoplus a_<12>x_1x_2\bigoplus a_<13>x_1x_3\bigoplus a_<23>x_2x_3\bigoplus a_<123>x_1x_2x_3.$$
$$\begin
\hline
x & y & x\bigoplus y \\
\hline
0 & 0 & 0 \\
\hline
0 & 1 & 1 \\
\hline
1 & 0 & 1 \\
\hline
1 & 1 & 0 \\
\hline
\end
Для построения полинома Жегалкина можно использовать различные методы:
Метод неопределенных коэффициентов
$\begin
\hline
x_1 & x_2 & x_3 & x_1x_2 & x_1x_2\vee x_3 & f\left(x_1,\ x_2,\ x_3\right)=\left(x_1x_2\vee x_3\right)\to <\overline
0 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 0 & 1 & 1 \\
\hline
0 & 1 & 0 & 0 & 0 & 1 \\
\hline
0 & 1 & 1 & 0 & 1 & 0 \\
\hline
1 & 0 & 0 & 0 & 0 & 1 \\
\hline
1 & 0 & 1 & 0 & 1 & 1 \\
\hline
1 & 1 & 0 & 1 & 1 & 0 \\
\hline
1 & 1 & 1 & 1 & 1 & 0 \\
\hline
\end
$$f\left(x_1,\ x_2,\ x_3\right)=a_0\bigoplus a_1x_1\bigoplus a_2x_2\bigoplus a_3x_3\bigoplus a_<12>x_1x_2\bigoplus a_<13>x_1x_3\bigoplus a_<23>x_2x_3\bigoplus a_<123>x_1x_2x_3.$$
$f\left(0,\ 0,\ 0\right)=a_0=1;$
$f\left(0,\ 0,\ 1\right)=a_0\bigoplus a_3=1\Rightarrow 1\bigoplus a_3=1\Rightarrow a_3=0;$
$f\left(0,\ 1,\ 0\right)=a_0\bigoplus a_2=1\Rightarrow 1\bigoplus a_2=1\Rightarrow a_2=0;$
$f\left(0,\ 1,\ 1\right)=a_0\bigoplus a_2\bigoplus a_3\bigoplus a_<23>=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_<23>=0\Rightarrow 1\bigoplus a_<23>=0\Rightarrow a_<23>=1;$
$f\left(1,\ 0,\ 0\right)=a_0\bigoplus a_1=1\Rightarrow 1\bigoplus a_1=1\Rightarrow a_1=0.$
$f\left(1,\ 0,\ 1\right)=a_0\bigoplus a_1\bigoplus a_3\bigoplus a_<13>=1\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_<13>=1\Rightarrow 1\bigoplus a_<13>=1\Rightarrow a_<13>=0;$
$f\left(1,\ 1,\ 0\right)=a_0\bigoplus a_1\bigoplus a_2\bigoplus a_<12>=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_<12>=0\Rightarrow 1\bigoplus a_<12>=0\Rightarrow a_<12>=1;$
$f\left(1,\ 1,\ 1\right)=a_0\bigoplus a_1\bigoplus a_2\bigoplus a_3\bigoplus a_<12>\bigoplus a_<13>\bigoplus a_<23>\bigoplus a_<123>=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus 0\bigoplus 1\bigoplus 0\bigoplus 1\bigoplus a_<123>=0\Rightarrow 1\bigoplus a_<123>=0\Rightarrow a_<123>=1;$
Подставляя найденные коэффициенты, получаем полином Жегалкина:
$$f\left(x_1,\ x_2,\ x_3\right)=1\bigoplus x_1x_2\bigoplus x_2x_3\bigoplus x_1x_2x_3.$$
Метод треугольника Паскаля
Построим полином Жегалкина для функции из предыдущего метода, используя треугольник Паскаля.
$$f\left(x_1,\ x_2,\ x_3\right)=1\bigoplus x_2x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3.$$
Преобразование ДНФ
Используя основные законы алгебры логики, приведем сначала данную функцию к ДНФ.
Далее в полученной ДНФ необходимо «избавиться» от дизъюнкции, используя законы де Моргана:
$\overline<<\overline<<\overline
Преобразование СДНФ
$\begin
\hline
x_1 & x_2 & x_3 & f\left(x_1,\ x_2,\ x_3\right) \\
\hline
0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 1 \\
\hline
0 & 1 & 0 & 1 \\
\hline
0 & 1 & 1 & 0 \\
\hline
1 & 0 & 0 & 1 \\
\hline
1 & 0 & 1 & 1 \\
\hline
1 & 1 & 0 & 0 \\
\hline
1 & 1 & 1 & 0 \\
\hline
\end
Чтобы построить полином Жегалкина через СДНФ, необходимо исключить операции дизъюнкции и отрицания, затем раскрыть скобки.
$f\left(x_1,\ x_2,\ x_3\right)=<\overline
Что нам стоит полином Жегалкина построить…
Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.
Главная особенность этих многочленов состоит в том, что любую булеву функцию можно представить полиномом Жегалкина, причем единственным образом.
Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.
Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.
Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».
Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).
Метод треугольника Паскаля
Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования 
.
Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.
Шаг 2. Построение треугольника.
Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:
Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.
Продолжаем вычисления, пока в строке не останется лишь одна цифра.
Шаг 3. Построение полинома Жегалкина.
Нас интересует левая сторона треугольника (значения выделены жирным):
Числа на левой стороне (выделены жирным шрифтом) треугольника есть коэффициенты полинома при монотонных конъюнкциях, соответствующих наборам значений переменных.
Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.
Если принцип получения конъюнкций понятен, то столбец с ними можно (даже лучше) не выписывать, а сразу переходить к построению полинома.
Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.
Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
Если переменных в функции не 3, а 4 или больше, то метод работает без изменений, только увеличатся размеры таблиц. Тем не менее, в отличие от метода неопределенных коэффициентов, расчеты можно без особых усилий выполнить на листе бумаги.
Полином Жегалкина
[math]P = a_ <000\ldots000>\oplus a_ <100\ldots0>x_1 \oplus a_ <010\ldots0>x_2 \oplus \ldots \oplus a_ <00\ldots01>x_n \oplus a_ <110\ldots0>x_1 x_2 \oplus \ldots \oplus a_ <00\ldots011>x_
Содержание
Полнота [ править ]
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
Исходя из этого, система функций [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] является полной:
| [math]x_0[/math] | [math]x_1[/math] | [math]\ldots[/math] | [math]x_n[/math] | [math]1[/math] | [math]\land[/math] | [math]\oplus[/math] |
|---|---|---|---|---|---|---|
| [math]0[/math] | [math]0[/math] | [math]\ldots[/math] | [math]0[/math] | [math]1[/math] | [math]0[/math] | [math]0[/math] |
| [math]1[/math] | [math]0[/math] | [math]\ldots[/math] | [math]0[/math] | [math]1[/math] | [math]0[/math] | [math]1[/math] |
| [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] |
| [math]1[/math] | [math]1[/math] | [math]\ldots[/math] | [math]1[/math] | [math]1[/math] | [math]1[/math] | [math]0[/math] |
| Сохраняет 0 | [math]0[/math] | [math]1[/math] | [math]1[/math] | |||
| Сохраняет 1 | [math]1[/math] | [math]1[/math] | [math]0[/math] | |||
| Самодвойственная | [math]0[/math] | [math]0[/math] | [math]0[/math] | |||
| Монотонная | [math]1[/math] | [math]1[/math] | [math]0[/math] | |||
| Линейная | [math]1[/math] | [math]0[/math] | [math]1[/math] | |||
На основе этой системы и строятся полиномы Жегалкина.
Существование и единственность представления (теорема Жегалкина) [ править ]
Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
Построение полинома Жегалкина [ править ]
Существует несколько способов построения полинома Жегалкина.
По таблице истинности [ править ]
Пример: Дана функция [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(1,0,0,0) = a_ <0000>\oplus a_ <1000>= 1,[/math] следовательно [math]a_ <1000>= 1[/math]
[math]f(0,1,0,0) = a_ <0000>\oplus a_ <0100>= 0,[/math] следовательно [math]a_ <0100>= 0[/math]
[math]f(0,0,1,0) = a_ <0000>\oplus a_ <0010>= 0,[/math] следовательно [math] a_ <0010>= 0[/math]
[math]f(0,0,0,1) = a_ <0000>\oplus a_ <0001>= 0,[/math] следовательно [math] a_ <0001>= 0[/math]
[math]f(1,1,0,0) = a_ <0000>\oplus a_ <1000>\oplus a_ <0100>\oplus a_ <1100>= 1,[/math] следовательно [math] a_ <1100>= 0[/math]
[math]f(1,0,1,0) = a_ <0000>\oplus a_ <1000>\oplus a_ <0010>\oplus a_ <1010>= 0, [/math] следовательно [math] a_ <1010>= 1[/math]
[math]f(1,0,0,1) = a_ <0000>\oplus a_ <1000>\oplus a_ <0001>\oplus a_ <1001>= 0, [/math] следовательно [math] a_ <1001>= 1[/math]
[math]f(0,1,1,0) = a_ <0000>\oplus a_ <0100>\oplus a_ <0010>\oplus a_ <0110>= 1, [/math] следовательно [math] a_ <0110>= 1[/math]
[math]f(0,1,0,1) = a_ <0000>\oplus a_ <0100>\oplus a_ <0001>\oplus a_ <0101>= 0, [/math] следовательно [math] a_ <0101>= 0[/math]
[math]f(0,0,1,1) = a_ <0000>\oplus a_ <0010>\oplus a_ <0001>\oplus a_ <0011>= 0, [/math] следовательно [math] 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, [/math] следовательно [math] 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, [/math] следовательно [math] 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, [/math] следовательно [math] 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, [/math] следовательно [math] 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, [/math] следовательно [math] 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]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 \oplus x_1 x_2 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) + 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]
Метод треугольника [ править ]
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных [math]P(A,B,C)[/math] показан на рисунке.
Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца [math]»P»[/math] таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.
[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,0,1) \oplus P(0,1,1), [/math]
и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.
Преобразование Мёбиуса [ править ]
[math]*[/math] [math]i \succ x[/math] обозначает, что [math]x[/math] «меньше» [math]i[/math] как последовательность бит
Отображение [math] f \rightarrow \alpha[/math] также называется преобразованием Мёбиуса.
Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина.
Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также < если необходимо >константы
Формально полином Жегалкина можно представить в виде
или в более формализованном виде как:
$P = a \oplus \bigoplus_ < \begin
Полнота
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
| $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$ |
На основе этой системы и строятся полиномы Жегалкина.
Существование и единственность представления
Теорема Жегалкина: Каждая булева функция единственным образом представляется в виде полинома Жегалкина.
Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него < любой один, если таких несколько >. Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
Построение полинома Жегалкина
Существует несколько способов построения полинома Жегалкина.
По таблице истинности
| $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(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$
Преобразование дизъюнктивной нормальной формы
Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.
Запишем функцию так:
$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)$
$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$
$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$
Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.