Тождественность и двойственность[править | править исходный текст]

Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:

Просмотрев таблицы истинности булевых функций, легко получить такие тождества:

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

(дистрибутивностьконъюнкции и дизъюнкции)

Функция называется двойственной функции , если . Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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