Материал: LS-Sb89586

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

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

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

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

Например, f (0, 0, 0) = a0 = 0 (значение берем из табл. 3.2).

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

В итоге получим: a3 = 1, a12 = 1, a23 = 1.

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

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

f (x, y, z) x yz x yz xyz xyz (1 x)(1 y)z x(1 y)z xy(1 z) xyzz zx zy xyz zx xyz xy xyz xyz z zy xy .

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

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

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

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

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

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

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

Посмотрим, например, что произойдет с дизъюнкцией при такой замене (табл. 3.4). После инвертирования получается табл. 3.5.

26

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

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

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

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

x y * x y;

x y * xXORy;

xXORy * x y;

(x)* x.

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

Это действие сводится к композиции инвертирования и переворота. Например, для функции со значениями (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 (x, y, z) (y x) (y z) ,

27

то f *(x, y, z) (y x)*XOR(y z)* y x *XOR(y z)* yx XOR yz .

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

3.10.Исследование булевой функции на принадлежность

косновным классам замкнутости

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

Множество функций, сохраняющих 0. Определяется условием f (0, 0, 0) = 0. (Определение приведено для булевых функций от трех переменных, но его легко обобщить на случай произвольного количества переменных.)

Множество функций, сохраняющих 1. Определяется условием f (1, 1, 1) = 1.

Линейные. Множество функций, многочлен Жегалкина которых не содержит произведений.

Монотонные. Выполнено условие: если набор α меньше набора β, то f (α) ≤ f (β).

Уточнение: для сравнения наборов используется правило – набор α меньше набора β тогда и только тогда, когда каждый элемент α не больше соответствующего элемента β и хотя бы один элемент α меньше соответствующего элемента β.

Например, набор (0, 1, 0) меньше набора (1, 1, 1). А про наборы (1, 1, 0) и (1, 0, 1) нельзя сказать, что один меньше другого.

Для проверки функции на монотонность используют рисунок, называе-

мый диаграммой Хассе.

Рис. 3.1

28

Идея здесь состоит в том, чтобы сравнивать не каждые два набора из восьми, а меньшее количество пар. Возле каждого набора переменных пишем значение функции на этом наборе.

При этом если будет нарушение монотонности, оно обнаружится на диа-

Наконец, самодвойственной называют булеву функцию, которая равна двойственной к ней.

Ответ на задачу о проверке принадлежности булевой функции к классам замкнутости записывают таблицей (табл. 3.7).

Здесь T0 означает функции, сохраняющие 0; T1 – функции, сохраняю-

щие 1; L – линейные; M – монотонные; S – самодвойственные.

Ответ в таблице приведен, разумеется, для функции f (x, y, z)

(y x) (y z).

29

Список рекомендуемой литературы

Виноградов И. М. Основы теории чисел. М.: Наука, 1972.

Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. М.: Изд-во. иностр. лит., 1963.

Поздняков С. Н., Рыбин С. В. Дискретная математика. М.: Академия, 2008.

Фудзисава Т. Математика для радиоинженеров. Теория дискретных структур. М.: Радио и связь, 1984.

30