Том 26, номер 3, 2019 г., Стр. 115-140

УДК 519.714.7
Чухров И. П.
О минимизации булевых функций для аддитивных мер сложности

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

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

DOI: 10.33048/daio.2019.26.640

Чухров Игорь Петрович ¹
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056, Москва, Россия
е-mail: chip@icad.org.ru

Статья поступила 23 ноября 2018 г.
После доработки — 14 мая 2019 г.
Принята к публикации 5 июня 2019 г.

Литература

[1] Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискрет. математика и мат. вопросы кибернетики. Т. 1. М.: Наука, 1974. С. 99–148.

[2] Вебер К. О различных понятиях минимальности дизъюнктивных нормальных форм // Проблемы кибернетики. 1979. Вып. 36. С. 129–158.

[3] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.

[4] Сапоженко А. А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // Итоги науки и техн. Сер. Теория вероятностей. Мат. статистика. Теор. кибернетика. 1987. Т. 25. С. 68–116.

[5] Чухров И. П. О мерах сложности комплексов граней в единичном кубе // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 6. С. 77–94.

[6] Чухров И. П. О задаче минимизации для одного множества булевых функций // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. С. 75–97.

[7] Чухров И. П. О сложности минимизации квазициклических булевых функций // Дискрет. анализ и исслед. операций. 2018. Т. 25, №3. С. 126–151.

[8] Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2003. 384 с.

[9] Coudert O., Sasao T. Two-level logic minimization // Logic synthesis and verification. Norwell, MA: Kluwer Acad. Publ., 2001. P. 1–27. (Springer Int. Ser. Eng. Comp. Sci.; Vol. 654.)

[10] Pippenger N. The shortest disjunctive normal form of a random Boolean function // Random Structures & Algorithms. 2003. V. 22, No. 2. P. 161–186.

[11] Umans C., Villa T., Sangiovanni-Vincentelli A. L. Complexity of two-level logic minimization // IEEE Trans. CAD Integr. Circuits Syst. 2006. Vol. 25, No. 7. P. 1230–1246.