Поволжский регион УДК 517.718.7 Д. В. Кафтан О НИЖНЕЙ ОЦЕНКЕ ФУНКЦИИ ШЕННОНА ДЛИНЫ СЕРТИФИКАТА ПОВТОРНОСТИ БУЛЕВЫХ ФУНКЦИЙ В ОДНОМ СЕМЕЙСТВЕ БАЗИCОВ Аннотация. <...> В связи с развитием информатики и цифровой техники актуальным является исследование различных свойств булевых функций. <...> Одним из важных свойств является возможность представления функции в заданном базисе формулой без повторения переменных (бесповторной формулой). <...> Функции, которые можно так представить (бесповторные функции в данном базисе), можно рассматривать как класс «простых» функций в данном базисе. <...> В статье рассматривается следующая задача: для заданной функции требуется найти такой набор строк (сертификат), с помощью которого можно проверить ее повторность в предэлементарном базисе, содержащем функцию семейства дискриминаторных, зависящую от s переменных. <...> Целью данной работы является улучшение нижней оценки функции Шеннона длины сертификата повторности в этом базисе. <...> Используется метод разнозначных матриц и удачный подбор функции с высокой нижней оценкой длины сертификата повторности. <...> Показано, что сертификат повторности функции n переменных, равной единице только на нулевом и единичном наборах, в этом базисе имеет длину не менее n/2 – s + 1. <...> Таким образом улучшена известная нижняя оценка n/s функции Шеннона длины сертификата повторности в этом базисе. <...> Ключевые слова: бесповторная функция, сертификат повторности, семейство дискриминаторных функций, разнозначная матрица. <...> Kaftan ON THE LOWER BOUND OF THE SHANNON FUNCTION FOR READ-MANY CERTIFICATE LENGTH IN ONE BASE FAMILY Abstract. <...> The ability of a function to be represented in a given basis via a formula without replication of variables (a read-once formula) is an important one. <...> The author considers a problem of finding a read-many certificate for an arbitrary Boolean function in the extended elementary basis with a discriminator function of s variables. <...> The object of the article is to improve the lower bound of the Shannon <...>