Additional Optimization for Algorithm a Block Cover of a System of Disjunctive Normal Forms of Boolean Functions

The block coverage of the DNF system (Disjunctive Normal Forms) of fully defined Boolean functions consists in grouping elementary conjunctions into subsystems (blocks) with limited values of the number of input variables, functions and conjunctions. For a more effective solution to the problem of logical synthesis, an algorithm is proposed to reduce the number of different DNFs in a pair of intersecting blocks. The algorithm is based on constructing an undirected graph and coloring it into a minimum number of colors. This makes it possible to reduce the complexity of multi-level representations of block functions, since for sparse DNF systems of Boolean functions, the blocks often contain the same DNF. For matrix forms of sparse DNF systems, the ternary matrix specifying elementary conjunctions contains a large proportion of undefined values corresponding to the missing literals of Boolean input variables in the algebraic notation, and the Boolean matrix specifying the occurrences of conjunctions in the DNF of Boolean functions contains a large proportion of zero values. Thus, technologically independent optimization of sparse DNF systems of Boolean functions is divided into two stages — block coverage and minimization of multilevel representations of block functions in the form of BDD or Boolean nets.