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 $ m _ {f} $ be the complexity of the minimal disjunctive normal form of a function $ f $, let $ k _ {f} $ be the minimal complexity of its shortest disjunctive normal form and let $ l(n) $ be the largest of the ratios $ {k _ {f} } / {m _ {f} } $ over all functions in $ n $ variables. Then the following asymptotic relation holds:

$$ l (n) \sim { \frac{n}{2} } . $$

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 $ f(x _ {1} \dots x _ {n} ) $, which operates as follows: All disjunctive normal forms in the variables $ x _ {1} \dots x _ {n} $ are reviewed, and those which realize the function $ f $ and have minimal complexity are selected. In fact, this algorithm is not applicable even for small $ n $, 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 \lor A \cdot B \Rightarrow A \ ( \textrm{ absorption } ), $$

$$ xA \lor {Cx } B \Rightarrow xA \lor {Cx } B \lor AB. $$

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 $ E _ {n} $ denote the set of all vertices of the $ n $- dimensional unit cube. Each Boolean function $ f(x _ {1} \dots x _ {n} ) $ is in one-to-one correspondence with the subset $ N _ {f} $, $ N _ {f} \subseteq E _ {n} $, of vertices $ \widetilde \alpha $ such that $ f( \widetilde \alpha ) = 1 $. Let $ \mathfrak A $ be an elementary conjunction of rank $ r $. The set $ N _ {\mathfrak A} $ is then called an interval of rank $ r $ corresponding to the elementary conjunction $ \mathfrak A $. One says that a system of intervals $ N _ {\mathfrak A _ {1} } \dots N _ {\mathfrak A _ {m} } $ forms a covering of a set $ N \subseteq E _ {n} $ if

$$ N = N _ {\mathfrak A _ {1} } \cup \dots \cup N _ {\mathfrak A _ {m} } . $$

Since the equalities

$$ f = \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {m} \ \ \textrm{ and } \ \ N _ {f} = \ N _ {\mathfrak A _ {1} } \cup \dots \cup N _ {\mathfrak A _ {m} } $$

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 $ N _ {\mathfrak A} $ is called maximal for a function $ f $ if $ N _ {\mathfrak A} \subseteq N _ {f} $ and if there is no interval $ N _ {\mathfrak B} $ such that $ N _ {\mathfrak A} \subset N _ {\mathfrak B} \subseteq N _ {f} $. The construction of dead-end disjunctive normal forms of a function $ f $ reduces to a search for coverings of $ N _ {f} $ by maximal intervals such that no proper subset of it is a covering of $ N _ {f} $. 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 $ n $ arguments have no fewer than $ 2 ^ {2n} $ 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 $ f $( occurs in all minimal disjunctive normal forms for $ f $). 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 $ k $- th order neighbourhood $ S _ {k} ( \mathfrak A , \mathfrak N ) $ of an elementary conjunction $ \mathfrak A $ in a disjunctive normal form $ \mathfrak N $, $ \mathfrak A \in \mathfrak N $.

The zero-order neighbourhood $ S _ {0} ( \mathfrak A , \mathfrak N ) $ consists of the single conjunction $ \mathfrak A $. If $ S _ {k-1} ( \mathfrak A , \mathfrak N ) $ is the neighbourhood of order $ k - 1 $, then the neighbourhood $ S _ {k} ( \mathfrak A , \mathfrak N ) $ of order $ k $ consists of all conjunctions $ \mathfrak A _ {j} $ of the disjunctive normal form $ \mathfrak N $ that satisfy one of the following conditions: 1) $ N _ {\mathfrak A _ {j} } $ has a non-empty intersection with at least one interval corresponding to a conjunction of $ S _ {k-1} ( \mathfrak A , \mathfrak N ) $; or 2) $ N _ {\mathfrak A _ {j} } \subseteq \cup _ {i=1} ^ {r} N _ {\mathfrak B _ {i} } $, where $ N _ {\mathfrak B _ {i} } $, $ i = 1 \dots r $, satisfies 1).

Quine's algorithm. Here one considers at each step the neighbourhood $ S _ {1} ( \mathfrak A, \mathfrak N ) $ of one of the conjunctions in the disjunctive normal form $ \mathfrak N $. As the algorithm is executed for each conjunction, one attempts to compute one of the following properties:

$ P _ {1} ( \mathfrak A , \mathfrak N ) $— "A occurs in all minimal disjunctive normal forms" ; and

$ P _ {2} ( \mathfrak A , \mathfrak N ) $— "A does not occur in any minimal disjunctive normal form" .

