RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Иркутского государственного университета. Серия «Математика» // Архив

Известия Иркутского государственного университета. Серия Математика, 2024, том 49, страницы 105–123 (Mi iigum578)

Алгебро-логические методы в информатике и искусственный интеллект

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

Д. Н. Баротов

Финансовый университет при Правительстве Российской Федерации, Москва, Российская Федерация

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

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

УДК: 512.563+519.853.3

MSC: 06E30, 90C25, 46N10

Поступила в редакцию: 13.01.2024
Исправленный вариант: 02.03.2024
Принята в печать: 12.03.2024

DOI: 10.26516/1997-7670.2024.49.105



© МИАН, 2024