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 ![]() |
[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 |
Boolean functions, minimization of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_functions,_minimization_of&oldid=24382