An Incremental Method for Generating Prime Implicants/Implicates

Given the recent investigation of clause management systems(CMSs) for Artificial Intelligence applications, there is an urgent need for an efficient incremental method for generating prime implicants. Given a set of clauses $\cal F$, a set of prime implicants $\Pi$ of $\cal F$ and a clause $C$, the problem can be formulated as finding the set of prime implicants for $\Pi \bigcup \{ C \} $. Intuitively, the property of implicants being prime implies that any effort to generate prime implicants from a set of prime implicants will not yield any new prime implicants but themselves. In this paper, we exploit the properties of prime implicants and propose an incremental method for generating prime implicants from a set of existing prime implicants plus a new clause. The correctness proof and complexity analysis of the incremental method are presented, and the intricacy of subsumptions in the incremental method is also examined. Additionally, the role of prime implicants in the CMS is also mentioned.