Boolean functions, minimization of

A representation of Boolean functions by normal forms (cf. Boolean functions, normal forms of) that are most simple relative to some measure of complexity. The usual meaning of the complexity of a normal form is the number of letters in it. A simplest form is then called a minimal form. A measure of complexity sometimes used is the number of elementary conjunctions in a disjunctive normal form or the number of factors in a conjunctive normal form. In this case a simplest form is called a shortest form. In view of the duality of disjunctive and conjunctive normal forms, it is sufficient to consider disjunctive normal forms only.

The construction of shortest and minimal disjunctive normal forms each has its own specific features. The sets of minimal and shortest disjunctive normal forms of one and the same function may be connected by set-theoretical relations: of being contained one in one another, of having an empty intersection or a non-empty symmetric difference. Let be the complexity of the minimal disjunctive normal form of a function , let be the minimal complexity of its shortest disjunctive normal form and let be the largest of the ratios over all functions in variables. Then the following asymptotic relation holds:

By the problem of minimization of Boolean functions one usually understands that of constructing their minimal disjunctive normal forms. There is a trivial algorithm for constructing all minimal disjunctive normal forms of an arbitrary Boolean function , which operates as follows: All disjunctive normal forms in the variables are reviewed, and those which realize the function and have minimal complexity are selected. In fact, this algorithm is not applicable even for small , since the number of operations required increases rapidly. Many other algorithms have therefore been constructed, which, however, are not effectively applicable to all functions.

The initial specification of a function in the problem of minimization is usually a table, a perfect disjunctive normal form (cf. Boolean functions, normal forms of) or an arbitrary disjunctive normal form. The first stage consists in the transition to the so-called abridged disjunctive normal form, which is uniquely determined for each function. Many methods for the realization of this transition are available. The most universal method consists in performing transformations on a disjunctive normal form of the type

A typical property of the abridged disjunctive normal form is that it is possible to obtain any minimal abridged disjunctive normal form from it by removing certain elementary conjunctions. The second, most laborious stage is to extract from the abridged disjunctive normal form all dead-end disjunctive normal forms, among them all the minimal ones. A geometrical representation of Boolean functions is usually employed at this stage. Let denote the set of all vertices of the -dimensional unit cube. Each Boolean function is in one-to-one correspondence with the subset , , of vertices such that . Let be an elementary conjunction of rank . The set is then called an interval of rank corresponding to the elementary conjunction . One says that a system of intervals forms a covering of a set if

Since the equalities

are equivalent, the problem of minimization of Boolean functions is equivalent to the search for coverings with a minimal sum of the ranks of their intervals. Such coverings are called minimal. An interval is called maximal for a function if and if there is no interval such that . The construction of dead-end disjunctive normal forms of a function reduces to a search for coverings of by maximal intervals such that no proper subset of it is a covering of . These coverings correspond to dead-end disjunctive normal forms and are called irreducible. They are obtained from coverings corresponding to abridged disjunctive normal forms by removal of certain intervals.

The selection of the minimal disjunctive normal forms from all dead-end disjunctive normal forms is also a very laborious process, since "almost-all" Boolean functions in arguments have no fewer than different dead-end disjunctive normal forms. The diversity of the complexities of dead-end disjunctive normal forms may be very wide, so that if a random rather than a dead-end minimal disjunctive normal form is selected, a large error may result.

Estimates of the number of dead-end disjunctive normal forms and of the scatter of their complexities show that a more detailed inspection during the elimination of the elementary conjunctions from a disjunctive normal form is a natural way of improving the effectiveness of minimization algorithms. A conjunction should be eliminated (or, on the contrary, retained until the end of the process) only if it can be established by some procedure that it does not occur in any minimal disjunctive normal form for (occurs in all minimal disjunctive normal forms for ). The latter fact is usually established by an analysis of the conjunctions that are close to the one in question, i.e. occur in a neighbourhood of it (cf. Algorithm, local). Here one has to accumulate information about elementary conjunctions and use it in the subsequent analysis. Procedures of this kind are known as local simplification algorithms. Some of them are quoted below, and their description involves the concept of the -th order neighbourhood of an elementary conjunction in a disjunctive normal form , .

The zero-order neighbourhood consists of the single conjunction . If is the neighbourhood of order , then the neighbourhood of order consists of all conjunctions of the disjunctive normal form that satisfy one of the following conditions: 1) has a non-empty intersection with at least one interval corresponding to a conjunction of ; or 2) , where , , satisfies 1).

Quine's algorithm. Here one considers at each step the neighbourhood of one of the conjunctions in the disjunctive normal form . As the algorithm is executed for each conjunction, one attempts to compute one of the following properties:

— "A occurs in all minimal disjunctive normal forms" ; and

— "A does not occur in any minimal disjunctive normal form" .

The algorithm works as follows. 1) The neighbourhood is successively formed for each conjunction in . The inclusion is verified. If this is not the case, then is marked in some way as belonging to all minimal disjunctive normal forms. One says that is part of the kernel of (is a kernel conjunction). 2) Let the conjunctions be marked in in the first stage. The remaining conjunctions in are ordered, and the inclusion is checked for each such conjunction . Conjunctions satisfying this relation do not occur in any minimal disjunctive normal form and are removed from .

