<<
>>

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*}самодвойственных функций замкнут относительно суперпозиций.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.3.1. Двойственные функции: