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

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

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

Примечание.

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

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

x	y

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

x	y	*

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

x	y	*

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

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

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