The Concept of Term Exclusiveness and Its Effect on the Theory of Boolean Functions

Abstract

In a logical system with D variables pl, i = 0, 1, ..-, D - 1, a functionf is (incompletely) specified by two sets of minterms: p E {Pl ~ containing all minterms which must be present in every canonical ~II-form off, and p E {P}0 containing all minterms excluded from every canonical ~II-form off. Those two sets have no element in common, of course. The membership of any minterm which is neither in (P} ~ nor in (P } 0 is free to be specified later to fulfill prescribed optimization requirements. The function is then called" incompletely specified" and is designated by re. Here the word MINs is used to exclusively designate the MINterms in {P} ~. Expressed in the conventional geometrical model language, MIN designates a point p of the logical space of the system, where fo must be true (f~(p) = 1). Two MINs forming a pair p, p' are called mutually term exclusive iff no term-implicant T off ° exists, which covers them both. A set of MINs is called term ezclusive iff every pair of its elements is composed from hiINs which are mutually term exclusive. It is obvious that for a given fo the number of elements in term exclusive sets has a least upper bound/11. It is shown that M is a lower bound on the number of terms in any Boolean XII-form of fo with other important consequences which permit the development of N-minimal Boolean ZIl-forms under constraints which are much more general than the usual constraint of the minimal count of all literals, which restricts each term of the form to a prime implicant off ~. The solution of the optimal multiple output combinational network is offered as an example of a problem which needs the applica- tion of the concept of term exclusiveness.