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

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

Определение

Булева функция называется монотонной, если из того, что она принимает значение $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

Похожие исследовательские статьи

А́лгебра — раздел математики, который можно нестрого охарактеризовать как обобщение и расширение арифметики; в этом разделе числа и другие математические объекты обозначаются буквами и другими символами, что позволяет записывать и исследовать их свойства в самом общем виде. Слово «алгебра» также употребляется в общей алгебре в названиях различных алгебраических систем. В более широком смысле под «алгеброй» понимают раздел математики, посвящённый изучению операций над элементами множеств произвольной природы, обобщающий обычные операции сложения и умножения чисел.

В математике, целая часть вещественного числа $\text{[math]}$ — округление $\text{[math]}$ до ближайшего целого в меньшую сторону. Целая часть числа также называется антье, или пол. Наряду с полом существует парная функция — потолок — округление $\text{[math]}$ до ближайшего целого в большую сторону.

Опера́тор — математическое отображение между множествами, в котором каждое из них наделено какой-либо дополнительной структурой. Понятие оператора используется в различных разделах математики для отличия от другого рода отображений ; точное значение зависит от контекста, например в функциональном анализе под операторами понимают отображения, ставящие в соответствие функции другую функцию.

Локально тривиальное расслоение — расслоение, которое локально выглядит как прямое произведение.

Булева формула — терм над некоторым множеством булевых функций. Более развёрнуто: пусть $\text{[math]}$ — некоторое множество булевых функций, $\text{[math]}$ — множество символов переменных, $\text{[math]}$ « $\text{[math]}$ » « $\text{[math]}$ » « $\text{[math]}$ » $\text{[math]}$ — множество символов пунктуации, причём все три множества попарно непересекаются. Булева формула над множеством функций $\text{[math]}$ и множеством переменных $\text{[math]}$ индуктивно определяется как слово над алфавитом $\text{[math]}$ следующим образом:

слово $\text{[math]}$ , где $\text{[math]}$ — формула;
слово $\text{[math]}$ , где $\text{[math]}$ и $\text{[math]}$ имеет арность $\text{[math]}$ — формула;
слово $\text{[math]}$ , где $\text{[math]}$ , $\text{[math]}$ имеет арность $\text{[math]}$ , $\text{[math]}$ — некоторые формулы, — формула;
любая формула получена за конечное число применения шагов 1-3.

Пусть $\text{[math]}$ есть векторное пространство над полем $\text{[math]}$ .

Регуля́рный язык в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.

<span class="mw-page-title-main">Порядковое число</span> порядковый тип вполне упорядоченного множества

В теории множеств порядковым числом, или ординалом называется порядковый тип вполне упорядоченного множества. Как правило, порядковые числа отождествляются с наследственно транзитивными множествами. Ординалы представляют собой одно из расширений натуральных чисел, отличающееся как от целых, так и от кардинальных чисел. Как и другие разновидности чисел, их можно складывать, перемножать и возводить в степень. Бесконечные порядковые числа называют трансфинитными. Ординалы играют ключевую роль в доказательстве многих теорем теории множеств — в частности, благодаря связанному с ними принципу трансфинитной индукции.

Замкнутый класс в теории булевых функций — такое множество $\text{[math]}$ функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: $\text{[math]}$ . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества $\text{[math]}$ , снова входит в это же множество.

Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Максом Адлеманом в 1979 году. Леонард Макс Адлеман — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.

Бу́лева фу́нкция от $\text{[math]}$ аргументов — в дискретной математике — отображение $\text{[math]}$ , где $\text{[math]}$ — булево множество. Элементы булева множества $\text{[math]}$ обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число $\text{[math]}$ , обозначающее количество аргументов, называется арностью или местностью функции, в случае $\text{[math]}$ булева функция превращается в булеву константу. Элементы декартова произведения $\text{[math]}$ называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается $\text{[math]}$ , а от $\text{[math]}$ аргументов — $\text{[math]}$ . Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.

Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством — замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все $\text{[math]}$ . Множество предполных классов булевых функций исчерпывается списком:

Класс $\text{[math]}$ функций, сохраняющих константу 0:
$\text{[math]}$ .
Класс $\text{[math]}$ функций, сохраняющих константу 1:
$\text{[math]}$ .
Класс $\text{[math]}$ самодвойственных функций:
$\text{[math]}$ .
Класс $\text{[math]}$ монотонных функций:
$\text{[math]}$ .
Класс $\text{[math]}$ линейных функций — представимых полиномом Жегалкина первой степени:
$\text{[math]}$ .

Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция $\text{[math]}$ называется самодвойственной, если для любых значений $\text{[math]}$ верно

\text{[math]}

Генератор группы — понятие, используемое в теории групп Ли. Генераторы группы $\text{[math]}$ — это элементы, образующие базис её алгебры Ли, или, в общем случае, базис алгебры Ли образа группы $\text{[math]}$ .

<span class="mw-page-title-main">Нормальные колебания</span>

Норма́льные колеба́ния, со́бственные колебания или мо́ды — набор характерных для колебательной системы типов гармонических колебаний. Каждое из нормальных колебаний физической системы, например, колебаний атомов в молекулах, характеризуется своей частотой. Такая частота называется нормальной частотой, или собственной частотой. Набор частот нормальных колебаний составляет колебательный спектр. Произвольное колебание физической системы можно представить в виде суперпозиции различных нормальных колебаний. Вынужденные колебания физической системы испытывают резонанс на частотах, которые совпадают с частотами нормальных колебаний этой системы.

Система F — система типизированного лямбда-исчисления, отличающаяся от просто типизированной системы наличием механизма универсальной квантификации над типами. Эту систему разработал в 1972 году Жан-Ив Жирар в контексте теории доказательств в логике. Независимо от него подобную систему предложил в 1974 году Джон Рейнольдс. Система F позволяет формализовать концепцию параметрического полиморфизма в языках программирования и служит теоретической основой для таких языков программирования как Haskell и ML.

Линейная булева функция — булева функция, полином Жегалкина которой имеет первую степень. Более развёрнуто булева функция $\text{[math]}$ называется линейной, если она выражается в виде:

\text{[math]}

Групповой анализ дифференциальных уравнений — раздел математики, изучающий свойства симметрии дифференциальных уравнений относительно различных преобразований зависимых и независимых переменных. Включает в себя методы и прикладные аспекты дифференциальной геометрии, теории групп и алгебр Ли, вариационного исчисления и является, в свою очередь, эффективным инструментом исследования в теории ОДУ, ДУЧП и математической физике.

Алгори́тм Шёнинга — вероятностный алгоритм для решения задачи выполнимости булевых формул в k-конъюнктивной нормальной форме, предложенный Уве Шёнингом в 1999 году.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.