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

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

Определение

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

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

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

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

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

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

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


См. также

Примечания

  1. Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб., БХВ-Петербург, 2004. — ISBN 5-94157-546-7, с 112
  2. «Журавлев Ю. И., Флёров Ю. А., Федько О. С.» Дискретный анализ. Комбинаторика. Алгебра логики. Теория графов : учеб. пособие — М. МФТИ, 2012—248 с. — ISBN 978-5-7417-0423-3
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.