Minimization of Boolean Functions

In designing switching circuits such as digital computers, telephone central offices, and digital machine tool controls, it is common practice to make use of Boolean algebra notation. 1 - 2> 3 - 4 The performance of a single-output circuit is specified by means of a Boolean function of the input variables. This function, which is called the circuit transmission, is equal to 1 when an output is present and equals 0 when there is no output. A convenient means of specifying a transmission is a table of combinations such as that given in Table I. This table lists, in the column under T, the output condition for each combination of input conditions. If there are some combinations of input conditions for which the output is not specified (perhaps because these combinations can never occur), d-entries are placed in the T-column of the corresponding rows of the table of combinations. The actual values (0 or 1) assigned to these rows are usually chosen so as to simplify the circuit which is designed to satisfy the requirements specified in the table of combinations. For each row of the table of combinations a transmission can be written which equals "one" only when the variables have the values listed in that row of the table. These transmissions will be called elementary product terms (or more simply, p-terms) since any transmission can always be written as a sum of these p-terms. Table I (b) lists the p-terms for Table 1(a). Note that every variable appears in each p-term. The * This paper is derived from a thesis submitted to the Massachusetts Institute of Technology in partial fulfillment of the requirements for the degree of Doctor of Science on April 30, 1956.