Препринт посвящен исследованию неравенств между выпуклыми, вогнутыми и полилинейными продолжениями булевых функций. В результате исследования доказано, что для заданной произвольной булевой функции от n переменных, во-первых, любое её выпуклое продолжение на n-мерный единичный куб не превосходит ее полилинейного продолжения на n-мерный единичный куб и, во-вторых, её полилинейное продолжение на n-мерный единичный куб не превосходит ни одного её вогнутого продолжения на n-мерный единичный куб. Доказано также, что равенство в этой последовательности неравенств может быть достигнуто тогда и только тогда, когда число существенных переменных заданной булевой функции не более одной. Полученный результат может быть использован при преобразовании систем булевых уравнений к задаче численной оптимизации и последующем поиске их решений.

выпуклое продолжение булевой функции, вогнутое продолжение булевой функции, полилинейное продолжение булевой функции, неравенство

Математические вопросы и теория численных методов

Баротов Достонжон Нумонжонович,  ,  orcid.org/0000-0001-5047-7710,  Финансовый Университет при Правительстве РФ

Судаков Владимир Анатольевич,  ,  orcid.org/0000-0002-1658-1941,  ИПМ им. М.В. Келдыша РАН; Финансовый Университет при Правительстве РФ