О нижней оценке функции Шеннона длины сертификата повторности булевых функций в одном семействе базисов

Актуальность и цели. В связи с развитием информатики и цифровой техники актуальным является исследование различных свойств булевых функций. Одним из важных свойств является возможность представления функции в заданном базисе формулой без повторения переменных (бесповторной формулой). Функции, которые можно так представить (бесповторные функции в данном базисе), можно рассматривать как класс «простых» функций в данном базисе. В статье рассматривается следующая задача: для заданной функции требуется найти такой набор строк (сертификат), с помощью которого можно проверить ее повторность в предэлементарном базисе, содержащем функцию семейства дискриминаторных, зависящую от s переменных. Целью данной работы является улучшение нижней оценки функции Шеннона длины сертификата повторности в этом базисе. Материалы и методы. Используется метод разнозначных матриц и удачный подбор функции с высокой нижней оценкой длины сертификата повторности. Результаты и выводы. Показано, что сертификат повторности функции $n$ переменных, равной единице только на нулевом и единичном наборах, в этом базисе имеет длину не менее $n/2-s+1$. Таким образом улучшена известная нижняя оценка n/s функции Шеннона длины сертификата повторности в этом базисе.