Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

16 4. Принцип двойственности. СДНФ. Разложение булевых функций по переменным Принцип двойственности Определение: Функция f * (x 1 ,…,x n ) , равная 1 ( ,..., ) n f x x , называется двойственной функцией к функции f(x 1 ,…,x n ) . Очевидно, что таблица для двойственной функции (при фиксированном порядке наборов значений переменных) получается из таблицы для функции f(x 1 ,…,x n ) инвертированием (т.е. заменой 0 на 1 и 1 на 0 ) столбца функции и его переворачиванием (таблицы 4.1 и 4.2). Таблица 4.1. x f 0 f 1 f 2 f 3 f 0 * f 1 * f 2 * f 3 * 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 Таблица 4.2. x 1 x 2 f 0 f 3 f 0 * f 3 * 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 Из таблиц видно, что функция 0 двойственна функции 1 , функция 1 двойственна функции 0 , функция x двойственна функции x, функция x двойственна функции x , функция 1 2 x x  двойственна функции 1 2 x x  , функция 1 2 x x  двойственна функции 1 2 x x  . Функция, двойственная самой себе, является самодвойственной. Т.о. х и x являются самодвойственными функциями.