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

Булева функция называется монотонной, если из того, что она принимает значение ${\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 M}$, а множество всех монотонных булевых функций, зависящих от ${\displaystyle n}$ переменных ${\displaystyle M^{(n)}}$

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