Application of Hypergraphs in the Prime Implicants Selection Process

摘要

The paper presents a new concept of the selection of prime implicants in a two-level logic minimization of Boolean functions. The method is based on the two-level minimization process of the Boolean functions, according to the Quine-McCluskey approach. Initially, the set of prime implicants for the logic function ought to be calculated. Next, the selection process is applied to achieve the minimal formula. Such an operation is a typical covering problem and in general case it has exponential computational complexity. In the paper we propose a new prime implicants selection method. An idea is based on the hypergraph theory. The prime implicants matrix (chart) is formed as a selection hypergraph. If the selection hyper-graph belongs to the Exact Transversal Hypergraph class (xt-class), the solution may be obtained in a polynomial time, which is not possible in a general case. The proposed method is illustrated by an example. All necessary steps will be shown in order to apply the proposed selection algorithm to minimize an exemplary Boolean function.