Zastosowanie hipergrafów w procesie selekcji implikantów prostych

摘要

In the paper a new idea for the selection of prime implicants is proposed. 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 table is formed as a selection hypergraph. If the selection hypergraph 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 are shown in order to apply the proposed selection algorithm to minimize an exemplary Boolean function.%W referacie przedstawiona została nowa koncepcja selekcji implikantów prostych w procesie dwupoziomowej minimalizacji funkcji logicznych. Aktualnie znane metody selekcji bazują na połączeniu metod dokładnych z przybliżonymi. W artykule zaproponowana została nowatorska metoda selekcji, która w całości opiera się na algorytmach dokładnych, poprzez zastosowanie teorii hipergrafów. Najbardziej istotną zaletą proponowanego rozwiązania jest wielomianowa złożoność obliczeniowa całej operacji selekcji, która w przypadku ogólnym ma złożoność wykładniczą.