Regular points algorithm. During each step of this algorithm one examines the neighbourhood of a conjunction in the disjunctive normal form , and the conjunctions not occurring in any dead-end disjunctive normal form, and hence not occurring in any minimal disjunctive normal form either, are eliminated. The description of the algorithm involves the concept of an -bundle in , which, for this point in , is the set of intervals such that , . For a conjunction in a point of is called regular with respect to if there exists a point such that and . A set is called regular with respect to if all its points are regular with respect to . This algorithm is based on the fact that a conjunction of the abridged disjunctive normal form of a function does not occur in any dead-end disjunctive normal form of if and only if is a regular set with respect to . The algorithm checks whether in a certain sequence the conjunction intervals occurring in the disjunctive normal form are regular sets and eliminates those that are regular. Whether or not an interval is regular with respect to is completely determined by the neighbourhood but not, in general, by the neighbourhood .

The -algorithm. The concept employed here is that of a disjunctive normal form that is minimal with respect to a disjunctive normal form , i.e. one that is minimal among all disjunctive normal forms that are equivalent to and are obtained from by omission of certain elementary conjunctions. Two properties of an elementary conjunction in a disjunctive normal form are considered:

— "A occurs in all disjunctive normal forms that are minimal with respect to N" ; and

— "A occurs in no disjunctive normal form that is minimal with respect to N" .

It is assumed that if the property holds, and otherwise. It is also assumed that disjunctive normal forms are formed from conjunctions with informative marks , where . The equality means that the property has not been calculated , while the equalities mean that . A conjunction with informative marks () is denoted by . The -algorithm computes the values of the properties and for the conjunctions in the disjunctive normal form , using for this purpose only the conjunctions of the neighbourhood and their informative marks. For a conjunction of rank of a set is called a set of the first type relative to if contains conjunctions of ranks such that and .

The difference of two disjunctive normal forms and is the disjunctive normal form consisting of the elementary conjunctions occurring in but not in .

Before the application of the -algorithm all conjunctions of the disjunctive normal form have the mark . After steps have been performed and the conjunctions have received the mark , and the conjunctions have received the mark , the -th step consists of the following. The conjunctions in the disjunctive normal form are ordered in some way. If the disjunctive normal form is empty, the -algorithm is terminated. If it is not, the conjunctions of this disjunctive normal form are ordered in some way; the first conjunction in the sequence and its neighbourhoods and in the disjunctive normal form are singled out, and the relation

is checked. If it is satisfied, the mark over is replaced by and the -th step of the -algorithm is terminated. If not, then a check is made whether or not can be represented in the form , where is a regular set relative to and is a set of the first type relative to . If can be represented in this form, the mark over is replaced by and the -th step of the -algorithm is terminated; if this is not possible, the procedure is applied to the second conjunction in the sequence, etc. If the mark does not change in any one of these conjunctions, then after all the conjunctions have been examined, the operation of the -algorithm is terminated.

If the abridged disjunctive normal form of a function is taken for , then no conjunctions that obtained in the algorithm the mark occur in any minimal disjunctive normal form of ; they are eliminated from . Conjunctions that obtained the mark occur in all minimal disjunctive normal forms of . Various special cases of the -algorithm have also been considered.

The ring algorithm places over the conjunctions informative marks , with the same meaning as in the -algorithm. At each step of the ring algorithm use is made of the conjunctions contained in the -th order neighbourhood of some conjunction and of their informative marks. A simplified version of this algorithm is outlined below. The ring algorithm in its complete form is the best local algorithm with a special memory relative to the neighbourhoods . The algorithms described above are special cases of the general ring algorithm. If

and

then to each subset a Boolean function that is not everywhere defined is assigned, such that the set of its ones is and the set of its zeros is ; the function is not defined on . The set of such functions is denoted by . Prior to the beginning of the algorithm the conjunctions of the disjunctive normal form in question have the mark . If, after steps have been completed, conjunctions with the mark and conjunctions with the mark are obtained, then the -th step is performed as follows. The conjunctions of the disjunctive normal forms are ordered in some way. If the disjunctive normal form is empty, the algorithm is terminated. If not, then all conjunctions of this disjunctive normal form are ordered in some way. For the conjunction which is the first in the sequence and for all from the set , all disjunctive normal forms which realize on its domain of definition, which consist of conjunctions in and which contain the least number of variable symbols as compared with other such disjunctive normal forms, are found. Among them one selects all disjunctive normal forms which, first, do not contain the conjunctions and, secondly, contain all the conjunctions , , for which . If for all in the conjunction occurs in all disjunctive normal forms selected, then the mark over is replaced by and the -th step of the algorithm is terminated. If does not occur in any disjunctive normal form selected, then the mark is changed into and the -th step of the algorithm is terminated. Otherwise, the procedure just described is applied to the conjunction that is next in sequence, etc. If the mark cannot be changed for any conjunction, the algorithm terminates at the -th step. All conjunctions obtained in the ring algorithm over the abridged disjunctive normal form of a function with mark (or, respectively, ) occur in all minimal disjunctive normal forms (or, do not occur in any minimal disjunctive normal form) of . The algorithms just described yield identical results, whatever the manner of ordering of the conjunctions in the disjunctive normal form.

The task of selecting all conjunctions occurring in at least one or not occurring in any minimal disjunctive normal form cannot be solved by algorithms working with if is bounded or increases too slowly as the number of variables increases. This situation does not change if to the properties stored in the algorithm a bounded set of properties or one that increases too slowly as increases is added.

References

[1]	S.V. Yablonskii, "Functional constructions in -placed logic" Trudy Mat. Inst. Steklov. , 51 (1958) pp. 5–142 (In Russian)
[2]	Yu.I. Zhuravlev, "Set-theoretical methods in the algebra of logic" Problemy Kibernet. , 8 (1962) pp. 5–44 (In Russian)
[3]	W.V. Quine, "On cores and prime implicants of truth functions" Amer. Math. Monthly , 66 (1959) pp. 755–760 MR0108439 Zbl 0201.32203