- Классы ФАЛ. Монотонные функции, их свойства.
Определение. Функция f называется монотонной, если для любых двух наборов значений входных переменных a и b из того, что a³b, следует, что f(a)³f(b).
Свойства монотонных функций.
Нулевой набор значений сравним с любым набором, и является меньшим любого из них. Значит, если монотонная функция равна единице на этом наборе, то она равна единице и на любом наборе, т.е. равна константе. Точно так же, если на единичном наборе значений монотонная функция равна нулю, то она не может быть единицей ни на каком наборе, так как единичный набор больше всякого другого набора.
Пусть функция на наборе a, отличном от единичного, равна 1, и пусть значение i-ой компоненты в нём равно 0. Это значит, что на наборе, который отличается только тем, что i-ая переменная в нём равна 1, функция тоже примет единичное значение. Это означает, что конъюнкции в ДНФ, соответствующие этим наборам, можно склеить по переменной xi. Точно так же, для набора со значением переменной 0 (т.е. с возможным значением в конъюнкции переменной с инверсией) найдётся набор со значением переменной 1, что приведёт к склеиванию по этой переменной. Следовательно, в минимальной ДНФ монотонной функции нет переменных в инверсной форме.
Из этого свойства можно вывести, что суперпозиция монотонных функций снова будет монотонной функцией, т.е. множества монотонных функций образует класс монотонных функций, обозначаемый как M. Базис класса М образуют обе константы и пара функций – конъюнкция и дизъюнкция, т.е. множество {x×y, xÚy, 0,1}.