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

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

Определение

Булева функция называется монотонной, если из того, что она принимает значение $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}\leqslant \beta _{i}$для всех $i=1,...,n$.

Если ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ и ${\tilde {\alpha }}\neq {\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})\leqslant f({\tilde {\beta }}_{n})$.

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

См. также

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