Том 18, номер 2, 2011 г., Стр. 75-94

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

Аннотация:
На основе исследования экстремальных ядровых комплексов граней заданной размерности получены нижние оценки числа кратчайших комплексов граней в единичном $n$-мерном кубе. Показано, что число кратчайших комплексов $k$-мерных граней совпадает по порядку логарифма с числом комплексов, состоящих из не более $2^{n-1}$ различных граней размерности $k$, при $1\le k\le c\cdot n$ и $c<0.5$. Отсюда вытекают аналогичные нижние оценки для максимальных значений длины ядровых и числа кратчайших д.н.ф. булевых функций.
Библиогр. 15.

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

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

Статья поступила 2 ноября 2010 г.

Литература

[1] Андреев А. Е. Об одной модификации градиентного алгоритма // Вестн. МГУ. Сер. Математика. Механика. — 1985. — № 3. — С. 29–35.

[2] Васильев Ю. Л. К вопросу о числе минимальных и тупиковых дизъюнктивных нормальных форм // Дискрет. анализ. № 2. — Новосибирск: Ин-т математики СО АН СССР, 1964. —С. 3–9.

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

[4] Глаголев В. В. Некоторые оценки д.н.ф. булевых функций алгебры логики // Проблемы кибернетики. — 1967. — Т. 19. — С. 75–94.

[5] Журавлев Ю. И. Оценка для числа тупиковых д.н.ф. функций алгебры логики //Сиб. мат. журн. — 1962. — Т. 3, № 5. — С. 802–804.

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

[7] Коршунов А. Д. Сравнение сложности длиннейших и кратчайших д.н.ф. и нижняя оценка числа тупиковых д.н.ф. для почти всех булевых функций // Кибернетика. — 1969. — Т. 4. — С. 1–11.

[8] Коршунов А. Д. О сложности кратчайших дизъюнктивных нормальных форм булевых функций // Методы дискрет. анализа в изучении булевых функций. — Новосибирск: Ин-т математики СО АН СССР. — 1981. — № 37. — С. 9–41.

[9] Кузнецов С. Е. О нижней оценке длины кратчайшей д.н.ф. почти всех булевых функций // Вероятност. методы и кибернетика. — Казань: Изд-во Казанского ун-та, 1983. — № 19. — С. 44—47.

[10] Нигматуллин Р. Г. Вариационный принцип в алгебре логики // Дискрет. анализ. — Новосибирск: Ин-т математики СО АН СССР, 1967. — № 10. — С. 69–89.

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

[12] Чухров И. П. Оценки числа минимальных дизъюнктивных нормальных форм для поясковой функции // Методы дискрет. анализа в исследованиях функцион. систем. — Новосибирск: Ин-т математики СО АН СССР, 1981. — № 36. — С. 74–92.

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

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

[15] Pippenger N. The shortest disjunctive normal form of a random Boolean function // Random structures&algorithms. — 2003. — Vol. 22, N 2. — P. 161–186.