2015-04-01
557
а) Множество всех линейных функций является замкнутым классом, так как подстановка формул вида 
в формулу такого же вида снова дает формулу того же вида.
б) Аналогично множество всех дизъюнкций, то есть, функций вида 
является замкнутым классом.
Важным примером замкнутого класса является класс монотонных функций. Для определения монотонной функции введем отношение частичного порядка 
на множестве векторов одинаковой длины. Для двух векторов 
и 
, если и только если 
для всех 
.
Например (6,0.3,-9) < (7, 0.3,-4); (0,1,1) < (1,1,1), а вектора (0,1,1) и (1,0,1), (6,0.3,-9) и (7,0,-9) не сравнимы.
Воспользуемся этим отношением для двоичных векторов.
Функция 
называется монотонной, если для любых двоичных векторов 
и 
длины 
из того, что , следует, что 
.
