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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение

[править | править код]

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

Говорят, что набор предшествует набору , ( не больше ), если для всех .

Если и , то говорят, что набор строго предшествует набору , .

Наборы и называются сравнимыми, если либо .

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

Булева функция называется монотонной, если для любых двух сравнимых наборов и таких, что , имеет место неравенство .[2]

Множество всех монотонных функций алгебры логики обозначается через , а множество всех монотонных булевых функций, зависящих от переменных


Примечания

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