Том 22, номер 3, 2015 г., Стр. 75–97

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

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

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

DOI: 10.17377/daio.2015.22.471

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

Статья поступила 16 января 2015 г.

Литература

[1] Васильев Ю. Л. Массивные классы плотных булевых функций // Методы дискретного анализа в синтезе управляющих систем. № 32. Новосибирск: Ин-т математики СО АН СССР, 1978. С. 21–33.

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

[3] Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 7, № 2. С. 22–46.

[4] Леонтьев В. К. Дискретная оптимизация //Журн. вычисл. математики и мат. физики. 2007. Т. 47, № 2. С. 338–352.

[5] Чухров И. П. О минимальных комплексах граней в единичном кубе // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 3. С. 79–99.

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

[7] Coudert O. On solving covering problems // Proc. 33rd Design Automation Conf. (Las Vegas, NV, June 3–7, 1996). New York: ACM, 1996. P. 197–202.

[8] 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.)