Computing Irredundant Normal Forms from Abbreviated Presence Functions

Abstract

A new method is presented for computing irredundant normal forms which renders feasible the handling of ``large'' functions. The method is based on the concept of abbreviated presence function and incorporates techniques found in the methods of ratio function and iterated consensus of the prime implicants. The complete set of irredundant normal equivalents of a formula is shown to be obtainable from an ``abbreviated presence function'' consisting of the presence relations corresponding to the prime implicants occurring in any one irredundant normal equivalent of the formula. Several examples are included to illustrate the economy in labor which the method provides. A new set of necessary and sufficient conditions is also given which allows a direct determination of absolutely dispensable prime implicants from the set of presence relations. The notion of absolute dispensability as presented here is related to that of Urbano and Mueller in which a prime implicant is absolutely dispensable if and only if it does not belong to an essential star.