Namespaces
Variants
Actions

Difference between revisions of "Boolean functions, metric theory of"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
b0169501.png
 +
$#A+1 = 144 n = 0
 +
$#C+1 = 144 : ~/encyclopedia/old_files/data/B016/B.0106950 Boolean functions, metric theory of
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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.
 
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
+
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|Boolean functions, normal forms of]]). An upper estimate of this ratio is $  2 ^ { \mathop{\rm Dim}  f } $.  
 +
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>
+
$$
 +
\mathop{\rm Dim}  f
 +
(x _ {1} \dots x _ {n} )  \leq  \
 +
[  \mathop{\rm log} _ {2}  n] + 1
 +
$$
  
 
is valid for "almost-all" Boolean functions.
 
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" />.
+
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|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
  
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
+
$$
 +
p (f) = \
 +
\max _ { {\mathfrak A \in \mathfrak N _ {f} } }  k ( \mathfrak A , f)
 +
$$
  
<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  $  f $.
 +
For "almost-all" Boolean functions
  
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
+
$$
 +
p (f (x _ {1} \dots x _ {n} ))  \sim \
  
<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>
+
\frac{n}{ \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n }
 +
.
 +
$$
  
 
Let
 
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>
+
$$
 +
p (n)  = \
 +
\max _ {f (x _ {1} \dots x _ {n} ) } \
 +
p (f (x _ {1} \dots x _ {n} )).
 +
$$
  
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
+
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|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
  
<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>
+
$$
 +
c _ {1} \cdot 2  ^ {n}  < p (n)  < c _ {2} \cdot 2  ^ {n} ,
 +
$$
  
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.
+
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 <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 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 <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" />.
+
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 <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
+
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
  
<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>
+
$$
 +
\mathop{\rm log} _ {2}  \psi (n)  \sim \
 +
\left (
 +
\begin{array}{c}
 +
n \\
 +
\left [
 +
\frac{n}{2}
 +
\right ]
 +
\end{array}
 +
\
 +
\right )
 +
$$
  
 
is also known.
 
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
+
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
  
<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>
+
$$
 +
m (n)  = \
 +
\max _ {f (x _ {1} \dots x _ {n} ) } \
 +
m (f).
 +
$$
  
The quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016950/b016950117.png" /> satisfies the asymptotic equality:
+
The quantity $  m(n) $
 +
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>
+
$$
 +
m (n)  \sim  2
 +
\left (
 +
\begin{array}{c}
 +
n \\
 +
\left [ {
 +
\frac{n}{2}
 +
} \right ]
 +
\end{array}
 +
\
 +
\right ) .
 +
$$
  
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.
+
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 <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" />.
+
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 <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
+
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
  
<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>
+
$$
 +
t (n)  = \max _ {F(x _ {1} \dots x _ {n} ) }  t _ {F} (n) .
 +
$$
  
 
It is known that
 
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>
+
$$
 +
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 <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 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.
 
The metric theory of Boolean functions also deals with problems of computing characteristics connected with the problem of minimization of Boolean functions.

Latest revision as of 06:28, 30 May 2020


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
How to Cite This Entry:
Boolean functions, metric theory of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_functions,_metric_theory_of&oldid=46115
This article was adapted from an original article by Yu.I. Zhuravlev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article