Boolean functions, normal forms of

Formulas of a special kind realizing Boolean functions. One distinguishes between disjunctive normal forms (cf. Boolean functions, minimization of) and conjunctive normal forms. A product , where if and if , is called an elementary conjunction of rank if all its variables are different; "1" is considered to be an elementary conjunction of rank zero. A logical sum is called an elementary disjunction of rank if all its variables are different; "0" is considered to be an elementary disjunction of rank zero.

A formula , where are distinct elementary conjunctions of ranks , respectively, is called a disjunctive normal form, and the number is called its complexity; a formula , where are different elementary disjunctions of ranks , respectively, is called a conjunctive normal form, and the number is called its complexity. Every Boolean function that does not vanish identically can be defined by a disjunctive normal form which is, generally speaking, not unique. The same applies to conjunctive normal forms and functions that do not identically vanish.

From a table defining a Boolean function one easily obtains the perfect disjunctive normal form , where , , and the sets are such that . The perfect disjunctive normal form realizing a Boolean function is unique. The perfect conjunctive normal form is defined similarly.

Since for "almost-all" Boolean functions the number of unit sets varies between and , the asymptotic complexity of the perfect disjunctive normal form for "almost-all" Boolean functions is . The maximal complexity of the perfect disjunctive normal forms for functions in variables is attained for functions that vanish at a single point. This complexity is .

The main problem in the theory of normal forms of Boolean functions is that of minimizing Boolean functions, i.e. the construction of conjunctive or disjunctive normal forms of minimal complexity — minimal conjunctive or disjunctive normal forms for any given Boolean function (cf. Boolean functions, minimization of; Algorithm, local). Here, by virtue of the duality principle, it is sufficient to consider disjunctive normal forms only. In connection with the problem of minimizing Boolean functions one also considers abridged dead-end, shortest and minimal disjunctive normal forms. An important problem in the theory of disjunctive normal forms is the search for numerical characteristics of them, and characteristics connecting various types of disjunctive normal forms of a given function.

The abridged disjunctive normal form is uniquely constructed from a Boolean function by means of a fairly simple algorithm. Its most important property is the fact that every minimal disjunctive normal form of a function and at least one shortest form can be obtained from the abridged disjunctive normal form by the elimination of certain elementary conjunctions. Therefore many minimization algorithms employ the abridged disjunctive normal form as the initial specification of a Boolean function. It is of major interest in this context to define the complexity of abridged disjunctive normal forms for "almost-all" functions and to determine the absolute maximum of this complexity. If is the number of elementary conjunctions in the abridged disjunctive normal form of a Boolean function and if

then the following estimates hold:

and for "almost-all" Boolean functions

It is clear from these results and from the estimates of the complexity of the perfect disjunctive normal form that the complexity of the abridged disjunctive normal form is much higher than that of the perfect disjunctive normal form, both in the "typical" and in the "record-breaking" cases. Unlike the perfect and the abridged disjunctive normal form, a given Boolean function may have many dead-end and minimal disjunctive normal forms. Let be the number of dead-end disjunctive normal forms and let be the number of minimal disjunctive normal forms of a Boolean function ,

Then the following estimates hold:

and for "almost-all" Boolean functions

A non-trivial upper estimate for and a non-trivial estimate for for "almost-all" functions are as yet (1977) not known. Complexity estimates of dead-end and of minimal disjunctive normal forms are of great interest in problems of minimization of Boolean functions. Let be the number of elementary conjunctions in a dead-end disjunctive normal form of the function ; let be the number of elementary conjunctions in a shortest disjunctive normal form of ,

The following estimates then hold:

For "almost-all" Boolean functions and for almost-all dead-end disjunctive normal forms :

For "almost-all" Boolean functions :

These estimates show that the shortest (and also the minimal) disjunctive normal forms of "almost-all" Boolean functions account for only a small fraction of the number of dead-end disjunctive normal forms. There are also estimates of the relative complexity of dead-end and shortest disjunctive normal forms of Boolean functions. Let be the maximal number of elementary conjunctions in a dead-end disjunctive normal form of a function . For "almost-all" Boolean functions

The maximum value of the ratio can be estimated from below by , as . Estimates of — the so-called scatter of — have also been obtained. Here

where and are arbitrary dead-end disjunctive normal forms realizing , and is the number of characters in the dead-end disjunctive normal form . Examples of Boolean functions with have been constructed; it has been established, however, that for "almost-all" Boolean functions

The estimates above give a fairly complete idea of the difficulties that arise when Boolean functions are minimized according to the scheme: perfect disjunctive normal form — abridged disjunctive normal form — dead-end disjunctive normal form — minimal disjunctive normal form.

References

[1]	Yu.L. Vasil'ev, "On comparing the complexity of typical and disjunctive normal forms" Problemy Kibernet. : 10 (1963) pp. 5–61 (In Russian)
[2]	V.V. Glagolev, "Certain estimates of the disjunctive normal forms of functions of the algebra of logic" Problemy Kibernet. , 19 (1967) pp. 75–94 (In Russian) MR225634
[3]	A.D. Korshunov, "The upper complexity bound of the shortest disjunctive normal forms of almost all Boolean functions" Cybernetics , 5 : 6 (1969) pp. 705–715 Kibernetika (Kiev) : 6 (1969) pp. 1–8
[4]	A.A. Sapozhenko, "On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions" Math. Notes , 4 : 6 (1968) pp. 881 Mat. Zametki , 4 : 6 (1968) pp. 649–658 Zbl 0177.02001