BBC Russian

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

Определение

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

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

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

См. также

Примечания

↑ Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб., БХВ-Петербург, 2004. — ISBN 5-94157-546-7, с 112
↑ «Журавлев Ю. И., Флёров Ю. А., Федько О. С.» Дискретный анализ. Комбинаторика. Алгебра логики. Теория графов : учеб. пособие — М. МФТИ, 2012—248 с. — ISBN 978-5-7417-0423-3

Эта страница в последний раз была отредактирована 7 октября 2020 в 02:44.

Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.

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

Из Википедии — свободной энциклопедии

Определение

См. также

Примечания