Non-Clausal Deductive Techniques for Computing Prime Implicants and Prime Implicates

Abstract Several methods to compute the prime implicants and the prime implicates of a negation normal form (NNF) formula are developed and implemented. An algorithm PI is introduced that is an extension to negation normal form of an algorithm given by Jackson and Pais. The PI algorithm alone is sufficient in a computational sense. However, it can be combined with path dissolution, and it is shown empirically that this is often an advantage. None of these variations rely on conjunctive normal form or on disjunctive normal form. A class of formulas is described for which reliance on CNF or on DNF results in an exponential increase in the time required to compute prime implicants/implicates. The possibility of avoiding this problem with efficient structure preserving clause form translations is examined briefly and appears unfavorable.

Authors

• Anavai Ramesh
• Neil V. Murray

Keywords

No keywords are indexed for this paper.