The algorithm works as follows. 1) The neighbourhood $ S _ {1} ( \mathfrak A , \mathfrak N ) = \{ \mathfrak A , \mathfrak A _ {1} \dots \mathfrak A _ {m} \} $ is successively formed for each conjunction $ \mathfrak A $ in $ \mathfrak N $. The inclusion $ N _ {\mathfrak A} \subset \cup _ {i = 1 } ^ {m} N _ {\mathfrak A _ {i} } $ is verified. If this is not the case, then $ \mathfrak A $ is marked in some way as belonging to all minimal disjunctive normal forms. One says that $ \mathfrak A $ is part of the kernel of $ \mathfrak N $( is a kernel conjunction). 2) Let the conjunctions $ \mathfrak B _ {1} \dots \mathfrak B _ {q} $ be marked in $ \mathfrak N $ in the first stage. The remaining conjunctions in $ \mathfrak N $ are ordered, and the inclusion $ N _ {\mathfrak B} \subseteq \cup _ {i=1} ^ {q} N _ {\mathfrak B _ {i} } $ is checked for each such conjunction $ \mathfrak B $. Conjunctions satisfying this relation do not occur in any minimal disjunctive normal form and are removed from $ \mathfrak N $.

Regular points algorithm. During each step of this algorithm one examines the neighbourhood $ S _ {2} ( \mathfrak A , \mathfrak N ) $ of a conjunction $ \mathfrak A $ in the disjunctive normal form $ \mathfrak N $, 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 $ \widetilde \alpha $- bundle in $ \mathfrak N $, which, for this point $ \widetilde \alpha $ in $ N _ {\mathfrak N} $, is the set $ M( \widetilde \alpha , \mathfrak N ) $ of intervals $ N _ {\mathfrak A _ {j} } $ such that $ \mathfrak A _ {j} \in \mathfrak N $, $ \widetilde \alpha \in N _ {\mathfrak A _ {j} } $. For a conjunction $ \mathfrak A $ in $ \mathfrak N $ a point $ \widetilde \alpha $ of $ N _ {\mathfrak A} $ is called regular with respect to $ ( \mathfrak A , \mathfrak N ) $ if there exists a point $ \widetilde \alpha {} ^ \prime $ such that $ \widetilde \alpha {} ^ \prime \in N _ {\mathfrak N} \setminus N _ {\mathfrak A} $ and $ M( \widetilde \alpha {} ^ \prime , \mathfrak N ) \subseteq M ( \widetilde \alpha , \mathfrak N ) $. A set $ M \subseteq N _ {\mathfrak A} $ is called regular with respect to $ ( \mathfrak A , \mathfrak N ) $ if all its points are regular with respect to $ ( \mathfrak A , \mathfrak N ) $. This algorithm is based on the fact that a conjunction $ \mathfrak A $ of the abridged disjunctive normal form of a function $ f $ does not occur in any dead-end disjunctive normal form of $ f $ if and only if $ N _ {\mathfrak A} $ is a regular set with respect to $ ( \mathfrak A , \mathfrak N ) $. 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 $ N _ {\mathfrak A} $ is regular with respect to $ ( \mathfrak A , \mathfrak N ) $ is completely determined by the neighbourhood $ S _ {2} ( \mathfrak A , \mathfrak N ) $ but not, in general, by the neighbourhood $ S _ {1} ( \mathfrak A , \mathfrak N ) $.

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

$ P _ {1} ( \mathfrak A , \mathfrak N ) $— "A occurs in all disjunctive normal forms that are minimal with respect to N" ; and

$ P _ {2} ( \mathfrak A , \mathfrak N ) $— "A occurs in no disjunctive normal form that is minimal with respect to N" .

It is assumed that $ P _ {i} = 1 $ if the property $ P _ {i} $ holds, and $ P _ {i} = 0 $ otherwise. It is also assumed that disjunctive normal forms are formed from conjunctions with informative marks $ ( \omega _ {1} , \omega _ {2} ) $, where $ \omega _ {i} \in \{ 0, 1, \Delta \} $. The equality $ \omega _ {i} = \Delta $ means that the property $ P _ {i} $ has not been calculated $ (i = 1, 2) $, while the equalities $ \omega _ {i} = 1 $ mean that $ P _ {i} = \omega _ {i} $ $ (i = 1, 2) $. A conjunction $ \mathfrak A $ with informative marks ( $ \omega _ {1} , \omega _ {2} $) is denoted by $ \mathfrak A ^ {\omega _ {1} \omega _ {2} } $. The $ A $- algorithm computes the values of the properties $ P _ {1} $ and $ P _ {2} $ for the conjunctions $ \mathfrak A $ in the disjunctive normal form $ \mathfrak N $, using for this purpose only the conjunctions of the neighbourhood $ S _ {2} ( \mathfrak A , \mathfrak N ) $ and their informative marks. For a conjunction $ \mathfrak A $ of rank $ r $ of $ \mathfrak N $ a set $ M \subseteq N _ {\mathfrak A} $ is called a set of the first type relative to $ ( \mathfrak A , \mathfrak N ) $ if $ \mathfrak N $ contains conjunctions $ \mathfrak A _ {1} \dots \mathfrak A _ {m} $ of ranks $ r _ {1} \dots r _ {m} $ such that $ M \subseteq \cup _ {j=1} ^ {m} N _ {\mathfrak A _ {j} } $ and $ r > {\sum _ {j=1} ^ {m} } r _ {j} $.

