Boolean functions, metric theory of

The branch of mathematics in which one studies numerical characteristics and metric properties of Boolean functions. The principal parts of this theory are concerned with properties of "almost-all" Boolean functions (cf. Boolean functions, minimization of), properties of the set of all Boolean functions in a given number of variables, and special subclasses of Boolean functions. Another topic is the structure of the truth domains of Boolean functions with the aid of numerical characteristics that appear mainly in problems connected with the minimization of Boolean functions and the theory of local algorithms. These characteristics are the dimension and the extent of functions.

Let $ N _ {f(x _ {1} \dots x _ {n} ) } $ be the set of vertices of the $ n $- dimensional unit cube on which a function $ f(x _ {1} \dots x _ {n} ) $ is equal to one. Consider all maximal intervals of the function $ f(x _ {1} \dots x _ {n)} $ and select the interval of the largest dimension $ r $. The quantity $ r $ is called the dimension of $ f(x _ {1} \dots x _ {n} ) $ and is denoted by $ \mathop{\rm Dim} f(x _ {1} \dots x _ {n} ) $. In terms of the dimension one can estimate the complexity ratio of the most complex dead-end and the shortest disjunctive normal forms of $ f $( cf. Boolean functions, normal forms of). An upper estimate of this ratio is $ 2 ^ { \mathop{\rm Dim} f } $. The inequality

$$ \mathop{\rm Dim} f (x _ {1} \dots x _ {n} ) \leq \ [ \mathop{\rm log} _ {2} n] + 1 $$

is valid for "almost-all" Boolean functions.

In solving problems of minimization of Boolean functions it is of interest to calculate the dimension of "typical" maximal intervals. It has been proved that "almost-all" maximal intervals of "almost-all" Boolean functions $ f(x _ {1} \dots x _ {n} ) $ are of dimension close to $ \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n $.

Let $ S _ {k} ( \mathfrak A , f) $ be the $ k $- th order smooth neighbourhood (cf. Algorithm, local) of an elementary conjunction $ \mathfrak A $ occurring in the abridged disjunctive normal form $ \mathfrak N _ {f} $ of $ f $, and let $ k( \mathfrak A , f) $ be the minimal value of the order of the neighbourhood in which $ S _ {k} ( \mathfrak A , f) $ includes all elementary conjunctions occurring in the abridged disjunctive normal form $ \mathfrak N _ {f} $. The quantity

$$ p (f) = \ \max _ { {\mathfrak A \in \mathfrak N _ {f} } } k ( \mathfrak A , f) $$

is called the extent of $ f $. For "almost-all" Boolean functions

$$ p (f (x _ {1} \dots x _ {n} )) \sim \ \frac{n}{ \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n } . $$

Let

$$ p (n) = \ \max _ {f (x _ {1} \dots x _ {n} ) } \ p (f (x _ {1} \dots x _ {n} )). $$

It is known that $ p(n) $ can be realized on a Boolean function of a special kind, which is called a chain. A function $ \psi (x _ {1} \dots x _ {n} ) $ is called a chain if the set $ N _ \psi $ of its zeros can be represented as a sequence $ \widetilde \alpha _ {1} \dots \widetilde \alpha _ {q} $ such that $ \rho ( \widetilde \alpha _ {i} , \widetilde \alpha _ {i+1 } ) = 1 $, where $ \rho $ is the Hamming distance (cf. Code); the distance between other pairs $ \widetilde \alpha _ {r} , \widetilde \alpha _ {s} $( possibly except for the pair ( $ \widetilde \alpha _ {1} , \widetilde \alpha _ {q} $)) is larger than one, and no interval of dimension 2 is completely contained in the set of ones of $ \psi $. The extent of the chain $ \psi $ is $ q - 1 $. Therefore, the problem of calculating $ p(n) $ reduces to the construction of a chain with maximal $ q $ in the $ n $- dimensional unit cube. It has been shown by direct construction of such chains that

$$ c _ {1} \cdot 2 ^ {n} < p (n) < c _ {2} \cdot 2 ^ {n} , $$

where $ c _ {1} , c _ {2} $ are constants. The construction of closed chains (cycles), i.e. of chains in which $ \rho ( \widetilde \alpha _ {1} , \widetilde \alpha _ {q} ) = 1 $, with maximum cardinality of the set $ N _ \psi $ is an important part of the proof of the theorem that the properties of conjunctions "of occurring in the minimal or shortest disjunctive normal form" are non-computable in the class of local algorithms.

