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 $ x _ {i _ {1} } ^ {\sigma _ {1} } \dots x _ {i _ {k} } ^ {\sigma _ {k} } $, where $ x ^ \sigma = x $ if $ \sigma = 1 $ and $ x ^ \sigma = Cx $ if $ \sigma = 0 $, is called an elementary conjunction of rank $ k $ if all its variables are different; "1" is considered to be an elementary conjunction of rank zero. A logical sum $ x _ {j _ {1} } ^ {\sigma _ {1} } \lor {} \dots \lor x _ {j _ {r} } ^ {\sigma _ {r} } $ is called an elementary disjunction of rank $ r $ if all its variables are different; "0" is considered to be an elementary disjunction of rank zero.

A formula $ \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {l} $, where $ \mathfrak A _ {1} \dots \mathfrak A _ {l} $ are distinct elementary conjunctions of ranks $ r _ {1} \dots r _ {l} $, respectively, is called a disjunctive normal form, and the number $ \sum _ {i=1 } ^ {l} r _ {i} $ is called its complexity; a formula $ \mathfrak B _ {1} \dots \mathfrak B _ {t} $, where $ \mathfrak B _ {1} \dots \mathfrak B _ {t} $ are different elementary disjunctions of ranks $ \rho _ {1} \dots \rho _ {t} $, respectively, is called a conjunctive normal form, and the number $ \sum _ {i=1 } ^ {t} \rho _ {i} $ 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 $ f(x _ {1} \dots x _ {n} ) $ one easily obtains the perfect disjunctive normal form $ \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {s} $, where $ \mathfrak A _ {i} = x _ {1} ^ {\sigma _ {i1} } \dots x _ {n} ^ {\sigma _ {in} } $, $ i = 1 \dots s $, and the sets $ \sigma _ {i1} \dots \sigma _ {in} $ are such that $ f( \sigma _ {i1} \dots \sigma _ {in} ) = 1 $. The perfect disjunctive normal form realizing a Boolean function $ f $ is unique. The perfect conjunctive normal form is defined similarly.

Since for "almost-all" Boolean functions the number of unit sets varies between $ 2 ^ {n-1} - \sqrt n \cdot 2 ^ {n/2} $ and $ 2 ^ {n-1} + \sqrt n \cdot 2 ^ {n/2} $, the asymptotic complexity of the perfect disjunctive normal form for "almost-all" Boolean functions is $ n \cdot {2 ^ {n-1} } $. The maximal complexity of the perfect disjunctive normal forms for functions in $ n $ variables is attained for functions that vanish at a single point. This complexity is $ n \cdot ( {2 ^ {n} } - 1) $.

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 $ S _ {f} (n) $ is the number of elementary conjunctions in the abridged disjunctive normal form of a Boolean function $ f(x _ {1} \dots x _ {n} ) $ and if

$$ S (n) = \ \max _ {f (x _ {1} \dots x _ {n} ) } \ S _ {f} (n), $$

then the following estimates hold:

$$ C _ {1} \frac{3 ^ {n} }{n} \lce \ S (n) \lce \ C _ {2} \cdot \frac{3 ^ {n} }{\sqrt n } , $$

and for "almost-all" Boolean functions

$$ n ^ {(1 - \epsilon ) \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n } 2 ^ {n} < S _ {f} (n) < \ n ^ {(1 + \epsilon ) \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n } 2 ^ {n} , $$

$$ \epsilon \rightarrow 0 \textrm{ as } n \rightarrow \infty . $$

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 $ t _ {f} (n) $ be the number of dead-end disjunctive normal forms and let $ m _ {f} (n) $ be the number of minimal disjunctive normal forms of a Boolean function $ f(x _ {1} \dots x _ {n} ) $,

$$ t (n) = \ \max _ {f (x _ {1} \dots x _ {n} ) } \ t _ {f} (n),\ \ m (n) = \ \max _ {f (x _ {1} \dots x _ {n} ) } \ m _ {f} (n). $$

