Статья в сборнике "Математические вопросы кибернетики" №20, Москва, 2022
Авторы:Чухров И.П.
Задача минимизации булевых функций: условия минимальности и вероятностный метод
Аннотация:
Статья написана на основе докладов, представленных на XII Международном семинаре. Дискретная математика и ее приложения имени академика О. Б. Лупанова (Москва, МГУ, 20–25 июня 2016 г.) и содержит обзор результатов для задачи минимизации булевых функций, в которых рассматриваются методы доказательства минимальности и неконструктивные подходы к получению оценок параметров, характеризующих трудоемкость минимизации относительно классов мер сложности.
Ключевые слова:
минимизация булевых функций, n-мерный единичный куб, грань, комплекс граней, покрытие, мера сложности, ядровое, тупиковое, кратчайшее, минимальное покрытия, нижняя оценка сложности покрытия
