EN|RU

Том 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
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056 Москва, Россия
е-mail: chip@icad.org.ru

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

 © Институт математики им. С. Л. Соболева, 2015