Двойственные функции
Определение. Двойственной для функции f(x1, x2, …, xn) называется функция
Пример 44.
Построить функцию, двойственную данной:
1. f = x Ъ 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). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.
предыдущаяследующая