для чего нужен полином жегалкина
Что нам стоит полином Жегалкина построить…
Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.
Главная особенность этих многочленов состоит в том, что любую булеву функцию можно представить полиномом Жегалкина, причем единственным образом.
Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.
Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.
Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».
Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).
Метод треугольника Паскаля
Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования 
.
Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.
Шаг 2. Построение треугольника.
Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:
Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.
Продолжаем вычисления, пока в строке не останется лишь одна цифра.
Шаг 3. Построение полинома Жегалкина.
Нас интересует левая сторона треугольника (значения выделены жирным):
Числа на левой стороне (выделены жирным шрифтом) треугольника есть коэффициенты полинома при монотонных конъюнкциях, соответствующих наборам значений переменных.
Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.
Если принцип получения конъюнкций понятен, то столбец с ними можно (даже лучше) не выписывать, а сразу переходить к построению полинома.
Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.
Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
Если переменных в функции не 3, а 4 или больше, то метод работает без изменений, только увеличатся размеры таблиц. Тем не менее, в отличие от метода неопределенных коэффициентов, расчеты можно без особых усилий выполнить на листе бумаги.
Полином Жегалкина. Методы построения.
$$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
Полином Жегалкина
[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] также называется преобразованием Мёбиуса.
Полином Жегалкина
Содержание:
Канонический полином Жегалкина
Заменив в 
и используя распределительный закон для конъюнкции относительно сложения по модулю два, имеем 
Тогда, учитывая, что 
булеву функцию f можно представить в виде 
причем 
Такое представление булевой функции называется каноническим полиномом Жегалкина.
По этой ссылке вы найдёте полный курс лекций по теории вероятности:
Например, представим в виде полинома Жегалкина булеву функцию, заданную таблично (табл. 4.36).
Найдем ее СДНФ и преобразуем:
Как видим, 
, остальные полиномиальные коэффициенты равны 1. Нули можно не выписывать, а отсутствие слагаемого (конъюнкции) вида 
будет означать, что 
Таким образом, предпоследнее выражение тоже является полиномом Жегалкина.
Итак, с помощью конъюкции и М2 любую логическую функцию можно единственным образом представить в виде многочлена. Иногда можно представить функцию в виде полинома Жегалкина более простым способом. Например, функцию 
будем рыскать в виде многочлена с неопределенными коэффициентами: 
При 
с, откуда 
Наконец, при 
Возможно вам будут полезны данные страницы:
Функциональная замкнутость
Обозначим через 
множество всех функций алгебры логики.
Класс функций 
называется функционально замкнутым, если любая суперпозиция функций этого класса R принадлежит этому же классу.
либо 
Рассмотрим наиболее важные функционально замкнутые классы функций алгебры логики.
Класс функций, сохраняющих константу 0 (
). Так называют функции, для которых выполняется 
. Итак, 
. В строчной записи функции через ее значения они начинаются на 0, например 
Покажем, что
. Действительно, 
Для п аргументов имеется 
функций от п аргументов, сохраняющих константу, поскольку на одном из двоичных наборов, а именно на х = (0. 0), значение/фиксировано, и для функции с п аргументами возможно подобрать лишь 
произвольных наборов аргументов.
Такой класс функционально замкнут по определению, поскольку если 
Класс функций, сохраняющих константу 1 (
). Так называют функции, для которых выполняется 
. Итак, 
В строчной записи функции, сохраняющие константу 1, оканчиваются на 1, например 
Покажем, что 
сохраняет 1. Это можно проверить подстановкой: 
Для К1 справедливо все то же, что и для K0.
Класс самодвойственных функций (
). Функция 
, удовлетворяющая условию 
называется двойственной по отношению к функции 
. Очевидно, что 
Таким образом, если 
т.е. множество булевых функций разбивается на пары взаимно-двойственных функций.
Обратим внимание на свойства важнейших функций 
Подобная двойственность лежит в основе построения противоположных высказываний.
Функция 
называется самодвойственной, если 
. Например, самодвойственна функция 
Самодвойственная функция полностью определяется своими значениями на половине наборов аргументов, поэтому число таких функций при п аргументах равно 
Множество самодвойственных функций образует функционально замкнутый класс.
Пусть 
Обозначим_противоположный элемент на булевом кубе через 
. Тогда
откуда следует, что любая композиция самодвойственных фун: ций не выходит из этого класса.
Класс линейных функций (Ал). Функцию алгебры логики вида, 
называют линейной, если ее канонический полигон
Жегалкина имеет вид многочлена первой степени: 
аналогичного обычному алгебра! ческому многочлену первой степени, но с коэффициентами кх виде 0 или 1. Число таких линейных функций от п аргументе равно 
, при 
их восемь из шестнадцати. Они образуй функционально замкнутый класс. В гл. 1 было доказано это утверх дение для непрерывных линейных отображений одного переме! ного. Можно доказать, что оно справедливо и для композици булевых линейных функций 
Для это1 в многочлен 
нужг подставить многочлены 
затем, используя переместительный и сочетательный законы дг операции суммы по модулю два, привести подобные слагаемы Тогда при каждом аргументе 
будет коэффициег 
который нужно просто вычислить.
Класс монотонных функций (
). В гл. 1 были определены пою тия порядок и упорядоченное множество. Для бесконечных множест это означает возможность введения бинарного отношения 
не более чем счетных — возможность перенумерования элементе и тем самым также введения 
. При этом эталоном сравнения служат натуральные числа.
На множестве В введем полный порядок: 
по аналогии с отношением 
на множестве целых чисел Z. На мне жестве 
введем частичный порядок, означающий, что неравен ство 
выполняется тогда и тольк тогда, когда 
Например, 001100 
00110
Два элемента 
называются сравнимыми между собог если 
. Частичным такой порядок является потом? что не все элементы 
сравнимы. Например, кортежи 1100 и 011 не сравнимы с помощью 
Поэтому не стоит путать частичны порядок 
на и полное упорядочивание, использовавшееся для табличного и строчного задания булевой функции (назове: его здесь). Очевидно, что если 
Функция 
называется монотонной, если для любы двух элементов 
, сравнимых между собой, из 
следует, что 
Монотонными будут 
не является монотон ной.
Монотонные функции также образуют функционально замк нутый класс. Действительно, пусть 
Тогда композиция 
будет иметь вид 
, где 
Пусть 
. Тогда 
и 
( а поскольку g — монотонна, то 
. Подставляя сюда явные выражения для 
, получим 
т.е. монотонную функцию.
Следует отметить свойство монотонных булевых функций одно го и двух аргументов. Поскольку на 
сравнимы лишь 
и 
соответственно, а значения получаются 
, то такие монотонные функции будут сохраняющими 0 и 1, т.е. пересече нием этих двух подклассов.
Каждый из пяти рассмотренных классов функций обладает очен] важным свойством: любая из функций алгебры логики, полученная
Функционально полные системы функций
Систему 5 функций 
алгебры логики называю функционально полной, если любую функцию алгебры логик можно записать с помощью суперпозиции некоторого набора бу левых функций 
Очевидно, что если S — функционально полная система, то добавление любого числа булевых функций не изменит статус системы как функционально полной.
Функционально полная система функций называется базисо! в пространстве 
, если удаление хотя бы одной из функций входящих в нее, превращает эту систему в функционально не полную.
Ранее было доказано, что через функции 
, можно выразить любые функции алгебры логики, приведя их виду СКИФ или СДНФ. Следовательно, система этих трех функ ций полна. Так же мы представляли любую функцию в виде ком позиции суммы по модулю два, конъюнкции и константы 1 (удаление всех 0 приводило к равной функции). Однако это не един ственные возможности для представления функций алгебры логику Оказывается, существует довольно много функционально полны систем.
_Например, булевы функции можно выразить только через 
и 
воспользовавшись правилом Де Моргана и представив one рацию конъюнкции через дизъюнкцию и отрицание, так ка 
Критерий функциональной полноты системы функций сфор мулирован в теореме Поста—Яблонского.
Для того чтобы система S функций 
алгебры логики был функционально полной, необходимо и достаточно, чтобы она содер жала функцию:
Выбор элементарных функций для базиса можно осуществлять с помощью табл. 4.37, где плюсом отмечены свойства, которыми эти функции обладают. В ней приведено распределение различных булевых функций двух переменных по пяти рассмотренным функционально замкнутым классам.
Какое минимальное число булевых функций должен содержать базис?
Просим не путать обозначения функций в этой таблице, например 
с аналогичной нумерацией в подразд. 4.2.
Из табл. 4.37 видно, что каждая из функций 
— стрелка Пирса и 
— штрих Шеффера является минимальным базисом, так как соответствует условиям теоремы Поста—Яблонского. Это подтверждает и возможность выражать эти функции через отрицание, конъюнкцию и дизъюнкцию по формулам:
Таким образом, для описания булевой алгебры достаточно одной функции. Другое дело, что стрелку Пирса и штрих Шеффера трудно интерпретировать в теории множеств и реализовать в виде элементарных логических схем через элементы И — НЕ и ИЛИ НЕ, а формулы и логические схемы, составленные только из них, являются громоздкими.
Вообще говоря, в алгебре логики доказано, что минимальный базис содержит не более четырех функций. Хотя существует базис, который содержит ровно четыре функции и образует функционально полную систему: 
Приведем примеры основных функционально полных систем булевых функций:
и, или, не, которые лежат в основе алгебры высказываний или булевой алгебры, 
Заметим, что полная система функций 
будет избыточной. Действительно, удалив из него одну из функций 
или 
и выразив их с помощью законов Де Моргана через 
или 
соответственно, можно получить новую функционально полную систему с базисом 
соответственно.
Рассматриваемая проблема представления логических функций заключается не только в выборе минимального базиса, но и в выборе формы наиболее экономичного представления этих функций.
Так, совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) менее экономичны, чем некоторые из ДНФ и КНФ, хотя и обладают определенными достоинствами, например дают однозначное представление логической функции. Поэтому одинаково важны обе встречные проблемы: с одной стороны, минимизация булевых функций, т.е. приведение к наиболее экономичному виду, и с другой стороны — придание им совершенного вида, важного в некоторых приложениях, например для получения выводов.
Уточним, что минимальной называется такая форма представления логических функций, которая содержит минимальное количество термов и переменных в термах, а значит, минимальная форма предполагает завершение процесса упрощения.
Можно построить различные формальные системы — алгебры — в зависимости от выбранных в качестве базисных логических операций.
Так, булевы функции вида 
образуют булеву алгебру, а операции дизъюнкции, конъюнкции и отрицания образуют базис булевой алгебры.
Множество булевых функций в базисе 
образуют алгебру Жегалкина, а операции 
и 1 образуют базис Жегалкина. Достоинством алгебры Жегалкина является арифметизация логики, благодаря чему двузначная аристотелева логика нашла свое практическое применение. Поскольку в ней справедлив закон исключенного третьего, то алгебра Жегалкина обладает одной существенной особенностью: она непротиворечива, так как непротиворечива ее система аксиом.
Анализ построения различных алгебр с помощью выбора соответствующего языка дает возможность увидеть принципы построения любой науки вообще.
Выбирая, например, язык будущей системы, примем во внимание структуру любой науки, будь то алгебра, геометрия, математическая логика или языки программирования.
Лекции:
Присылайте задания в любое время дня и ночи в ➔ 
Официальный сайт Брильёновой Натальи Валерьевны преподавателя кафедры информатики и электроники Екатеринбургского государственного института.
Все авторские права на размещённые материалы сохранены за правообладателями этих материалов. Любое коммерческое и/или иное использование кроме предварительного ознакомления материалов сайта natalibrilenova.ru запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.