The following result clarifies the structure of the truth domains of "almost-all" Boolean functions. A set $ M $ of vertices of the $ n $- dimensional unit cube is called connected if for any point $ \widetilde \alpha \in M $ there exists a point $ \widetilde \beta $ in $ M $ such that $ \rho ( \widetilde \alpha , \widetilde \beta ) = 1 $. A point $ \widetilde \alpha $ in $ M $ is called isolated if all $ \widetilde \beta $ such that $ \rho ( \widetilde \alpha , \widetilde \beta ) = 1 $ satisfy the condition $ \widetilde \beta \notin M $. The following theorem holds: For "almost-all" Boolean functions $ f(x _ {1} \dots x _ {n} ) $ the set of ones, $ N _ {f(x _ {1} \dots x _ {n} ) } $, splits into the sum of a connected set and a set of isolated points. The cardinality of the connected set is not less than $ 2 ^ {n-1} - {\sqrt n } \cdot {2 ^ {n/2} } - {\textrm{ const } } \cdot \mathop{\rm log} _ {2} n $ and the number of isolated points does not exceed $ \textrm{ const } \cdot \mathop{\rm log} _ {2} n $.

The results obtained in calculating the extent of "almost-all" Boolean functions are closely connected with the results obtained on calculating the radii and diameters of the graphs generated by Boolean functions. The graph $ G(f) $ generated by a Boolean function $ f $ has as vertices the points of $ N _ {f} $ and as edges the pairs of points of $ N _ {f} $ at Hamming distance one from each other. The distance $ r _ {G} ( \widetilde \alpha , \widetilde \beta ) $ between two vertices $ \widetilde \alpha $ and $ \widetilde \beta $ of $ G(f) $ is defined as the length of the shortest chain connecting $ \widetilde \alpha $ with $ \widetilde \beta $. (It is assumed that the vertices $ \widetilde \alpha $ and $ \widetilde \beta $ belong to the same connected component of $ G(f) $.) The deviation of the vertex $ \widetilde \alpha $ in $ G(f) $ is the quantity $ l( \widetilde \alpha ) = \max {r _ {G} } ( \widetilde \alpha , \widetilde \beta ) $, where the maximum is taken over all the vertices of $ G $ that belong to the same connected component as $ \widetilde \alpha $. The radius of a connected component $ K $ of $ G $ is the number $ R (K) = \mathop{\rm min} _ {\widetilde \alpha \in K } l ( \widetilde \alpha ) $. The quantity $ R(G) = \max R(K) $, where the maximum is taken over all connected components of $ G $, is called the radius of $ G $. The diameter of $ G $ is the number $ D(G) = \max r _ {G} {( \widetilde \alpha , \widetilde \beta ) } $, where the maximum is taken over all pairs of vertices $ \widetilde \alpha , \widetilde \beta $ that belong to the same connected component. For "almost-all" Boolean functions $ f(x _ {1} \dots x _ {n} ) $ the quantities $ R(G) $ and $ D(G) $ are such that $ n - 2 \leq R(G(f)) \leq n - 1 $ and $ D(G(f)) = n - 1 $.

Of all the results of computations of numerical characteristics of individual classes of Boolean functions only those concerning monotone Boolean functions will be considered. Let $ \widetilde \alpha = ( \alpha _ {1} \dots \alpha _ {n} ) $, $ \widetilde \beta = ( \beta _ {1} \dots \beta _ {n} ) $ be binary ordered samples. One says that $ \widetilde \alpha \leq \widetilde \beta $ if $ \alpha _ {i} \leq \beta _ {i} $, $ i = 1 \dots n $. A Boolean function is called monotone if $ \widetilde \alpha \leq \widetilde \beta $ implies that $ f( \widetilde \alpha ) \leq f( \widetilde \beta ) $. It is of interest to determine the exact number $ \psi (n) $ of distinct monotone Boolean functions in the variables $ x _ {1} \dots x _ {n} $. This number is known for only a few small values of $ n $. The asymptotic equality

$$ \mathop{\rm log} _ {2} \psi (n) \sim \ \left ( \begin{array}{c} n \\ \left [ \frac{n}{2} \right ] \end{array} \ \right ) $$

is also known.

