Minimal ``Sum of Products of Sums" Expressions of Boolean Functions

Abstract

The problem of economical synthesis of circuits for digital computers leads to the problem of finding Boolean expressions of minimal length equivalent to a Boolean expression f. Previous authors restricted themselves to ``sum of products'' expressions; dualizing this gives ``products of sums.'' The next more efficient step is to find minimal ``sums of products of sums'' expressions. In this paper, the basic concepts are formulated in Part I, and general theorems are given in Part II. In Part III, all the distinct minimal ``sum of products of sums'' expressions are obtained in case the cell complex of f consists of two isolated points. For the case of three isolated points partial results have been obtained which will be published in a later communication.