2.2.3. Двойственные функции. Принцип двойственности

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

Из определения следует, что для того, чтобы получить таблицу значений двойственной функции , нужно в таблице значений функции (и в части переменных, и в части значений ) заменить все 0 на 1, а все 1 на 0. При этом, правда, порядок следования бинарных наборов в левой части таблицы изменится на обратный по сравнению с исходной таблицей. Чтобы его восстановить, нужно перевернуть все столбцы (в том числе и столбец значений). Таким образом, можно сформулировать следующее правило получения таблицы истинности двойственной функции : нужно (не меняя столбцы аргументов) в столбце значений функции заменить все 0 на 1, а 1 на 0, и перевернуть полученный столбец.

Пример. Пусть , тогда . Таким образом, двойственной функцией к конъюнкции является дизъюнкция.

Поскольку для всех функций очевидно , то обратно: двойственной к дизъюнкции является конъюнкция.

Кроме того, легко видеть, что , ; , ; .

< Предыдущая		Следующая >