2.2.3.3. Монотонные функции
Определение. Если a = (a1, …, an) и b = (b1, …, bn) - наборы длины n из 0 и 1, то a £ b, если a1 £ b1, …, an £ bn.
Пример 47.
Наборы ( 0, 1, 0) и (1, 1, 0) сравнимы, причем ( 0, 1, 0) £ (1, 1, 0).
Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и ( 1, 1, 0).
Определение. Функция f(x1, x2, …, xn) называется монотонной, если для всяких наборов a = (a1, …, an) и b = (b1, …, bn) условие a £ b влечет f(a) £ f(b).
Утверждение. Функция монотонна тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.
Следствие. Функция монотонна тогда и только тогда, когда ее МДНФ не содержит отрицаний.
Пример 48.
Выяснить, являются ли функции монотонными: f = 00100110; f = 00110111.
Решение.
1. Сокращенная ДНФ для функции f = 00100110 имеет вид Поскольку сокращенная ДНФ содержит отрицания, то функция не является монотонной.
2. Сокращенная ДНФ для функции f = 00110111 имеет вид Поскольку сокращенная ДНФ не содержит отрицаний, то функция является монотонной.
Теорема. Класс M = {f | a£ b ? f(a)£ f(b)} монотонных функций замкнут относительно суперпозиций.