В данной работе рассматривается одна новая комбинаторная задача, возникающая в связи с изучением сложности представлений булевых функций полиномиальными нормальными формами. В теории сложности минимальная сложность представления самой сложной функции называется функцией Шеннона. Таким образом, верхняя оценка функции Шеннона гарантирует наличие представления данной сложности для любой булевой функции, что имеет существенное прикладное значение.

Обычно для нахождения верхней оценки функции Шеннона используются конструктивные алгоритмы минимизации, работающие на классе всех булевых функций. Ранее автором был разработан алгоритм минимизации полиномиальных нормальных форм булевых функций, основанный на комбинаторной технике, связанной с задачами нахождения покрытий и упаковок на множестве двоичных наборов. Полиномиальная форма для заданной булевой функции строится на основе шаблона, который описывается невырожденной матрицей над полем Z2, где каждая строка и столбец соответствует некоторому двоичному набору. При этом для получения хорошей верхней оценки требуется, чтобы множества наборов в строках и столбцах обладали упаковками с плотностью 1 +o(1).

При построении матрицы шаблона естественно воспользоваться линейными кодами, исправляющими одну ошибку, в частности, может быть использован код Хэмминга. Это позволяет использовать понятия теории линейных кодов в формулировках соответствующих комбинаторных задач. Задачу, рассматриваемую в настоящей работе также можно отнести к классу задач на нахождение покрытий и упаковок. При этом на покрытие накладывается ряд дополнительных условий, вытекающих из требований к матрице. В работе приводятся некоторые из возможных покрытий, описанные на языке линейных кодов, исправляющих ошибки.

1. Кириченко К. Д. Оценки сложности шаблонов минимизации полиномиальных форм булевых функций / К. Д. Кириченко // Изв. Иркут. гос. ун-та. Сер. Математика. – 2009. – Т. 2, № 2. – С. 67–76.

2. Башов М. А. О длине функций k-значной логики в классе полиномиальных нормальных форм по модулю k / М. А. Башов, С. Н. Селезнева // Дискрет. математика. – 2014. – Т. 26, № 3. – C. 3–9.

3. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь. — 1979. — 744 c.

4. Cooper J. N. Asymmetric binary covering codes / J. N. Cooper, R. B. Ellis, A. B. Kahng // Journal of Combinatorial Theory. – 2001. – Vol. 100, N 2. – P. 232–249.

5. Rodl V. On a packing and covering problem / V. Rodl // European Journal of Combinatorics. – 1985. – Vol. 6. – P. 69–78.

6. Turan P. Reseach Problems / P. Turan // Magyar Tud. Acad. Mat. Kutato Int. Kozl. – 1961. – Vol. 6. – P. 417–423.