Монотонная булева функция

Монотонная булева функция — булева функция, которая монотонно возрастает (точнее не убывает) по каждому аргументу. Класс всех монотонных булевых функций является одним из пяти предполных классов булевой логики.

Определение

Булева функция называется монотонной, если из того, что она принимает значение $1$ на некотором наборе аргументов $a$, следует, что она принимает значение $1$ на всяком наборе аргументов $b$, который получается из набора аргументов $a$ путём замены произвольного числа нулей на единицы.

Говорят, что набор $\tilde{\alpha }=({\alpha }_1,...{\alpha }_n)$ предшествует набору $\tilde{\beta }=({\beta }_1,...{\beta }_n)$, $\tilde{\alpha }\preccurlyeq \tilde{\beta }$ ($\tilde{\alpha }$ не больше $\tilde{\beta }$), если ${\alpha }_i⩽{\beta }_i$для всех $i=1,...,n$.

Если $\tilde{\alpha }\preccurlyeq \tilde{\beta }$ и $\tilde{\alpha }\ne \tilde{\beta }$, то говорят, что набор $\tilde{\alpha }$ строго предшествует набору $\tilde{\beta }$, $\tilde{\alpha }\prec \tilde{\beta }$.

Наборы $\tilde{\alpha }$ и $\tilde{\beta }$ называются сравнимыми, если $\tilde{\alpha }\preccurlyeq \tilde{\beta }$ либо $\tilde{\beta }\preccurlyeq \tilde{\alpha }$.

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

Шаблон:РамкаБулева функция $f({\tilde{x}}_n)$ называется монотонной, если для любых двух сравнимых наборов ${\tilde{\alpha }}_n$и ${\tilde{\beta }}_n$ таких, что $\tilde{\alpha }\preccurlyeq \tilde{\beta }$, имеет место неравенство $f({\tilde{\alpha }}_n)⩽f({\tilde{\beta }}_n)$. Шаблон:Конец рамки

Множество всех монотонных функций алгебры логики обозначается через $M$, а множество всех монотонных булевых функций, зависящих от $n$ переменных $M^{(n)}$

Сокращённая ДНФ и КНФ

Единица монотонной функции называется нижней, если на всех наборах меньше неё функция принимает значение $0$.Шаблон:Sfn Двойственно, нуль монотонной функции называется верхним, если на всех наборах больше него функция принимает значение $1$. Любая единица монотонной функции больше некоторой нижней единицы; любой ноль монотонной функции меньше некоторого верхнего нуля. Нижних единиц нет только у функции, тождественно равной $0$ (потому что у неё вообще нет единиц); верхних нулей нет только у функции, тождественно равной $1$ (потому что у неё вообще нет нулей). Монотонная функция полностью определяется множеством своих нижних единиц: она равна $1$ на наборах, для которых существует меньшая нижняя единица, и равна $0$ на наборах, которые меньше любой нижней единицы. Двойственно, монотонная функция полностью определяется множеством своих верхних нулей: она равна $0$ на наборах, для которых существует больший верхний ноль, и равна $1$ на наборах, которые больше любого верхнего нуля. Все нижние единицы монотонной функции всегда несравнимы между собой; все верхние нули монотонной функции также несравнимы между собой. Любое множество несравнимых наборов из $E_2^n$ является множеством нижних единиц некоторой монотонной функции арности $n$, причём только одной. Любое множество несравнимых наборов из $E_2^n$ является множеством верхних нулей некоторой монотонной функции арности $n$, причём только одной. Таким образом, между монотонными функциями и множествами несравнимых наборов есть взаимо-однозначное соответствие, которое монотонной функции сопоставляет множество нижних единиц (или верхних нулей).

Булева функция является монотонной тогда и только тогда, когда её сокращённая ДНФ (КНФ) не содержит отрицаний.Шаблон:Sfn Из этого моментально следует, что $\{\wedge ,\vee ,0,1\}$ порождает все монотонные функции. Для её сокращённых ДНФ и КНФ можно указать явные формулы. Обозначим за $N(f)$ ― множество нижних единиц $f$, а за $M(f)$ — множество верхних нулей. Тогда:

$f(x_1,\dots ,x_n)=\underset{(i_1,\dots ,i_n)\in N(f)}{\bigvee }\underset{i_j=1}{\bigwedge }{x}_j$

