f(x1,...,
xn) называется
двойственной к функции f(x1,..., xn).
Существует еще один способ для получения тождеств, который основан на использовании принципа двойственности.
| Определение |
|---|
|
Функция [f (x1,..., xn)]*, равная
f(x1,...,
xn) называется
двойственной к функции f(x1,..., xn).
|
Очевидно, что таблица для двойственной функции получается (при выбранном
порядке наборов) получается из таблицы для функции f(x1,...,
xn) инвертированием (т. е. заменой 0 на 1 и 1 на 0) столбца
функции и его переворачиванием.
Легко видеть, что среди функций 0, 1, x, x,
x1 & x2, x1 
x2
функция 0 двойственна 1,
функция 1 двойственна 0,
функция х двойственна х,
функция x двойственна x,
функция x1 & x2 двойственна x1 x2,
функция x1 x2 двойственна x1 & x2.
Из определения двойственности вытекает, что
f** = (f*)* = f,
т. е. функция f является двойственной к f* (свойство взаимности).
Принцип двойственности.
Если формула U=C[f1,..., fs] реализует функцию
f(x1,..., xn), то формула
C[f*1,..., f*s], т. е. формула,
полученная из U заменой функций f1,..., fs
на f*1,..., f*s
реализует функцию f*(x1,..., xn).
Эту формулу будем называть формулой, двойственной к U и обозначать U*.
Для формул над множеством Р = {0, 1, x, x,
x1 & x2, x1 x2}
принцип двойственности может быть сформулирован так:
для получения формулы. U*, двойственной к формуле U надо в формуле
U всюду заменить 0 на 1, 1на 0, & на , на &,
или,
если U = С [0, 1, x, x1 & x2,
x1 x2 }, то U* =
С [1, 0, x, x1 x2,
x1 & x2 }
Из принципа двойственности вытекает, что если
f (x1,..., xn) = g (x1,..., xn)
то
f*(x1,..., xn) =
g*(x1,..., xn)
Принцип двойственности позволяет быстрее выводить тождества при рассмотрении
элементарных функций и зная только половину законов логики легко получать
остальные.
Упражнения