The problem of optimal decoding of a monotone Boolean function has a large number of applications in the solution of discrete extremal problems. Consider a given algorithm $ A $ for the computation of a monotone Boolean function $ f(x _ {1} \dots x _ {n} ) $ at any point $ \widetilde \alpha $. If it can be established in the course of the computations that $ f( \widetilde \alpha ) = 1 $ for some point $ \widetilde \alpha $, then $ f( \widetilde \beta ) = 1 $ for all $ \widetilde \beta \geq \widetilde \alpha $. If $ f( \widetilde \alpha ) = 0 $, the function $ f $ is known (and vanishes) at all points $ \widetilde \beta \leq \widetilde \alpha $. Therefore, to effect the decoding, i.e. to completely reproduce the function $ f $, the algorithm $ A $ need only compute its values in a certain set of points. Let $ m(f) $ denote the minimum number of points sufficient to reproduce $ f $ completely. Let

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

The quantity $ m(n) $ satisfies the asymptotic equality:

$$ m (n) \sim 2 \left ( \begin{array}{c} n \\ \left [ { \frac{n}{2} } \right ] \end{array} \ \right ) . $$

The estimate of $ m(f) $ can be improved if supplementary information about the monotone Boolean function is available.

A problem related to the problem of decoding monotone Boolean functions is that of calculating numerical characteristics of the set of essential variables of Boolean functions that are not defined everywhere, i.e. functions defined on some subset of the set of vertices of the $ n $- dimensional unit cube. A collection of variables $ x _ {i _ {1} } \dots x _ {i _ {k} } $ is called essential for a Boolean function $ F(x _ {1} \dots x _ {n} ) $ that is not everywhere defined if $ \{ x _ {i _ {1} } \dots x _ {i _ {k} } \} \subseteq \{ x _ {1} \dots x _ {n} \} $ and if there exists a Boolean function $ \phi (x _ {i _ {1} } \dots x _ {i _ {k} } ) $ that is not everywhere defined such that $ F(x _ {1} \dots x _ {n} ) \equiv \phi (x _ {i _ {1} } \dots x _ {i _ {k} } ) $ throughout the domain of definition of $ F $. An essential collection is called a dead-end collection for $ F $ if no proper part of it is essential for $ F $.

Each everywhere-defined Boolean function has a unique dead-end collection. For Boolean functions that are not defined everywhere the structure of the collections of essential variables is distinguished by its large variety. Let $ \Sigma $ be the system of subsets of the set $ \{ x _ {1} \dots x _ {n} \} $ that satisfies the following condition: If $ S \in \Sigma $ and if $ S ^ { \prime } $ is an arbitrary subset of $ \{ x _ {1} \dots x _ {n} \} $, then $ S \cup S ^ { \prime } \in \Sigma $. Then there exists a Boolean function $ F _ \Sigma (x _ {1} \dots x _ {n} ) $, not everywhere defined, such that $ \Sigma $ is a system of essential collections for $ F _ \Sigma $. Let $ {t _ {F} } (n) $ be the number of distinct dead-end collections for $ F(x _ {1} \dots x _ {n} ) $ and put

$$ t (n) = \max _ {F(x _ {1} \dots x _ {n} ) } t _ {F} (n) . $$

It is known that

$$ t (n) = \ \left ( \begin{array}{c} n \\ \left [ { \frac{n}{2} } \right ] \end{array} \ \right ) . $$

The algorithm for the construction of all dead-end collections for $ F(x _ {1} \dots x _ {n} ) $ has maximal computational labour $ 2 ( {} _ {[n/2]} ^ { n } ) $ and this maximum is in fact attained. (Here the unit of labour is defined as the labour involved in verifying whether or not a given collection of variables is essential for $ F $.)

The metric theory of Boolean functions also deals with problems of computing characteristics connected with the problem of minimization of Boolean functions.

References

[1]	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
[2]	Yu.I. Zhuravlev, "On algorithmic extraction of the set of essential variables of not everywhere defined functions of the algebra of logic" Problemy Kibernet. , 11 (1964) pp. 271–275 (In Russian)
[3]	V.K. Korobkov, "On monotone functions of the algebra of logic" Problemy Kibernet. , 13 (1965) pp. 5–28 (In Russian) MR209077
[4]	A.A. Sapozhenko, "Metric properties of almost all functions of the algebras of logic" Diskret. Anal. , 10 (1967) pp. 91–119 (In Russian)
[5]	A.A. Sapozhenko, "The order of the neighbourhood of maximal intervals for almost all logical functions" Soviet Math. Dokl. , 9 : 3 (1968) pp. 591–594 Dokl. Akad. Nauk SSSR , 180 : 1 (1968) pp. 32–35
[6]	D.J. Kleitman, "On Dedekind's problem: the number of monotone Boolean functions" Proc. Amer. Math. Soc. , 21 (1969) pp. 677–682 MR241334