The difference $ \mathfrak N _ {1} \setminus \mathfrak N _ {2} $ of two disjunctive normal forms $ \mathfrak N _ {1} $ and $ \mathfrak N _ {2} $ is the disjunctive normal form consisting of the elementary conjunctions occurring in $ \mathfrak N _ {1} $ but not in $ \mathfrak N _ {2} $.

Before the application of the $ A $- algorithm all conjunctions of the disjunctive normal form $ \mathfrak N $ have the mark $ ( \Delta , \Delta ) $. After $ i $ steps have been performed and the conjunctions $ {\mathfrak A _ {1} ^ \prime } \dots {\mathfrak A } _ {s} ^ \prime $ have received the mark $ (1, \Delta ) $, and the conjunctions $ {\mathfrak A } _ {1} ^ {\prime\prime} \dots {\mathfrak A } _ {t} ^ {\prime\prime} $ have received the mark $ ( \Delta , 1) $, the $ (i + 1) $- th step consists of the following. The conjunctions in the disjunctive normal form are ordered in some way. If the disjunctive normal form $ \mathfrak N \setminus ( \lor _ {j = 1 } ^ {s} {\mathfrak A } _ {j} ^ \prime \lor \lor _ {j = 1 } ^ {t} {\mathfrak A } _ {j} ^ {\prime\prime} ) $ is empty, the $ A $- algorithm is terminated. If it is not, the conjunctions of this disjunctive normal form are ordered in some way; the first conjunction $ \mathfrak A $ in the sequence and its neighbourhoods $ S _ {1} $ and $ S _ {2} $ in the disjunctive normal form $ \widetilde{\mathfrak N} = \mathfrak N \setminus ( \lor _ {j=1} ^ {t} {\mathfrak A } _ {j} ^ {\prime\prime} ) $ are singled out, and the relation

$$ N _ {\mathfrak A} \equiv \ \cup _ {\mathfrak B \in (S _ {1} ( \mathfrak A , \widetilde{\mathfrak N} ) \setminus \mathfrak A ) } N _ {\mathfrak B.} $$

is checked. If it is satisfied, the mark $ ( \Delta , \Delta ) $ over $ \mathfrak A $ is replaced by $ (1, \Delta ) $ and the $ (i + 1) $- th step of the $ A $- algorithm is terminated. If not, then a check is made whether or not $ N _ {\mathfrak A} $ can be represented in the form $ M _ {1} \cup M _ {2} $, where $ M _ {1} $ is a regular set relative to $ ( \mathfrak A , \mathfrak N ) $ and $ M _ {2} $ is a set of the first type relative to $ ( \mathfrak A , \mathfrak N ) $. If $ N _ {\mathfrak A} $ can be represented in this form, the mark $ ( \Delta , \Delta ) $ over $ \mathfrak A $ is replaced by $ ( \Delta , 1) $ and the $ (i + 1) $- th step of the $ A $- 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 $ A $- algorithm is terminated.

If the abridged disjunctive normal form $ \mathfrak N _ {f} $ of a function $ f $ is taken for $ \mathfrak N $, then no conjunctions that obtained in the algorithm the mark $ ( \Delta , 1) $ occur in any minimal disjunctive normal form of $ f $; they are eliminated from $ \mathfrak N _ {f} $. Conjunctions that obtained the mark $ (1, \Delta ) $ occur in all minimal disjunctive normal forms of $ f $. Various special cases of the $ A $- algorithm have also been considered.

The ring algorithm places over the conjunctions informative marks $ ( \omega _ {1} , \omega _ {2} ) $, with the same meaning as in the $ A $- algorithm. At each step of the ring algorithm use is made of the conjunctions contained in the $ k $- 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 $ S _ {k} ( \mathfrak A , \mathfrak N ) $. The algorithms described above are special cases of the general ring algorithm. If

$$ S _ {k - 1 } ( \mathfrak A , \mathfrak N ) = \ \{ \mathfrak A , \mathfrak A _ {1} \dots \mathfrak A _ {l} \} , $$

$$ S _ {k} ( \mathfrak A , \mathfrak N ) = \{ \mathfrak A , \mathfrak A _ {1} \dots \mathfrak A _ {l} ,\ \mathfrak A _ {l + 1 } \dots \mathfrak A _ {m} \} $$

and

$$ N _ {S _ {k - 1 } } = \ N _ {\mathfrak A} \cup \ \cup _ {i = 1 } ^ { l } N _ {\mathfrak A _ {i} } ,\ \ N _ {S _ {k} } = \ N _ {\mathfrak A} \cup \ \cup _ {j = 1 } ^ { m } N _ {\mathfrak A _ {j} } , $$

$$ Q (S _ {k} ) = N _ {S _ {k} } \setminus N _ {S _ {k - 1 } } , $$

then to each subset $ N \subseteq Q(S _ {k} ) $ a Boolean function $ f (x _ {1} \dots x _ {n} ) $ that is not everywhere defined is assigned, such that the set $ M _ {1} ^ {f} $ of its ones is $ N _ {S _ {k} } \setminus N $ and the set $ M _ {0} ^ {f} $ of its zeros is $ E _ {n} \setminus N _ {S _ {k} } $; the function $ f $ is not defined on $ N $. The set of such functions is denoted by $ F _ {k} ( \mathfrak A ) $. Prior to the beginning of the algorithm the conjunctions of the disjunctive normal form $ \mathfrak N $ in question have the mark $ ( \Delta , \Delta ) $. If, after $ i $ steps have been completed, conjunctions $ \mathfrak A _ {1} ^ \prime \dots \mathfrak A _ {s} ^ \prime $ with the mark $ (1, \Delta ) $ and conjunctions $ {\mathfrak A } _ {1} ^ {\prime\prime} \dots {\mathfrak A } _ {t} ^ {\prime\prime} $ with the mark $ ( \Delta , 1) $ are obtained, then the $ (i + 1) $- th step is performed as follows. The conjunctions of the disjunctive normal forms are ordered in some way. If the disjunctive normal form $ \mathfrak N \setminus ( \lor _ {j = 1 } ^ {s} {\mathfrak A } _ {j} ^ \prime \lor \lor _ {j = 1 } ^ {t} \mathfrak A _ {j} ^ {\prime\prime} ) $ is empty, the algorithm is terminated. If not, then all conjunctions of this disjunctive normal form are ordered in some way. For the conjunction $ \mathfrak A $ which is the first in the sequence and for all $ f $ from the set $ F _ {k} ( \mathfrak A ) $, all disjunctive normal forms which realize $ f $ on its domain of definition, which consist of conjunctions in $ S _ {k} ( \mathfrak A , \mathfrak N ) $ 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 $ \mathfrak A _ {1} ^ {\prime\prime} \dots \mathfrak A _ {t} ^ {\prime\prime} $ and, secondly, contain all the conjunctions $ \mathfrak A _ {j} ^ \prime $, $ j = 1 \dots s $, for which $ N _ {\mathfrak A} \cap (N _ {s _ {k} } \setminus N) = \emptyset $. If for all $ f $ in $ F _ {k} ( \mathfrak A ) $ the conjunction $ \mathfrak A $ occurs in all disjunctive normal forms selected, then the mark $ ( \Delta , \Delta ) $ over $ \mathfrak A $ is replaced by $ (1, \Delta) $ and the $ (i + 1) $- th step of the algorithm is terminated. If $ \mathfrak A $ does not occur in any disjunctive normal form selected, then the mark $ ( \Delta , \Delta ) $ is changed into $ ( \Delta , 1) $ and the $ (i + 1) $- 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 $ (i + 1) $- th step. All conjunctions obtained in the ring algorithm over the abridged disjunctive normal form $ \mathfrak N _ {f} $ of a function $ f $ with mark $ (1, \Delta ) $( or, respectively, $ ( \Delta , 1) $) occur in all minimal disjunctive normal forms (or, do not occur in any minimal disjunctive normal form) of $ f $. 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 $ S _ {k} ( \mathfrak A , \mathfrak N ) $ if $ k $ is bounded or increases too slowly as the number of variables $ n $ increases. This situation does not change if to the properties $ P _ {1} , P _ {2} $ stored in the algorithm a bounded set of properties or one that increases too slowly as $ n $ increases is added.

References

[1]	S.V. Yablonskii, "Functional constructions in $k$-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