— сокращённая ДНФ монотонной функции;Шаблон:Sfn

$f(x_1,\dots ,x_n)=\underset{(i_1,\dots ,i_n)\in M(f)}{\bigwedge }\underset{i_j=0}{\bigvee }{x}_j$

— сокращённая КНФ монотонной функции.

У монотонных функций есть только одна тупиковая ДНФ (КНФ) и она совпадает с сокращённой формой. Поэтому для монотонной функции существует лишь одна простая минимальная ДНФ (КНФ) относительно любого индекса простоты и она совпадает с сокращённой.

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

Множество всех монотонных булевых функций образует замкнутый класс,Шаблон:Sfn предполный в $P_2$. Таким образом, класс монотонных функций является одним из пяти предполных классов булевой логики. Класс монотонных функций обозначается $M$Шаблон:Sfn или $A_1$Шаблон:Sfn (обозначение Поста). В $M$ четыре предполных класса: $D$ (класс дизъюнкций с константами), $K$ (класс конъюнкций с константами), $M\cap T_0$ (класс монотонных, сохраняющих 0) и $M\cap T_1$ (класс монотонных, сохраняющих 1).Шаблон:Sfn Любой собственный подкласс $M$ может быть достроен до предполного в $M$.Шаблон:Sfn Как и для всех замкнутых классов в $P_2$, для класса монотонных функций верен аналог малой теоремы Поста: система монотонных функций полна в $M$ тогда и только тогда, когда в ней содержится не сохраняющая $0$ функция, не сохраняющая $1$ функция, не дизъюнкция или константа и не конъюнкция или константа.

Функции, тождественно равные $0$ и тождественно равные $1$ — монотонны. Все монотонные функции, не сохраняющие $0$, исчерпываются функциями, тождественно равными $1$. Таким образом, множество монотонных функций, сохраняющих $0$, это множество монотонных функций без тождественно равных нулю. Аналогично, все монотонные функции, не сохраняющие $1$, исчерпываются функциями, тождественно равными $0$. Таким образом, множество монотонных функций, сохраняющих $1$, это множество монотонных функций без тождественно равных единице. Из этого следует, что в любой порождающей класс монотонных функций системе всегда есть функция, тождественно равная нулю, и функция, тождественно равная единице.

Двойственная к монотонной функции тоже монотонна, то есть класс $M$ — самодвойственнен. Примеры базисов в $M$: $\{0,1,\wedge ,\vee \},\{0,1,x\wedge y\vee z\}$. Минимальное количество функций в базисе — $3$, максимальное — $4$. В $M$ нет шефферовой функции. Порядок класса линейных функций равен $2$. Все базисы монотонных функций можно поделить на 2 вида:

• $0$, $1$, $x_1\wedge \dots \wedge x_n$, $x_1\vee \dots \vee x_m$;
• $0$, $1$ и функция, не являющаяся конъюнкцией или дизъюнкцией.

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

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

Лемма о немонотонной функции

Лемма о немонотонной функции. Из немонотонной функции и констант $0$ и $1$ можно получить отрицание.Шаблон:Sfn

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

• Функция $f$ является немонотонной тогда и только тогда, когда у неё существуют 2 соседних набора ${\alpha }_i,\dots ,{\alpha }_{i-1},0,{\alpha }_{i+1},\dots ,{\alpha }_n$ и ${\alpha }_i,\dots ,{\alpha }_{i-1},1,{\alpha }_{i+1},\dots ,{\alpha }_n$ такие, что $f({\alpha }_i,\dots ,{\alpha }_{i-1},0,{\alpha }_{i+1},\dots ,{\alpha }_n)=1$, а $f({\alpha }_i,\dots ,{\alpha }_{i-1},1,{\alpha }_{i+1},\dots ,{\alpha }_n)=0$. Другими словами, для немонотонной функции всегда есть два таких соседних набора $\tilde{\alpha }\prec \tilde{\beta }$, что $f(\tilde{\alpha })\succ f(\tilde{\beta })$.Шаблон:Sfn
• Из немонотонной функции можно получить немонотонную функцию от трёх переменных, причём для неё будут выполнены равенства $f(0,0,1)=1,f(0,1,1)=0$.

Второе утверждение следует из первого, а утверждение леммы следует из второго.

См. также

• Предполные классы
• Линейная булева функция

Литература

• Шаблон:Cite web
• Шаблон:Книга