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

Определение

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

Говорят, что набор ${\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})}$ .

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

См. также

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

Примечания