Том 19, номер 3, 2012 г., Стр. 79-99

УДК 519.95
Чухров И. П. 
О минимальных комплексах граней в единичном кубе

Аннотация:
Рассматривается задача построения минимальных комплексов граней в единичном $n$-мерном кубе относительно класса мер сложности, для которых сложность комплекса не изменяется при замене некоторых граней гранями, изоморфными относительно перестановки координат. Этот класс содержит все известные меры сложности, используемые при минимизации булевых функций в классе дизъюнктивных нормальных форм (д.н.ф.). Показано, что число комплексов из граней размерности не более $k$, которые являются минимальными для всех мер сложности из этого класса, совпадает по порядку логарифма с числом комплексов из не более $2^{n-1}$ различных граней размерности не более $k$ при $1\le k\le c\cdot n$ и $c<0.5$. Число функций с “большим” числом минимальных комплексов совпадает по порядку логарифма с числом всех функций. Аналогичные оценки справедливы для максимального числа д.н.ф. булевой функции, которые являются минимальными для всех мер сложности из указанного класса. Полученные результаты показывают, что проблемы трудоёмкости при минимизации булевых функций определяются структурными свойствами множества вершин булевой функции в единичном кубе, т.е. свойствами области, на которой минимизируется функционал, а не свойствами функционала меры сложности.
Ил. 1, библиогр. 9.

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

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

Статья поступила 18 июня 2011 г.

Литература

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

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

[3] Журавлев Ю. И. О различных понятиях минимальности д.н.ф. // Сиб. мат. журн. — 1960. — Т. 1, № 4. — С. 609–611.

[4] Журавлев Ю. И. Алгоритмы построения минимальных д.н.ф. // Дискрет. математика и мат. вопросы кибернетики. Т. 1. — М.: Наука, 1974. — С. 67–98.

[5] Лин Син-Лян. О сравнении сложностей минимальных и кратчайших дизъюнктивных нормальных форм для функций алгебры логики // Проблемы кибернетики. — 1967. — Т. 18. — С. 11–44.

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

[7] Чухров И. П. О числе минимальных дизъюнктивных нормальных форм // Докл. АН СССР. — 1984. — Т. 276, № 6. — С. 1335–1339.

[8] Чухров И. П. О ядровых и кратчайших комплексах граней в единичном кубе // Дискрет. анализ и исслед. операций. — 2011. — Т. 18, № 2. — С. 75–94.

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