Определение

Булевская функция f (x ₁ ,..., x_n) называется монотонной, если для любых наборов и , для которых , справедливо неравенство .

Множество всех монотонных булевских функций обозначается как M.

Примеры.

1. Функция f (x ₁, x ₂)= x ₁ ® x ₂ немонотонна, так как

(0, 0) (1, 0), но f (0, 0) > f (1, 0).

2. Функции & и являются монотонными.

Множество всех монотонных функций является замкнутым классом. Поскольку тождественная функция f (x) = x - монотонна, то для доказательства замкнутости M достаточно проверить, что при

h = (1),

где f, g ₁,..., g _n - монотонные функции, M.

Пусть x ₁,..., x_n все различные символы переменных, которые встречаются в формуле (1). Возьмем два набора и значений этих переменных, для которых . Тогда для наборов и , составленных из значений переменных функций g ₁,..., g_n, взятых из наборов и , справедливы соотношения:

Следовательно, для i = 1,..., n. Поэтому . Поскольку M, то , т.е. . Поэтому M.

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

.

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

Лемма. (О немонотонной функции)

Если M, то подстановкой вместо переменных этой функции функций-констант и тождественной функции f (x) = x можно получить функцию .