Полином жегалкина метод треугольника кратко
Обновлено: 05.07.2024
Жегалкин (также Жегалкин, Gégalkine или же Шегалкин [1] ) многочлены образуют одно из многих возможных представлений операций Булева алгебра. Введен русским математиком Иван Иванович Жегалкин в 1927 году они кольцо многочленов над целые числа по модулю 2. В результате вырождения модульная арифметика приводят к тому, что полиномы Жегалкина проще обычных полиномов и не требуют ни коэффициентов, ни показателей. Коэффициенты избыточны, потому что 1 - единственный ненулевой коэффициент. Показатели избыточны, потому что в арифметическом модуле 2 Икс 2 = Икс. Следовательно, такой многочлен, как 3Икс 2 у 5 z конгруэнтно и поэтому может быть переписано как, xyz.
Содержание
Логический эквивалент
До 1927 года булева алгебра считалась исчислением логические значения с логическими операциями соединение, дизъюнкция, отрицаниеи др. Жегалкин показал, что все булевы операции могут быть записаны как обычные числовые многочлены, считая логические константы 0 и 1 целыми числами по модулю 2. Логическая операция соединения реализуется как арифметическая операция умножения. ху, и логично Эксклюзивный или как арифметическое сложение по модулю 2 (здесь записывается как Икс⊕у чтобы избежать путаницы с обычным использованием + в качестве синонима для включающего или ∨). Логическое дополнение ¬Икс тогда получается из 1 и ⊕ как Икс⊕1. Поскольку ∧ и ¬ образуют достаточную основу для всей булевой алгебры, а это означает, что все другие логические операции могут быть получены как составные части этих базовых операций, из этого следует, что многочлены обычной алгебры могут представлять все булевы операции, что позволяет выполнять логические рассуждения. надежно апеллируя к знакомым законам элементарная алгебра без отвлечения внимания на отличия от алгебры средней школы, которые возникают с дизъюнкцией вместо сложения по модулю 2.
Примером приложения является представление логического порога 2 из 3 или средняя операция как полином Жегалкина ху⊕yz⊕zx, который равен 1, если хотя бы две переменные равны 1, и 0 в противном случае.
Формальные свойства
Формально Жегалкин моном является произведением конечного набора различных переменных (следовательно, без квадратов), включая пустое множество, произведение которого обозначено 1. Имеется 2 п возможные одночлены Жегалкина в п переменных, поскольку каждый моном полностью определяется наличием или отсутствием каждой переменной. А Полином Жегалкина является суммой (исключающим ИЛИ) набора мономов Жегалкина, причем пустое множество обозначается как 0. Наличие или отсутствие данного монома в многочлене соответствует коэффициенту этого монома, равному 1 или 0 соответственно. Мономы Жегалкина, будучи линейно независимый, пролет 2 п -размерный векторное пространство над Поле Галуа GF(2) (NB: нет GF(2 п ), чье умножение совершенно иное). 2 2 п векторы этого пространства, то есть линейные комбинации этих одночленов как единичные векторы, составляют многочлены Жегалкина. Точное совпадение с количеством Логические операции на п переменные, которые исчерпывают п-арных операций на , дает прямой счетный аргумент в пользу полноты полиномов Жегалкина как булевого базиса.
Это векторное пространство не эквивалентно свободная булева алгебра на п генераторы, потому что ему не хватает дополнения (побитового логического отрицания) как операции (что эквивалентно, потому что ему не хватает верхнего элемента как константы). Это не означает, что пространство не закрыто из-за дополнений или отсутствует верх ( единичный вектор) как элемент, а то, что линейные преобразования этого и аналогичным образом построенных пространств не должны сохранять дополнение и вершину. Те, которые их сохраняют, соответствуют булевым гомоморфизмам, например существует четыре линейных преобразования из векторного пространства многочленов Жегалкина от одной переменной в пространство без переменных, только два из которых являются булевыми гомоморфизмами.
Метод расчета
Для вычисления полинома Жегалкина обычно используются различные известные методы.
- Используя метод неопределенных коэффициентов
- Построив каноническая дизъюнктивная нормальная форма
- Используя таблицы
- Метод Паскаля
- Метод суммирования
- Использование карты Карно
Метод неопределенных коэффициентов
Методом неопределенных коэффициентов формируется линейная система, состоящая из всех кортежей функции и их значений. Решение линейной системы дает коэффициенты полинома Жегалкина.
Пример
Этот вектор должен быть результатом умножения слева вектора неопределенных коэффициентов.
на 8x8 логическая матрица который представляет возможные значения, которые могут принимать все возможные конъюнкции A, B, C. Эти возможные значения приведены в следующей таблице истинности:
А B C 1 C B B C А А C А B А B C 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 <| c | c | c | c | c | c | c | c | c | c | c | c |>A & B & C & ;;;;;;; & 1 & C & B & BC & A & AC & AB & ABC hline 0 & 0 & 0 && 1 & 0 & 0 & 0 & 0 & 0& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 0 & 1 & 0 && 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 0 & 1 & 1 && 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 1 & 0 & 0 && 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 1 & 0 & 1 && 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0> .
Информация в приведенной выше таблице истинности может быть закодирована в следующей логической матрице:
S 3 = ( 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 ) = 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1end >>
где "S" здесь означает "Серпинский", как в Серпинский треугольник, а нижний индекс 3 дает показатели его размера: 2 3 × 2 3 imes 2 ^ > .
Тогда линейная система есть
который может быть решен для c → >> :
Использование канонической дизъюнктивной нормальной формы
Используя этот метод, каноническая дизъюнктивная нормальная форма (полностью развернутый дизъюнктивная нормальная форма) вычисляется первым. Затем отрицания в этом выражении заменяются эквивалентным выражением с использованием суммы по модулю 2 переменной и 1. Знаки дизъюнкции меняются на сложение по модулю 2, скобки открываются, и результирующее логическое выражение упрощается. Это упрощение приводит к полиному Жегалкина.
Использование таблиц
Обратите внимание, что
это я th коэффициент полинома Жегалкина, литералы которого в я th мономы такие же, как литералы в я th minterm, за исключением того, что отрицательные литералы удаляются (или заменяются на 1).
Ζ-преобразование является само по себе обратным, поэтому такая же таблица может использоваться для вычисления коэффициентов c 0 , . . . , c 2 п − 1 , . c_ -1>> учитывая коэффициенты грамм 0 , . . . , грамм 2 п − 1 , . g_ -1>> . Просто позволь
В терминах таблицы на рисунке скопируйте выходные данные таблицы истинности (в столбец с меткой п) в крайний левый столбец треугольной таблицы. Затем последовательно вычисляйте столбцы слева направо, применяя XOR к каждой паре вертикально смежных ячеек, чтобы заполнить ячейку сразу справа от верхней ячейки каждой пары. Когда вся треугольная таблица заполнена, верхняя строка считывает коэффициенты линейной комбинации, которая при упрощении (удаление нулей) дает многочлен Жегалкина.
Чтобы перейти от полинома Жегалкина к таблице истинности, можно заполнить верхнюю строку треугольной таблицы коэффициентами полинома Жегалкина (добавляя нули для любых комбинаций положительных литералов, не входящих в полином). Затем последовательно вычисляйте строки сверху вниз, применяя XOR к каждой паре горизонтально смежных ячеек, чтобы заполнить ячейку сразу до нижней части крайней левой ячейки каждой пары. Когда вся треугольная таблица заполнена, крайний левый столбец ее можно скопировать в столбец п таблицы истинности.
Отметим, что данный метод расчета соответствует принципу работы элементарный клеточный автомат называется Правило 102. Например, запустите такой клеточный автомат с восемью ячейками, настроенными с выходами таблицы истинности (или коэффициентами канонической дизъюнктивной нормальной формы) логического выражения: 10101001. Затем запустите клеточный автомат еще для семи поколений, сохраняя при этом запись состояния крайней левой ячейки. История этой ячейки тогда оказывается: 11000010, которая показывает коэффициенты соответствующего полинома Жегалкина. [2] [3]
Метод Паскаля
Наиболее экономичным по объему вычислений и целесообразным для построения полинома Жегалкина вручную является метод Паскаля.
Метод суммирования
Графическое представление коэффициентов полинома Жегалкина для функций с различным числом переменных.
По таблице истинности легко вычислить индивидуальные коэффициенты полинома Жегалкина. Для этого просуммируйте по модулю 2 значения функции в тех строках таблицы истинности, где переменные, не входящие в конъюнкцию (которая соответствует вычисляемому коэффициенту), принимают нулевые значения.
Поскольку нет переменных с постоянным членом,
Для члена, который включает все переменные, сумма включает все значения функции:
Представим графически коэффициенты многочлена Жегалкина как суммы по модулю 2 значений функций в определенных точках. Для этого мы строим квадратную таблицу, где каждый столбец представляет значение функции в одной из точек, а строка - коэффициент полинома Жегалкина. Точка на пересечении некоторого столбца и строки означает, что значение функции в этой точке входит в сумму для данного коэффициента полинома (см. Рисунок). Мы называем эту таблицу Т N > , куда N - количество переменных функции.
Теоретико-решеточная интерпретация
Кстати, обратите внимание, что общий рисунок таблицы Т N > это то из логическая матрица Серпинский треугольник. Также шаблон соответствует элементарный клеточный автомат называется Правило 60, начиная с крайней левой ячейки, установленной на 1, а все остальные ячейки очищены.
Использование карты Карно
На рисунке показана функция трех переменных, п(А, B, C) в виде Карта Карно, который читатель может рассматривать как пример преобразования таких отображений в полиномы Жегалкина; общая процедура состоит из следующих шагов:
- Мы рассматриваем все ячейки карты Карно в порядке возрастания количества единиц в их кодах. Для функции трех переменных последовательность ячеек будет 000–100–010–001–110–101–011–111. Каждая ячейка карты Карно связана с членом полинома Жегалкина в зависимости от позиций кода, в которых есть единицы. Например, ячейка 111 соответствует члену ABC, ячейка 101 соответствует члену AC, ячейка 010 соответствует члену B, а ячейка 000 соответствует члену 1.
- Если в рассматриваемой ячейке 0, перейдите к следующей ячейке.
- Если рассматриваемая ячейка равна 1, добавьте соответствующий член к многочлену Жегалкина, затем инвертируйте все ячейки в карте Карно, где этот член равен 1 (или принадлежит идеальный порожденные этим членом в булевой решетке одночленов) и переходят в следующую ячейку. Например, если при рассмотрении ячейки 110 в ней появляется единица, то к полиному Жегалкина добавляется член AB и инвертируются все ячейки карты Карно, для которых A = 1 и B = 1. Если единица находится в ячейке 000, то к полиному Жегалкина добавляется член 1 и инвертируется вся карта Карно.
- Процесс преобразования можно считать завершенным, если после следующей инверсии все ячейки карты Карно становятся нулевыми или не учитываются.
Преобразование Мёбиуса
В Формула обращения Мебиуса связывает коэффициенты булевого выражения суммы минимальных членов и полинома Жегалкина. Это частичный вариант формулы Мёбиуса, а не теоретико-числовой. Формула обращения Мёбиуса для частичных порядков:
Пример
В качестве примера рассмотрим случай с тремя переменными. В следующей таблице показано отношение делимости:
| Икс | делители Икс |
|---|---|
| 000 | 000 |
| 001 | 000, 001 |
| 010 | 000, 010 |
| 011 | 000, 001, 010, 011 |
| 100 | 000, 100 |
| 101 | 000, 001, 100, 101 |
| 110 | 000, 010, 100, 110 |
| 111 | 000, 001, 010, 011, 100, 101, 110, 111 |
Приведенная выше система уравнений может быть решена относительно ж, и результат может быть получен путем обмена грамм и ж во всей вышеупомянутой системе.
В таблице ниже показаны двоичные числа вместе с соответствующими одночленами Жегалкина и булевыми минтермами:
| Логический минтерм | ABC | Жегалкин моном |
|---|---|---|
| А ¯ B ¯ C ¯ > >> | 000 | 1 |
| А ¯ B ¯ C > C> | 001 | C |
| А ¯ B C ¯ B >> | 010 | B |
| А ¯ B C BC> | 011 | до н.э |
| А B ¯ C ¯ | 100 | А |
| А B ¯ C | 101 | AC |
| А B C ¯ | 110 | AB |
| А B C | 111 | ABC |
Мономы Жегалкина естественным образом упорядочены по делимости, тогда как булевы минтермы сами себя упорядочивают не так естественно; каждый представляет собой исключительную восьмую из трех переменных Диаграмма Венна. Порядок мономов переносится на битовые строки следующим образом: задано а 1 а 2 а 3 a_ a_ > и б 1 б 2 б 3 b_ b_ > , пара битовых троек, тогда а 1 а 2 а 3 ≤ б 1 б 2 б 3 ↔ а 1 ≤ б 1 ∧ а 2 ≤ б 2 ∧ а 3 ≤ б 3 a_ a_ leq b_ b_ b_ leftrightarrow a_ leq b_ клин a_ leq b_ клин a_ < 3>leq b_ > .
Тогда соответствие между булевой суммой терминов с тремя переменными и полиномом Жегалкина будет следующим:
Приведенную выше систему уравнений можно резюмировать как логическая матрица уравнение:
( грамм ( 000 ) грамм ( 001 ) грамм ( 010 ) грамм ( 011 ) грамм ( 100 ) грамм ( 101 ) грамм ( 110 ) грамм ( 111 ) ) = ( 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 ) ( ж ( 000 ) ж ( 001 ) ж ( 010 ) ж ( 011 ) ж ( 100 ) ж ( 101 ) ж ( 110 ) ж ( 111 ) ) g (000) g (001) g (010) g (011) g (100) g (101) g (110) g (111) end ) > =
который Н. Дж. Вильдбергер называет преобразованием Буля – Мёбиуса.
Ниже показан «XOR электронная таблицаФорма трансформации, идущая в направлении грамм к ж:
Связанных с работой
В том же году, что и работа Жегалкина (1927 г.), американский математик Эрик Темпл Белл опубликовал сложную арифметизацию булевой алгебры на основе Ричард ДедекиндИдеальная теория и общая модульная арифметика (в отличие от арифметики по модулю 2). Гораздо более простой арифметический характер многочленов Жегалкина был впервые замечен на Западе (независимо, общение между советскими и западными математиками в ту эпоху было очень ограниченным) американским математиком. Маршалл Стоун в 1936 году, когда он заметил, когда писал свой знаменитый Каменная двойственность Теорема о том, что предположительно слабая аналогия между Булевы алгебры и кольца Фактически, его можно было сформулировать как точную эквивалентность как для конечных, так и для бесконечных алгебр, что привело его к существенной реорганизации своей работы в течение следующих нескольких лет.
Полином (многочлен) Жегалкина представляет собой полином, коэффициентами которого являются числа $0$ или $1$, причем в качестве операций умножения и сложения выступают соответственно конъюнкция и сумма по модулю $2$. Например, для булевой функции $f\left(x_1,\ x_2,\ x_3\right)$ от трех переменных $x_1,\ x_2,\ x_3$ полином Жегалкина будет иметь следующий вид:
$$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_x_1x_2\bigoplus a_x_1x_3\bigoplus a_x_2x_3\bigoplus a_x_1x_2x_3.$$
Коэффициенты $a_0,\ a_1,\ \dots ,\ a_\in \left\$, то есть могут принимать значения либо $0$, либо $1$ в зависимости от того, какое значение принимает булева функция $f\left(x_1,\ x_2,\ x_3\right)$ на том или ином наборе значений переменных.
С помощью полинома Жегалкина можно представить любую булеву функцию, причем единственных образом. Поэтому можно сказать, что полином Жегалкина является еще одним способом представления булевых функций в алгебре операций $\bigoplus $ — суммы по модулю $2$, $\cdot $ — конъюнкции и константы $1$.
Операция $\bigoplus $ имеет и другие названия: сумма Жегалкина, неравнозначность, исключающее ИЛИ-НЕ. Иногда, для удобства ее обозначения используют привычную запись сложения $+$, но не стоит путать с дизъюнкцией и, тем более, с обычной арифметической операцией сложения. Таблица истинности данной операции имеет вид:
$$\begin<|c|c|>
\hline
x & y & x\bigoplus y \\
\hline
0 & 0 & 0 \\
\hline
0 & 1 & 1 \\
\hline
1 & 0 & 1 \\
\hline
1 & 1 & 0 \\
\hline
\end$$
Сумма $x\bigoplus y$ принимает истинное значение тогда и только тогда, когда истинно одно и только одно составляющее высказывание. Если сравнить таблицы истинности основных логических операций, то можно заметить, что $x\bigoplus y=\overline
Для двух введенных операций $\bigoplus ,\ \cdot $ (суммы по модулю 2 и конъюнкции) выполняются все логические законы:
- Коммутативность: $x\bigoplus y=y\bigoplus x$;
- Ассоциативность: $\left(x\bigoplus y\right)\bigoplus z=x\bigoplus \left(y\bigoplus z\right)$, то есть результат $x\bigoplus y\bigoplus z$ не зависит от расстановки скобок;
- Дистрибутивность: $x\left(y\bigoplus z\right)=xy\bigoplus xz$;
- $x\bigoplus x=0$;
- $0\bigoplus x=x$;
- $\overline=x\bigoplus 1$.
Для построения полинома Жегалкина можно использовать различные методы:
- Метод неопределенных коэффициентов;
- Метод треугольника Паскаля;
- Преобразование ДНФ;
- Преобразование СДНФ.
Метод неопределенных коэффициентов
Найдем полином Жегалкина для функции $f\left(x_1,\ x_2,\ x_3\right)=\left(x_1x_2\vee x_3\right)\to <\overline
$\begin<|c|c|>
\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)$ трех переменных $x_1,\ x_2,\ x_3$:
$$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_x_1x_2\bigoplus a_x_1x_3\bigoplus a_x_2x_3\bigoplus a_x_1x_2x_3.$$
Последовательно подставляем наборы значений переменных и находим коэффициенты $a_0,\ a_1,\ \dots ,\ a_$.
$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_=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_=0\Rightarrow 1\bigoplus a_=0\Rightarrow a_=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_=1\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_=1\Rightarrow 1\bigoplus a_=1\Rightarrow a_=0;$
$f\left(1,\ 1,\ 0\right)=a_0\bigoplus a_1\bigoplus a_2\bigoplus a_=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_=0\Rightarrow 1\bigoplus a_=0\Rightarrow a_=1;$
$f\left(1,\ 1,\ 1\right)=a_0\bigoplus a_1\bigoplus a_2\bigoplus a_3\bigoplus a_\bigoplus a_\bigoplus a_\bigoplus a_=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus 0\bigoplus 1\bigoplus 0\bigoplus 1\bigoplus a_=0\Rightarrow 1\bigoplus a_=0\Rightarrow a_=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(11101100\right)$. В каждой строке, начиная со второй, любой элемент такого треугольника вычисляется как сумма по модулю $2$ двух соседних элементов предыдущей строки. Так, элементы второй строки: $1\bigoplus 1=0,\ 1\bigoplus 1=0,\ 1\bigoplus 0=1,\ 0\bigoplus 1=1,\ 1\bigoplus 1=0,\ 1\bigoplus 0=1,\ 0\bigoplus 0=0$. Аналогично вычисляются элементы других строк.
Левой стороне треугольника Паскаля соответствуют наборы значений переменных исходной функции $f\left(x_1,\ x_2,\ x_3\right)$. Соединяя знаком конъюнкции переменные, значения которых в наборе равны $1$, мы получим слагаемое в полиноме Жегалкина. Набору $\left(000\right)$ соответствует $1$, набору $\left(001\right)$ соответствует $x_3$, и т.д.
Поскольку единицам левой стороны треугольника соответствуют слагаемые $1,\ x_2x_3,\ x_1x_2,\ 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=1\bigoplus x$ и применяем написанные выше логические законы, получаем:
$\overline<<\overline<<\overline
Преобразование СДНФ
$\begin<|c|c|>
\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$ принимает значение, равное 1. Если значение переменной в этом наборе равно 0, то она берется с отрицанием, если значение переменной равно 1, то переменная берется без отрицание. Соединив знаком конъюнкции переменные соответствующего набора, получим элементарную конъюнкцию. Тогда дизъюнкция всех таких элементарных конъюнкций есть СДНФ.
Чтобы построить полином Жегалкина через СДНФ, необходимо исключить операции дизъюнкции и отрицания, затем раскрыть скобки.
$f\left(x_1,\ x_2,\ x_3\right)=<\overline
Полином Жегалкина — многочлен над кольцом $\mathbb < Z >_2$, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой < АНФ >.
Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина.
Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также < если необходимо >константы
Формально полином Жегалкина можно представить в виде
$ P(X_1 . X_n) = a ~\oplus~ a_1 X_1 ~\oplus~ a_2 X_2 ~\oplus~ . ~\oplus~ a_n X_n ~\oplus~ a_ < 12 >X_1 X_2 ~\oplus~ a_ < 13 >X_1 X_3 ~\oplus~ . ~\oplus~ a_ < 1 . n >X_1 . X_n,$
или в более формализованном виде как:
$P = a \oplus \bigoplus_ < \begin < c >1\leq i_1 Примеры полиномов Жегалкина:
- $ 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) 04 сентября 2016, 20:11 проектирование км, кмд, кж Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв] 0 24236 0
Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида [math]0[/math] и [math]1[/math] , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления функций булевой логики. Полином Жегалкина имеет следующий вид:
[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_ x_n \oplus \ldots \oplus a_ <11\ldots1>x_1 x_2 \ldots x_n [/math]
Содержание
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
- Хотя бы одна функция, не сохраняющая [math]0[/math] ;
- Хотя бы одна функция, не сохраняющая [math]1[/math] ;
- Хотя бы одна нелинейная функция;
- Хотя бы одна немонотонная функция;
- Хотя бы одна несамодвойственная функция.
Исходя из этого, система функций [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] является полной:
На основе этой системы и строятся полиномы Жегалкина.
Заметим, что различных булевых функций от [math]n[/math] переменных [math]2^[/math] штук. При этом конъюнкций вида [math]x_ \ldots x_[/math] существует ровно [math]2^n[/math] , так как из [math]n[/math] возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит [math]0[/math] или [math]1[/math] , то есть существует [math]2^[/math] различных полиномов Жегалкина от [math]n[/math] переменных.
Существует несколько способов построения полинома Жегалкина.
Пусть для функции [math]f(x_1,x_2,\ldots,x_n)[/math] задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что [math] a \oplus 1 = \bar[/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_ \oplus a_ x_1 \oplus a_ x_2 \oplus a_ x_3 \oplus a_ x_4 \oplus a_ x_1 x_2 \oplus a_ x_1 x_3 \oplus a_ x_1 x_4 \oplus a_ x_2 x_3 \oplus a_ x_2 x_4 \oplus a_ x_3 x_4 \oplus a_ x_1 x_2 x_3 \oplus a_ x_1 x_2 x_4 \oplus a_ x_1 x_3 x_4 \oplus a_ x_2 x_3 x_4 \oplus a_ x_1 x_2 x_3 x_4[/math]
Так как [math]f(0,0,0,0) = 0[/math] , то [math]a_ = 0[/math] . Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:
[math]f(1,0,0,0) = a_ \oplus a_ = 1,[/math] следовательно [math]a_ = 1[/math]
[math]f(0,1,0,0) = a_ \oplus a_ = 0,[/math] следовательно [math]a_ = 0[/math]
[math]f(0,0,1,0) = a_ \oplus a_ = 0,[/math] следовательно [math] a_ = 0[/math]
[math]f(0,0,0,1) = a_ \oplus a_ = 0,[/math] следовательно [math] a_ = 0[/math]
[math]f(1,1,0,0) = a_ \oplus a_ \oplus a_ \oplus a_ = 1,[/math] следовательно [math] a_ = 0[/math]
[math]f(1,0,1,0) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]
[math]f(1,0,0,1) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]
[math]f(0,1,1,0) = a_ \oplus a_ \oplus a_ \oplus a_ = 1, [/math] следовательно [math] a_ = 1[/math]
[math]f(0,1,0,1) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 0[/math]
[math]f(0,0,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 0[/math]
[math]f(1,1,1,0) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 1, [/math] следовательно [math] a_ = 0[/math]
[math]f(1,1,0,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 0[/math]
[math]f(1,0,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 1, [/math] следовательно [math] a_ = 0[/math]
[math]f(0,1,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]
[math]f(1,1,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 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 [/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 \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]
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
- Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от [math]000\ldots00[/math] до [math]111\ldots11[/math] .
- Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
- Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
- Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
- Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке [math]111[/math] соответствует член [math]ABC[/math] , ячейке [math]101[/math] — член [math]AC[/math] , ячейке [math]010[/math] — член [math]B[/math] , ячейке [math]000[/math] — член [math]1[/math] и т.д.
- Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных [math]P(A,B,C)[/math] показан на рисунке.
Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца [math]''P''[/math] таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 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,0,1) \oplus P(0,1,1), [/math]
и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.
Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\< 0; 1 \>[/math] . Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
Пусть [math] i = (i_1, i_2, \ldots i_n), \;\; i_k \in \[/math] , и введем обозначение [math] x ^ \sim \left\ x, \;\; i_k=1 \\ 1, \;\; i_k=0 \end\right. [/math]
Тогда полином Жегалкина можно записать как: [math] f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^ \cdot x_2^ \cdot[/math] [math]\ldots[/math] [math]\cdot x_n^[/math] , где [math]\alpha_i \in \< 0; 1 \>[/math] .
Множество коэффициентов [math]\[/math] можно рассматривать как функцию [math]\alpha[/math] , заданной на множестве индексов [math] i = (i_1, i_2, \ldots 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[/math] [math]\ldots[/math] [math]\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_ \alpha_i [/math] [math] (2) [/math] Найдем отображение [math] f \mapsto \alpha[/math] (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).
[math]*[/math] [math]i \succ x[/math] обозначает, что [math]x[/math] "меньше" [math]i[/math] как последовательность бит
Пусть задана функция [math] f [/math] . Тогда функцию [math] \alpha_x [/math] можно найти по формуле: [math]\alpha_x = \bigoplus \limits_
Докажем при помощи индукции по количеству единиц в векторе [math] x [/math] ( иначе говоря, по сумме [math]x_1+x_2+[/math] [math]\ldots[/math] [math]+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_ \alpha_i = \left [ \bigoplus \limits_ \bigoplus \limits_
Рассмотрим сумму [math] \left [ \bigoplus \limits_ \bigoplus \limits_
Отображение [math] f \rightarrow \alpha[/math] также называется преобразованием Мёбиуса.
Видно, что [math] (2) [/math] и [math] (3) [/math] — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию [math]f[/math] . То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
A⊕B=B⊕A
A ⊕ B ⊕ C = C ⊕ A ⊕ B = B ⊕ C ⊕ A =
B ⊕ A ⊕ C = C ⊕ B ⊕ A = A ⊕ C ⊕ B =
(A ⊕ B) ⊕ C = A⊕ (B ⊕ C),
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D = B ⊕ A ⊕ C ⊕ D
- Дистрибутивность конъюнкции относительно суммы по модулю два:
- Сумма по модулю два относительно конъюнкции не дистрибутивна, т. е.:
A ⊕ (B*C) ≠ (A ⊕ B)*(A ⊕ C)
(A*B) ⊕ C ≠ (A ⊕ C)*(A ⊕ B)
A ⊕ A = 0
A ⊕ 0 = A
A ⊕ 1 = ⌐A
1 ⊕ 1 = 0
0 ⊕ 0 = 0
0 ⊕ 1 = 1
Вычислим, например, значение выражения
1⊕0*1⊕1*1=1⊕0⊕1=1⊕1=0.
Полином Жегалкина — полином с коэффициентами вида 0 и 1, в котором конъюнкция используется как произведение, сумма по модулю 2 используется как сложение. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).
Полином Жегалкина имеет вид:
H(x1,x2,…, xn)=C0 ⊕ C1 x1 ⊕C2 x2⊕ Cn xn⊕ C12 x1 x2⊕ C13 x1 x3⊕…⊕ C1…n x1…xn,
где C0, C1, …, C1…n – коэффициенты при переменных 1, x1, x2,…xn, x1x2,…, x1…xn соответственно.
Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.
Доказательство. Любая функция f(x1, x2, …, xn) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2п), отсюда следует утверждение теоремы.
Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.
Для булевых функций двух переменных полином Жегалкина имеет вид:
Определим булевы функции двух переменных через операции алгебры Жегалкина (т. е. через конъюнкцию и сумму по модулю 2).
Предварительно дадим решение простейших уравнений, вытекающих из определения суммы по модулю 2:
Если a ⊕ 1 = 1, то a = 0
Если a ⊕ 0 = 1, то a = 1
Если a ⊕ 1 = 0, то a = 1
Если a ⊕ 0 = 0, то a = 0.
Функция f0(x1,x2)= есть тождественный ноль.
Функция f1(x1,x2)= есть конъюнкция.
Для функции f2(x1,x2)= определим значения коэффициентов полинома Жегалкина:
f2(0,0) = C0=0
f2(0,1) = C0⊕ C2=0
f2(1,0) = C0⊕ C1=1
f2(1,1) = C0⊕ C1⊕ C2⊕ C12=0
Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
- Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000. 00 до 111. 11.
- Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
- Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
- Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
- Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
- Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций. Достоинством метода является то, что при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.
Читайте также: