Класс монотонных функций м

Понятие монотонности булевых функций связано с определением отношения предшествования на множестве вершин единичного n-мерного куба.

Два булевых вектора и находятся в отношении предшествования тогда и только тогда, когда одноименные координаты этих векторов находятся в отношении : . например, в случае трех переменных наборы их значений имеют номера от 0 до 7. Соответственно отношение предшествования на этих наборах определяется так:

Отношение предшествования на множестве вершин единичного n-мерного куба при является частичным порядком.

тогда и только тогда, когда на любых наборах значений переменных, находящихся в отношении предшествования, значения функции находятся в отношении :

Очевидно, константы 0 и 1 монотонны. Функция не монотонна, если на нулевом наборе значений переменных ее значение равно 1, но функция не является константой 1, или а функция не является константой 0.

Монотонными являются элементарные функции: . Тогда как .

Мажоритарная функция в соответствии с определением является монотонной, а трехместная функция XOR – нет, , так как, например, , а . Можно также указать и на другие нарушения монотонности этой функции.

Множество всех монотонных функций определим как

Теорема. Класс М замкнут и неполон, т.е. [M]=MP₂.

 Так как тождественная функция монотонна, для доказательства замкнутости достаточно показать, что суперпозиция монотонных функций монотонна. Пусть - m-местная монотонная функция и

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

Возьмем два произвольных набора значений переменных и , находящихся в отношении предшествования, таких, что Согласно определению монотонной функции

и, следовательно,

А так как то монотонность доказана, а значит, доказана и замкнутость класса М. Неполнота М следует из существования немонотонных функций. 

Лемма о немонотонной функции: из произвольной немонотонной функции с помощью подстановки констант и отождествления переменных можно получить функцию отрицания.

 Пусть Это означает, что существуют такие наборы значений переменных, находящихся в отношении предшествования, что а Последнее означает, что Из того, что значения функции на выбранных наборах не равны, следует, что сами наборы также не равны. Пусть расстояние Хемминга между наборами равно 1 и обусловлено различием значений переменной Образуем функцию Тогда Так как функция не монотонна, то

.

Соотношение определяет одноместную функцию отрицания.

Если , то следует рассмотреть последовательно все пары соседних вершин, находящихся в отношении предшествования, начиная с вершины , чтобы найти такую пару, на которой обнаружится нарушение монотонности. После этого задача сводится к предыдущему примеру.

Пример применения леммы о немонотонной функции.

Рассмотрим элементарную булеву функцию , вектор значений которой имеет вид: . Это двуместная функция, нулевой набор предшествует второму, расстояние Хемминга между ними равно 1 по первой переменной и . Вторая переменная в обоих наборах равна 0, а первая принимает оба возможных значения (мелькает). «Работа» леммы над этой функцией представлена ниже:

.

В формуле, которая задает рассматриваемую булеву функцию, тем переменным, которые не меняют значение в сравниваемых соседних наборах, на которых происходит нарушение монотонности, присваиваются значения этих переменных. Единственная переменная, изменяющая значение на рассматриваемой паре соседних векторов, получает значение x.

В соответствии с леммой о немонотонной функции при этом будет получена одноместная функция отрицания.

