A New Algorithm for Generating Prime Implicants

Abstract

This paper describes an algorithm which will generate all the prime implicants of a Boolean function. The algorithm is different from those previously given in the literature, and in many cases it is more efficient. It is proved that the algorithm will find all the prime implicants. The algorithm may possibly generate some nonprime implicants. However, using frequency orderings on literals, the experiments with the algorithm show that it usually generates very few ( possibly none) nonprime implicants. Furthermore, the algorithm may be used to find the minimal sums of a Boolean function. The algorithm is implemented by a computer program in the LISP language.