Abstract <p>A block cover of a system of disjunctive normal forms (DNFs) of fully defined Boolean functions involves grouping elementary conjunctions into subsystems (blocks) with limited numbers of input variables, functions, and conjunctions. To more efficiently solve the logic synthesis problem, an algorithm for reducing the number of different DNFs in a pair of intersecting blocks is proposed. The algorithm is based on constructing an undirected graph and coloring it with a minimum number of colors. This reduces the complexity of multilevel representations of block functions because for sparse DNF systems of Boolean functions, blocks often contain identical DNFs. For matrix forms of sparse DNF systems, the ternary matrix determining elementary conjunctions contains a large number of undefined values corresponding in algebraic notation to missing literals of Boolean input variables, and the Boolean matrix defining the occurrences of conjunctions in the DNF of Boolean functions contains a large proportion of zero values. Thus, technology-independent optimization of sparse DNF systems of Boolean functions is divided into two stages: block cover and minimization of multilevel representations of block functions in the form of binary decision diagrams (BDDs) or Boolean networks.</p>