View source for 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169501.png" /> be the set of vertices of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169502.png" />-dimensional unit cube on which a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169503.png" /> is equal to one. Consider all maximal intervals of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169504.png" /> and select the interval of the largest dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169505.png" />. The quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169506.png" /> is called the dimension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169507.png" /> and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169508.png" />. In terms of the dimension one can estimate the complexity ratio of the most complex dead-end and the shortest disjunctive normal forms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b0169509.png" /> (cf. [[Boolean functions, normal forms of|Boolean functions, normal forms of]]). An upper estimate of this ratio is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695010.png" />. The inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695011.png" /></td> </tr></table>

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695012.png" /> are of dimension close to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695013.png" />.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695014.png" /> be the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695015.png" />-th order smooth neighbourhood (cf. [[Algorithm, local|Algorithm, local]]) of an elementary conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695016.png" /> occurring in the abridged disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695017.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695018.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695019.png" /> be the minimal value of the order of the neighbourhood in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695020.png" /> includes all elementary conjunctions occurring in the abridged disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695021.png" />. The quantity

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695022.png" /></td> </tr></table>

is called the extent of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695023.png" />. For  "almost-all"  Boolean functions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695024.png" /></td> </tr></table>

Let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695025.png" /></td> </tr></table>

It is known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695026.png" /> can be realized on a Boolean function of a special kind, which is called a chain. A function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695027.png" /> is called a chain if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695028.png" /> of its zeros can be represented as a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695029.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695030.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695031.png" /> is the Hamming distance (cf. [[Code|Code]]); the distance between other pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695032.png" /> (possibly except for the pair (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695033.png" />)) is larger than one, and no interval of dimension 2 is completely contained in the set of ones of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695034.png" />. The extent of the chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695035.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695036.png" />. Therefore, the problem of calculating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695037.png" /> reduces to the construction of a chain with maximal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695038.png" /> in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695039.png" />-dimensional unit cube. It has been shown by direct construction of such chains that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695040.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695041.png" /> are constants. The construction of closed chains (cycles), i.e. of chains in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695042.png" />, with maximum cardinality of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695043.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695044.png" /> of vertices of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695045.png" />-dimensional unit cube is called connected if for any point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695046.png" /> there exists a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695047.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695048.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695049.png" />. A point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695050.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695051.png" /> is called isolated if all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695052.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695053.png" /> satisfy the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695054.png" />. The following theorem holds: For  "almost-all"  Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695055.png" /> the set of ones, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695056.png" />, splits into the sum of a connected set and a set of isolated points. The cardinality of the connected set is not less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695057.png" /> and the number of isolated points does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695058.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695059.png" /> generated by a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695060.png" /> has as vertices the points of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695061.png" /> and as edges the pairs of points of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695062.png" /> at Hamming distance one from each other. The distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695063.png" /> between two vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695064.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695065.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695066.png" /> is defined as the length of the shortest chain connecting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695067.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695068.png" />. (It is assumed that the vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695070.png" /> belong to the same connected component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695071.png" />.) The deviation of the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695072.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695073.png" /> is the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695074.png" />, where the maximum is taken over all the vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695075.png" /> that belong to the same connected component as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695076.png" />. The radius of a connected component <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695077.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695078.png" /> is the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695079.png" />. The quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695080.png" />, where the maximum is taken over all connected components of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695081.png" />, is called the radius of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695082.png" />. The diameter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695083.png" /> is the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695084.png" />, where the maximum is taken over all pairs of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695085.png" /> that belong to the same connected component. For  "almost-all"  Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695086.png" /> the quantities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695087.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695088.png" /> are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695090.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695091.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695092.png" /> be binary ordered samples. One says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695093.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695094.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695095.png" />. A Boolean function is called monotone if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695096.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695097.png" />. It is of interest to determine the exact number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695098.png" /> of distinct monotone Boolean functions in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b01695099.png" />. This number is known for only a few small values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950100.png" />. The asymptotic equality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950101.png" /></td> </tr></table>

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950102.png" /> for the computation of a monotone Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950103.png" /> at any point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950104.png" />. If it can be established in the course of the computations that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950105.png" /> for some point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950106.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950107.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950108.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950109.png" />, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950110.png" /> is known (and vanishes) at all points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950111.png" />. Therefore, to effect the decoding, i.e. to completely reproduce the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950112.png" />, the algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950113.png" /> need only compute its values in a certain set of points. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950114.png" /> denote the minimum number of points sufficient to reproduce <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950115.png" /> completely. Let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950116.png" /></td> </tr></table>

The quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950117.png" /> satisfies the asymptotic equality:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950118.png" /></td> </tr></table>

The estimate of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950119.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950120.png" />-dimensional unit cube. A collection of variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950121.png" /> is called essential for a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950122.png" /> that is not everywhere defined if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950123.png" /> and if there exists a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950124.png" /> that is not everywhere defined such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950125.png" /> throughout the domain of definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950126.png" />. An essential collection is called a dead-end collection for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950127.png" /> if no proper part of it is essential for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950128.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950129.png" /> be the system of subsets of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950130.png" /> that satisfies the following condition: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950131.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950132.png" /> is an arbitrary subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950133.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950134.png" />. Then there exists a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950135.png" />, not everywhere defined, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950136.png" /> is a system of essential collections for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950137.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950138.png" /> be the number of distinct dead-end collections for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950139.png" /> and put

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950140.png" /></td> </tr></table>

It is known that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950141.png" /></td> </tr></table>

The algorithm for the construction of all dead-end collections for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950142.png" /> has maximal computational labour <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950143.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950144.png" />.)

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

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.K. Korobkov,   "On monotone functions of the algebra of logic"  ''Problemy Kibernet.'' , '''13'''  (1965)  pp. 5–28  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Sapozhenko,   "Metric properties of almost all functions of the algebras of logic"  ''Diskret. Anal.'' , '''10'''  (1967)  pp. 91–119  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  D.J. Kleitman,   "On Dedekind's problem: the number of monotone Boolean functions"  ''Proc. Amer. Math. Soc.'' , '''21'''  (1969)  pp. 677–682</TD></TR></table>