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

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

Определение

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

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

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

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

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

Булева функция ${\displaystyle f({\tilde {x}}_{n})}$ называется монотонной, если для любых двух сравнимых наборов ${\displaystyle {\tilde {\alpha }}_{n}}$и ${\displaystyle {\tilde {\beta }}_{n}}$ таких, что ${\displaystyle {\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}}$, имеет место неравенство ${\displaystyle f({\tilde {\alpha }}_{n})\leqslant f({\tilde {\beta }}_{n})}$.[2]

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

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

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

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

${\displaystyle f(x_{1},\ldots ,x_{n})=\bigvee _{(i_{1},\ldots ,i_{n})\in N(f)}\quad \bigwedge _{i_{j}=1}x_{j}}$

— сокращённая ДНФ монотонной функции;[5]

${\displaystyle f(x_{1},\ldots ,x_{n})=\bigwedge _{(i_{1},\ldots ,i_{n})\in M(f)}\quad \bigvee _{i_{j}=0}x_{j}}$

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

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

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

Множество всех монотонных булевых функций образует замкнутый класс,[6] предполный в ${\displaystyle P_{2}}$. Таким образом, класс монотонных функций является одним из пяти предполных классов булевой логики. Класс монотонных функций обозначается ${\displaystyle M}$[7] или ${\displaystyle A_{1}}$[6] (обозначение Поста). В ${\displaystyle M}$ четыре предполных класса: ${\displaystyle D}$ (класс дизъюнкций с константами), ${\displaystyle K}$ (класс конъюнкций с константами), ${\displaystyle M\cap T_{0}}$ (класс монотонных, сохраняющих 0) и ${\displaystyle M\cap T_{1}}$ (класс монотонных, сохраняющих 1).[8] Любой собственный подкласс ${\displaystyle M}$ может быть достроен до предполного в ${\displaystyle M}$.[9] Как и для всех замкнутых классов в ${\displaystyle P_{2}}$, для класса монотонных функций верен аналог малой теоремы Поста: система монотонных функций полна в ${\displaystyle M}$ тогда и только тогда, когда в ней содержится не сохраняющая ${\displaystyle 0}$ функция, не сохраняющая ${\displaystyle 1}$ функция, не дизъюнкция или константа и не конъюнкция или константа.

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

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

• ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle x_{1}\land \ldots \land x_{n}}$, ${\displaystyle x_{1}\lor \ldots \lor x_{m}}$;
• ${\displaystyle 0}$, ${\displaystyle 1}$ и функция, не являющаяся конъюнкцией или дизъюнкцией.

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

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

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

Лемма о немонотонной функции. Из немонотонной функции и констант ${\displaystyle 0}$ и ${\displaystyle 1}$ можно получить отрицание.[10]

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

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

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

См. также

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

Примечания

1. Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб., БХВ-Петербург, 2004. — ISBN 5-94157-546-7, с 112
2. «Журавлев Ю. И., Флёров Ю. А., Федько О. С.» Дискретный анализ. Комбинаторика. Алгебра логики. Теория графов : учеб. пособие — М. МФТИ, 2012—248 с. — ISBN 978-5-7417-0423-3
3. Подколзин ТДФ 3, с. 7.
4. Яблонский, Гаврилов, Кудрявцев, 1966, с. 29.
5. Подколзин ТДФ 3, с. 8.
6. Яблонский, Гаврилов, Кудрявцев, 1966, с. 26.
7. Подколзин ТДФ 3, с. 3.
8. Яблонский, Гаврилов, Кудрявцев, 1966, с. 101.
9. Яблонский, Гаврилов, Кудрявцев, 1966, с. 102.
10. Подколзин ТДФ 3, с. 4.
11. Яблонский, Гаврилов, Кудрявцев, 1966, с. 27.

Литература

• Подколзин А. С. 3 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 19 декабря 2024.
• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста (рус.) / под ред. В. В. Донченко. — М.: Наука, 1966. — 120 с. — 10 000 экз.