Then the following estimates hold:

$$ (2 ^ {2 ^ {n} } ) ^ {\sqrt n } \leq \ t (n) \leq \ (2 ^ {2 ^ {n} } ) ^ {n/2} ,\ \ m (n) > (2 ^ {2 ^ {n} } ) ^ {\textrm{ const } \cdot \sqrt n } , $$

and for "almost-all" Boolean functions

$$ (2 ^ {2 ^ {n - 1 } } ) ^ {(1 - \epsilon ) \mathop{\rm log} _ {2} n \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n } < t _ {f} (n) < $$

$$ < \ (2 ^ {2 ^ {n - 1 } } ) ^ {(1 + \epsilon ) \mathop{\rm log} _ {2} n \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n } , $$

$$ \epsilon \rightarrow 0 \textrm{ as } n \rightarrow \infty . $$

A non-trivial upper estimate for $ m (n) $ and a non-trivial estimate for $ m _ {f} (n) $ 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 $ {\lambda _ {f} ^ {T} } (n) $ be the number of elementary conjunctions in a dead-end disjunctive normal form $ T $ of the function $ f(x _ {1} \dots x _ {n} ) $; let $ {l _ {f} } (n) $ be the number of elementary conjunctions in a shortest disjunctive normal form of $ f(x _ {1} \dots x _ {n} ) $,

$$ \lambda (n) = \ \max _ {f, T } \ \lambda _ {f} ^ {T} (n),\ \ l (n) = \max _ { f } \ l _ {f} (n). $$

The following estimates then hold:

$$ \lambda (n) \sim 2 ^ {n} ,\ \ l (n) = 2 ^ {n - 1 } . $$

For "almost-all" Boolean functions $ f(x _ {1} \dots x _ {n} ) $ and for almost-all dead-end disjunctive normal forms $ T $:

$$ \lambda _ {f} ^ {T} (n) \sim \ 2 ^ {n - 1 } . $$

For "almost-all" Boolean functions $ f(x _ {1} \dots x _ {n} ) $:

$$ \frac{2 ^ {n} }{ \mathop{\rm log} _ {2} n \cdot \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n } < \ l _ {f} (n) < \ \frac{2 ^ {n} }{ \mathop{\rm log} _ {2} n } . $$

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 $ {\lambda _ {f} } (n) $ be the maximal number of elementary conjunctions in a dead-end disjunctive normal form of a function $ f(x _ {1} \dots x _ {n} ) $. For "almost-all" Boolean functions

$$ \mathop{\rm log} _ {2} n < \ \frac{\lambda _ {f} (n) }{l _ {f} (n) } < \ \mathop{\rm log} _ {2} n \cdot \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n. $$

The maximum value of the ratio $ {\lambda _ {f} } (n)/ {l _ {f} } (n) $ can be estimated from below by $ 2 ^ {n(1 - \epsilon ) } $, $ \epsilon \rightarrow 0 $ as $ n \rightarrow \infty $. Estimates of $ y(f) $— the so-called scatter of $ f(x _ {1} \dots x _ {n} ) $— have also been obtained. Here

$$ y (f) = \ \max _ {\begin{array}{c} {} \\ T ^ { \prime } , T ^ { \prime\prime } \end{array} } \ \frac{L (T ^ { \prime } ) }{L (T ^ { \prime\prime } ) } , $$

where $ T ^ { \prime } $ and $ T ^ { \prime\prime } $ are arbitrary dead-end disjunctive normal forms realizing $ f(x _ {1} \dots x _ {n} ) $, and $ L(T) $ is the number of characters in the dead-end disjunctive normal form $ T $. Examples of Boolean functions with $ y(f) \geq 2 ^ {n(1 - o(1)) } $ have been constructed; it has been established, however, that for "almost-all" Boolean functions

$$ y (f) \leq \ \mathop{\rm log} _ {2} n \cdot \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n. $$

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