2.2.3.1. Двойственные функции
Определение. Двойственной для функции f(x1, x2, …, xn) называется функция
Пример 44.
Построить функцию, двойственную данной:
1.
f = x U y;2. f = x® y.
Решение.
1.
2.
Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.
Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция тоже самодвойственна.
Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
Противоположными называются те наборы, которые в сумме дают двоичный код числа (2n-1).
Пример 45.
Выяснить являются ли функции самодвойственными:
1. ;
2. f = 01110010.
Решение.
1. Строим таблицу истинности для данной функции (табл. 55):
Таблица 55
№ | x | y | z | ||||
0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
2 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
3 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
4 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
5 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
6 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
7 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.
2.
Строим таблицу значений для функции f = 01110001 (табл. 56).Таблица 56
№ | x | y | z | f(x, y, z) |
0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 1 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 1 | 1 | 1 |
4 | 1 | 0 | 0 | 0 |
5 | 1 | 0 | 1 | 0 |
6 | 1 | 1 | 0 | 0 |
7 | 1 | 1 | 1 | 1 |
Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.
Теорема. Класс S = {f | f = f*}самодвойственных функций замкнут относительно суперпозиций.