Finding Prime Implicants by Minimizing Integer Programming Problems

The notion of Prime Implicants plays an important role in many AI applications such as diagnostic and abductive reasoning, automated theorem proving and, more in general, causal and hypothetical reasoning. Here we present a novel approach to generate prime implicants based on 0-1 programming. The problem of finding a prime implicant is transformed into an equivalent one that finds minimum solutions of an integer linear program. Then, the problem of finding a minimum solution is characterized with respect to the approximation properties. Finally, a generative algorithm which computes all prime implicants one at a time is presented and compared with the method proposed by Jackson and Pais, on the basis of a significant benchmark. 1 Introduction In this paper we introduce a generative method to compute prime implicants. We show the advantages of our approach both from a theoretical and an applicative point of view. The fundamental interest of prime implicants of a formula originally aris..