On the lower bound of the Shannon function for read-many certificate length in one base family

Background. The research of various properties of Boolean functions is an actual problem in connection with the progress of informatics and digital technology. 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 class of functions having this ability may be regarded as a class of “simple” functions in this basis. 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 function for read-once certificate length in this basis. Materials and methods. The method named “the matrix of various values” is applied in this paper to a well-selected read-many function with a high lower bound of a read-many certificate. Results. and conclusion . The author shows that the length of s read-many certificate of a function, which equals to $1$ only on the sets $(0,\dots,0)$ and $(1,\dots,1)$, is not less than $n/2-s+1$ in this basis. Thus, the researcher has improved the known lower bound n/s of Shannon function for the certificate length in this basis.