A new method to compute prime and essential prime implicants of Boolean functions
J.C. Madre, Olivier Coudert · 1992
Computing the prime implicants and the essential prime implicants of Boolean functions is a problem that has applications in several areas of computer science, for instance it is critical in circuit synthesis and optimization, but also in automated reasoning. In this paper we propose a new method to compute implicitly the sets of prime implicants and of essential prime implicants of incompletely specified Boolean functions. This method allows us to handle functions that have sets of prime implicants and of essential prime implicants several orders of magnitude larger than those of the functions that could be handled by existing methods. The key idea that makes these computations possible is to manipulate sets of prime and of essential prime implicants denoted by their meta-products, which are characteristic functions. These functions are represented with binary decision diagrams that are a very compact canonical graph representation of Boolean functions and that support very efficiently all the operations needed here.