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 be the set of vertices of the -dimensional unit cube on which a function is equal to one. Consider all maximal intervals of the function and select the interval of the largest dimension . The quantity is called the dimension of and is denoted by . In terms of the dimension one can estimate the complexity ratio of the most complex dead-end and the shortest disjunctive normal forms of (cf. Boolean functions, normal forms of). An upper estimate of this ratio is . The inequality

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 are of dimension close to .

Let be the -th order smooth neighbourhood (cf. Algorithm, local) of an elementary conjunction occurring in the abridged disjunctive normal form of , and let be the minimal value of the order of the neighbourhood in which includes all elementary conjunctions occurring in the abridged disjunctive normal form . The quantity

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

Let

It is known that can be realized on a Boolean function of a special kind, which is called a chain. A function is called a chain if the set of its zeros can be represented as a sequence such that , where is the Hamming distance (cf. Code); the distance between other pairs (possibly except for the pair ()) is larger than one, and no interval of dimension 2 is completely contained in the set of ones of . The extent of the chain is . Therefore, the problem of calculating reduces to the construction of a chain with maximal in the -dimensional unit cube. It has been shown by direct construction of such chains that

where are constants. The construction of closed chains (cycles), i.e. of chains in which , with maximum cardinality of the set 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 of vertices of the -dimensional unit cube is called connected if for any point there exists a point in such that . A point in is called isolated if all such that satisfy the condition . The following theorem holds: For "almost-all" Boolean functions the set of ones, , splits into the sum of a connected set and a set of isolated points. The cardinality of the connected set is not less than and the number of isolated points does not exceed .

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 generated by a Boolean function has as vertices the points of and as edges the pairs of points of at Hamming distance one from each other. The distance between two vertices and of is defined as the length of the shortest chain connecting with . (It is assumed that the vertices and belong to the same connected component of .) The deviation of the vertex in is the quantity , where the maximum is taken over all the vertices of that belong to the same connected component as . The radius of a connected component of is the number . The quantity , where the maximum is taken over all connected components of , is called the radius of . The diameter of is the number , where the maximum is taken over all pairs of vertices that belong to the same connected component. For "almost-all" Boolean functions the quantities and are such that and .

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 , be binary ordered samples. One says that if , . A Boolean function is called monotone if implies that . It is of interest to determine the exact number of distinct monotone Boolean functions in the variables . This number is known for only a few small values of . The asymptotic equality

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 for the computation of a monotone Boolean function at any point . If it can be established in the course of the computations that for some point , then for all . If , the function is known (and vanishes) at all points . Therefore, to effect the decoding, i.e. to completely reproduce the function , the algorithm need only compute its values in a certain set of points. Let denote the minimum number of points sufficient to reproduce completely. Let

The quantity satisfies the asymptotic equality:

The estimate of 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 -dimensional unit cube. A collection of variables is called essential for a Boolean function that is not everywhere defined if and if there exists a Boolean function that is not everywhere defined such that throughout the domain of definition of . An essential collection is called a dead-end collection for if no proper part of it is essential for .

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 be the system of subsets of the set that satisfies the following condition: If and if is an arbitrary subset of , then . Then there exists a Boolean function , not everywhere defined, such that is a system of essential collections for . Let be the number of distinct dead-end collections for and put

It is known that

The algorithm for the construction of all dead-end collections for has maximal computational labour 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 .)

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