Функции сохраняющие ноль -T0 и функции

Основные замкнутые классы двоичных функций относительно суперпозиций функций.

Замечание 3

Замечание 3

Введеное отношение между функциями является отношением эквивалентности, и поэтому по основному утверждению разбивает все множество функций на классы эквивалентных функций- любая пара функций из одного и тогоже класса эквивалентны между собой, а любая пара функций из разных классов между собой не эквивалентны.

В дальнейшем будем рассматривать функции с точностью до эквивалентности. То есть под функцией будем понимать класс эквивалентных фукций, в который входит данная функция.

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

Пример 1:

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

Пример 2:

Упражнение

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

Определение: замкнутой системой функции называют систему, замыкание которой совпадает с самой системой .

Пример 3:

Определение: система функций называется полной, если ее замыкание совпадает с классом всех булевых функций.(По другому говоря, с помощью суперпозиций функций из системы можно получить любую булевую функцию.)

Дата добавления: 2017-01-13