Пример 3. Замкнутые классы и монотонные функции

Замкнутые классы и монотонные функции

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

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

а) Множество всех дизъюнкций, то есть функций вида является замкнутым классом.

б) Множество всех линейных функций является замкнутым классом, так как подстановка формул вида после преобразований даёт формулу такого же вида.

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

Ранее рассматривалось отношение частичного порядка на множестве векторов одинаковой длины. Напомним, что для векторов и выполняется , если для любого выполняется . Здесь воспользуемся этим отношением для двоичных векторов.

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