M - класс монотонных функций.

Определение

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

Набор предшествует набору , если одноименные координаты связаны отношением меньше или равно ( …,).

Если хотя бы одна пара координат не связана отношением предшествования, то данные наборы являются несравнимыми.

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

Рис. 1. Диаграмма Хассе

Например, к этому классу относятся функции , , , но не относятся , .

Для определения принадлежности к классу монотонных функций, необходимо в таблице истинности сравнить значения на сравнимых наборах. Для всех сравнимых пар должны выполняться условия: и координаты на бо'льшем наборе не меньше и значение не меньше, чем на меньшем наборе.

Если последовательно рассматривать все сравнимые наборы, используя диаграмму Хассе, то проблем с распознаванием монотонности быть не должно. Пример определения монотонности с последовательным рассмотрением каждого варианта сравнимых наборов представлен на рисунке 2 (рассматриваемая функция является монотонной).

Рис. 2. Пример обнаружения монотонности

Обозначим число монотонных функций через . Точное значение известно только для , поскольку число функций резко возрастает и при n > 8 подсчеты становится проблематичными.

Например, при n = 2 число функций равно 6, при n = 5 – 7581, а при n = 9 число функций превышает 10⁴². Полный список известных значений точного количества монотонных функций представлен в таблице 1.

Таблица 1. Число монотонных функций

Задача вычисления числа булевых функций от n переменных, принадлежащих классу M, оказалась довольно трудной. Эту задачу принято называть проблемой Дедекинда. Известны несколько оценок числа монотонных булевых функций, в зависимости от используемых методов подсчета и сложности вычислений. Например, одна из оценок: где [a] – целая часть числа a.