Generation of Prime Implicants from Subfunctions and a Unifying Approach to the Covering Problem

Abstract

A new method for computing the prime implicants of a Boolean function from an arbitrary sum-of-products form is given. It depends on the observation that the prime implicants of a Boolean function can be obtained from the prime implicants of its subfunctions with respect to a fixed but arbitrary variable. The problem of obtaining all irredundant sums from the list of all prime implicants and an arbitrary list of implicants representing the function is solved. The irredundant sums are in one-to-one relation to the prime implicants of a positive Boolean function associated with these lists. The known formulas of Petrick, Ghazala, Tison, Mott, and Chang are obtained as special cases and incompletely specified functions can also be handled. We give a complete and simple method for finding the positive Boolean function mentioned above. The paper is self-contained and examples are included.