дискр мат / Понятие_суперпозиции

3

Понятие двойственности

Определение

Функция называется двойственной по отношению к функции , если

.

Согласно определению, для того, чтобы получить двойственную функцию, в таблице истинности исходной функции все нули заменяем на единицы, а все единицы – на нули.

Пример

,

x	y
0	0	0		1	1	1
0	1	1		1	0	0
1	0	1		0	1	0
1	1	1		0	0	0

Отсюда получаем: , .

Определение

Функция называется самодвойственной, если она равна двойственной.

Пример

x
0	1		1	0
1	0		0	1

Следовательно, тождественная функция и функция отрицания являются самодвойственными.

Поэтому если функция представлена формулой, в которой используются только операции , то для получения двойственной функции нужно конъюнкцию заменить на дизъюнкцию, а дизъюнкцию на конъюнкцию.

Пример

Понятие суперпозиции

Определение

Функция называется суперпозицией функций и функции , если

Не теряя общности, имея возможность добавления и изъятия фиктивных переменных, можем считать, что функции зависят от одного и того же числа переменных.

Пример

Функция

Является суперпозицией функций:

Теорема

Если функция реализована формулой

,то формула

реализует функцию .

Доказательство

Если формула представлена как суперпозиция функций , , то для получения : заменяем на , на на .

3