Операция двоичного сложения. Многочлен Жегалкина.

В этой лекции рассмотрим операцию, именуемую суммой по модулю 2, а также представим алгоритм построения полинома Жегалкина (алгоритм приведения формулы к алгебраической нормальной форме).

Определение. Двоичным сложением (суммой по модулю 2, сложением по модулю 2, кольцевой суммой или операцией «Исключающее или») называется формула логики высказываний (булева функция), таблица истинности которой представлена в виде

Таблица истинности для двоичного сложения

Таблица истинности суммы по модулю 2 (она же двоичное сложение, сложение по модулю 2, кольцевая сумма или операция «Исключающее или»)

Таким образом, формула логики высказываний (булева функция) «сумма по модулю 2» имеет значение истинности, равное единице, когда истинна первая или вторая логическая переменная, а значение истинности, равное нулю, если обе переменные одновременно имеют одинаковые значения истинности.

Определение. Выражение вида

где соответствующие коэффициенты

а сумма берется по модулю 2 и по всем подмно­жествам множества {1, ... , n}, называется многочленом (полиномом) Жегалкина (в некоторой литературе называется алгебраической нормальной формой (АНФ).

Теорема Жегалкина о представлении любой булевой функции многочленом. Любую формулу логики высказываний (булеву функцию) можно представить единственным многочленом Жегалкина.

Алгоритм построения многочлена Жегалкина (приведения к алгебраической нормальной форме) состоит из следующих этапов.

Этап 1. Необходимо построить таблицу истинности.

Этап 2. Необходимо продолжить таблицу истинности, добавив столбец с треугольником Паскаля: верхняя строка такого треугольника представляет собой строку значений исходной формулы логики высказываний. В каждой строке, начиная со второй, любой элемент треугольника равен сумме по модулю 2 двух соседних эле­ментов предыдущей строки.

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

Этап 4. Соединив знаком конъюнкции переменные, значения которых в наборе равны 1, получаем слагаемое в многочлене Жегалкина. Заметим, что набору 000 соответствует слагаемое 1.

Пример. Для формулы логики высказываний (булевой функции) F = (01011001) определите многочлен Жегалкина (алгебраическую нормальную форму).

Решение. Построим многочлен Жегалкина для формулы логики высказываний F = (01011001). Заполним таблицу, как показано ниже.

Треугольник Паскаля для формулы логики высказываний (булевой функции) F = (01011001)

Поясним, как заполняется таблица.

Первые четыре столбца взяты из условия. В пятом столбце строится треугольник Паскаля. Верхняя строка такого треугольника представляет собой строку значений исходной формулы логики высказываний. В каждой строке, начиная со второй, любой элемент треугольника равен сумме по модулю 2 двух соседних элементов предыдущей строки. Элементы второй строки определяются соотношениями:

0 + 1 = 1,

1 + 0 = 1,

0 + 1 = 1,

1 + 1 = 0,

1 + 0 = 1,

0 + 0 = 0,

0 + 1 = 1.

Аналогично для других (последующих в треугольнике Паскаля) строк.

В шестом столбце указаны конъюнкции переменных, значения которых
в одном из первых трех столбцов равны 1. Набору 000, как ранее было замечено, соответствует 1.

Левая сторона треугольника Паскаля равна 01001010. Единицам этой строки соответствуют слагаемые z, х, ху из шестого столбца. Поэтому многочлен Жегалкина функции формулы логики высказываний F = (01011001) равен

Результирующий полином Жегалкина для формулы логики высказываний F = (01011001)

Упражнение. Для формулы логики высказываний (булевой функции) из таблицы ниже определите многочлен Жегалкина (алгебраическую нормальную форму).

Варианты формул логики высказываний (булевых функций)

Запишите в комментарии под лекцией: Если формула логики высказываний F = (вектор из задания), то её полином Жегалкина равняется: далее запись соответствующего полинома Жегалкина. Пример записи для упражнения 1. Если формула F = (01011001), то её полином Жегалкина равняется: z XOR х XOR xy.