Принцип двойственности

ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И

КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ

План лекции:

1. Принцип двойственности.

2. Разложение булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы.

Принцип двойственности

Функция , равная , называется двойственной функцией к функции .

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

Легко установить для функций 0, 1, , , , , что

1) функция 0 двойственна 1;

2) функция 1 двойственна 0;

3) функция двойственна ;

4) функция двойственна ;

5) функция двойственна ;

6) функция двойственна.

Из определения двойственности следует, что

,

т. е. функция является двойственной к (свойство взаимности).

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

Формулу будем называть формулой, двойственной к .

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

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

.

Тогда

т. е. функция получается из в результате той же самой подстановки переменных.

Доказательство справедливости принципа двойственности для шага проведем на примере. Пусть

.

Тогда

т. е. функция получается из и так же, как функция из и .

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

Пример 1. Из тождества следует тождество .

Действительно,

; ; .

Пример 2. Построение формулы для отрицания функции.

Из определения двойственной функции следует

.

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

Найдем отрицание для функции .

Так как , то .