In this paper we introduce a new combinatorial problem for covering binary sets. This problem appears in connection to research of complexity of ESOP. Shannon function is called maximum from complexities of the shortest representation of each Boolean function. Hence the upper bound of the Shannon function guarantees the existence of the representation of any Boolean function with this complexity. It is important for applications.

As usual implicit algorithms of minimisation working with any Boolean function are used for defining the upper bound of Shannon function. Previously we have developed the algorithm of minimisation of Boolean functions in ESOPs which uses the combinatorial technique connected with tasks of finding covering and packing of binary sets. ESOP for given Boolean function is built by pattern which is described of non-singular matrix over the field Z2 in that earch row and column matches any binary set. These binary sets should have the packing with density 1 + o(1) for getting the effective upper bound.

It is normal to use error-correcting linear codes for building a matrix of pattern. In this case Hamming code may by used. And so it lets use terms of the linear codes theory in definitions of combinatorial problems. In this paper we investigate a problem which belongs to covering and packing design. In doing so requirements to matrix impose several conditions to cover. In this work some of possible covers are introduced which have been described in terms of error-correcting linear codes.

1. Kirichenko K.D. Bounds of the minimization patterns’ complexity of ESOP (in Russian). IIGU Ser. Matematika, 2009, vol. 2, pp. 67–76.

2. Bashov М.A., Selezneva C.N. On the length of functions of k-valued logics in modulo k ESOP (in Russian). Diskretnaya matematika, 2014, vol. 26, no 3, pp. 3–9.

3. Cooper J.N., Ellis R.B., Kahng A.B. Asymmetric binary covering codes. Journal of Combinatorial Theory, 2001, vol. 100, no 2, pp. 232–249.

4. MacWilliams F.J., Sloane N.J.A. The Theory of Error Correction Codes. North-Holland Publishing Company, 1977.

5. Rodl V. On a packing and covering problem. European Journal of Combinatorics, 1985, vol. 6, pp. 69–78.

6. Turan P. Reseach Problems. Magyar Tud. Acad. Mat. Kutato Int. Kozl, 1961, vol. 6, pp. 417–423.