Многочлен Жегалкина

Многочлен Жегалкина – это представление булевой функции в виде арифметического выражения, а точнее – в виде многочлена , причём значения переменных x, y, z и значения полученных выражений рассматриваются в кольце вычетов по модулю 2. При этом каждое чётное число заменяют 0, а каждое нечётное – 1.

Есть несколько способов вычисления этих коэффициентов, мы рассмотрим два способа.

Первый способ: метод неопределённых коэффициентов.

Подставим в многочлен все возможные наборы x, y, z и получим 8 условий на 8 коэффициентов. При этом матрица системы будет содержать много нулей.

Например, f (0, 0, 0) = a₀ = 0 (значение берём из таблицы истинности).

Далее, f (0, 0, 1) = a₀ + a₃ = 1, поэтому a₃ = 1. И так далее, на каждом уравнении будем получать новый коэффициент.

В итоге получим: a₃ = 1, a₁₂ = 1, a₂₃ = 1.

Тогда многочлен Жегалкина имеет вид: z + xy + yz.

Второй способ: использование СДНФ.

Как и следовало ожидать, ответ для второго способа вычисления многочлена Жегалкина совпал с ответом для первого способа.

Если эти ответы различаются, необходимо проверить выкладки.

В ответе с многочленом Жегалкина принято записывать слагаемые в лексикографическом порядке.

Двойственная функция

Определение. Пусть f – некоторая булева функция. Тогда двойственной к f (обозначается f*) называют функцию, таблица истинности которой получается из таблицы истинности f заменой всех 0 на 1, а всех 1 на 0.

Такую операцию называют инвертированием таблицы истинности.

Примечание.

Инвертирование происходит не только со значениями функции, но и со значениями x и y. Поэтому после построения таблицы её нужно будет «перевернуть», то есть переставить все строки в обратном порядке.

Посмотрим, например, что произойдёт с дизъюнкцией при такой замене.

x	y
0	0	0
0	1	0
1	0	0
1	1	1

После инвертирования таблицы

x	y	*
1	1	1
1	0	1
0	1	1
0	0	0

Поскольку в таблице истинности записывают значения переменных в лексикографическом порядке, таблицу следует перевернуть.

x	y	*
0	0	0
0	1	1
1	0	1
1	1	1

Из полученной таблицы видно, что значения функции, двойственной к конъюнкции, совпали со значениями дизъюнкции.

Следовательно, .

Аналогично можно обосновать такие равенства.

Нахождение таблицы значений функции, двойственной к данной булевой функции

Это действие сводится к композиции инвертирования и переворота.

Например, для функции со значениями (0, 1, 0, 0, 0, 1, 1, 1) значения двойственной можно получить следующим образом.

Инвертирование (1, 0, 1, 1, 1, 0, 0, 0).

Переворот (0, 0, 0, 1, 1, 1, 0, 1).

То есть значения двойственной функции будут такими: (0, 0, 0, 1, 1, 1, 0, 1).

Гораздо более творческое задание – получить формулу для функции, двойственной к данной булевой функции, используя теорему о двойственной к суперпозиции функций.

При этом используется следующая идея.

Если α и β – две булевы функции, то, например, . Аналогично вычисляется двойственная для других выражений, например, XOR заменяют эквивалентностью, а эквивалентность – XOR.

Например, если , то

Для самопроверки следует построить таблицу значений этой функции и сравнить с таблицей для f*, полученной композицией инверсии и переворота.