M - класс монотонных функций.
Определение
Булева функция f(x1,...,xn) называется монотонной,
если для любой пары наборов
и
,
из которых набор
предшествует набору
,
выполняется неравенство
.
Набор
предшествует набору
,
если одноименные координаты связаны отношением меньше или равно
(
…,
).
Если хотя бы одна пара координат не связана отношением предшествования, то данные наборы являются несравнимыми.
На рисунке представлены диаграммы Хассе со сравнимыми наборами для функций двух,
трёх и четырёх переменных. Дугами соединены сравнимые наборы, а так как они расположены в порядке возрастания,
то являются предшествующими.
Рис. 1. Диаграмма Хассе
Например, к этому классу относятся функции
,
,
, но не относятся
,
.
Для определения принадлежности к классу монотонных функций, необходимо в таблице истинности сравнить значения
на сравнимых наборах. Для всех сравнимых пар должны выполняться условия: и координаты на бо'льшем наборе не меньше и значение не меньше,
чем на меньшем наборе.
Если последовательно рассматривать все сравнимые наборы, используя диаграмму Хассе, то проблем с распознаванием монотонности быть не должно.
Пример определения монотонности с последовательным рассмотрением каждого варианта сравнимых наборов представлен на рисунке 2 (рассматриваемая функция является монотонной).
Рис. 2. Пример обнаружения монотонности
Обозначим число монотонных функций через
.
Точное значение
известно только для
,
поскольку число функций резко возрастает и при n > 8 подсчеты становится проблематичными.
Например, при n = 2 число функций равно 6, при n = 5 – 7581, а при n = 9 число функций превышает 1042.
Полный список известных значений точного количества монотонных функций представлен в таблице 1.
Таблица 1. Число монотонных функций
Задача вычисления числа булевых функций от n переменных, принадлежащих классу M, оказалась довольно трудной.
Эту задачу принято называть проблемой Дедекинда. Известны несколько оценок числа монотонных булевых функций, в зависимости от используемых методов подсчета и сложности вычислений.
Например, одна из оценок:
где [a] – целая часть числа a.