Namespaces
Variants
Actions

Difference between revisions of "Boolean functions, normal forms of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
Formulas of a special kind realizing Boolean functions. One distinguishes between disjunctive normal forms (cf. [[Boolean functions, minimization of|Boolean functions, minimization of]]) and conjunctive normal forms. A product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169701.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169702.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169703.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169704.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169705.png" />, is called an elementary conjunction of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169706.png" /> if all its variables are different;  "1"  is considered to be an elementary conjunction of rank zero. A logical sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169707.png" /> is called an elementary disjunction of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169708.png" /> if all its variables are different;  "0"  is considered to be an elementary disjunction of rank zero.
+
<!--
 +
b0169701.png
 +
$#A+1 = 73 n = 0
 +
$#C+1 = 73 : ~/encyclopedia/old_files/data/B016/B.0106970 Boolean functions, normal forms of
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
A formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b0169709.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697010.png" /> are distinct elementary conjunctions of ranks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697011.png" />, respectively, is called a disjunctive normal form, and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697012.png" /> is called its complexity; a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697013.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697014.png" /> are different elementary disjunctions of ranks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697015.png" />, respectively, is called a conjunctive normal form, and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697016.png" /> is called its complexity. Every Boolean function that does not vanish identically can be defined by a disjunctive normal form which is, generally speaking, not unique. The same applies to conjunctive normal forms and functions that do not identically vanish.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
From a table defining a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697017.png" /> one easily obtains the perfect disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697018.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697020.png" />, and the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697021.png" /> are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697022.png" />. The perfect disjunctive normal form realizing a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697023.png" /> is unique. The perfect conjunctive normal form is defined similarly.
+
Formulas of a special kind realizing Boolean functions. One distinguishes between disjunctive normal forms (cf. [[Boolean functions, minimization of|Boolean functions, minimization of]]) and conjunctive normal forms. A product  $  x _ {i _ {1}  } ^ {\sigma _ {1} } \dots x _ {i _ {k}  } ^ {\sigma _ {k} } $,  
 +
where $  x  ^  \sigma  = x $
 +
if  $  \sigma = 1 $
 +
and  $  x  ^  \sigma  = Cx $
 +
if  $  \sigma = 0 $,  
 +
is called an elementary conjunction of rank  $  k $
 +
if all its variables are different; "1" is considered to be an elementary conjunction of rank zero. A logical sum  $  x _ {j _ {1}  } ^ {\sigma _ {1} } \lor {} \dots \lor x _ {j _ {r}  } ^ {\sigma _ {r} } $
 +
is called an elementary disjunction of rank  $  r $
 +
if all its variables are different; "0" is considered to be an elementary disjunction of rank zero.
  
Since for "almost-all" Boolean functions the number of unit sets varies between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697025.png" />, the asymptotic complexity of the perfect disjunctive normal form for "almost-all" Boolean functions is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697026.png" />. The maximal complexity of the perfect disjunctive normal forms for functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697027.png" /> variables is attained for functions that vanish at a single point. This complexity is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697028.png" />.
+
A formula  $  \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {l} $,
 +
where  $  \mathfrak A _ {1} \dots \mathfrak A _ {l} $
 +
are distinct elementary conjunctions of ranks  $  r _ {1} \dots r _ {l} $,
 +
respectively, is called a disjunctive normal form, and the number  $  \sum _ {i=1 }  ^ {l} r _ {i} $
 +
is called its complexity; a formula  $  \mathfrak B _ {1} \dots \mathfrak B _ {t} $,
 +
where  $  \mathfrak B _ {1} \dots \mathfrak B _ {t} $
 +
are different elementary disjunctions of ranks  $  \rho _ {1} \dots \rho _ {t} $,
 +
respectively, is called a conjunctive normal form, and the number  $  \sum _ {i=1 }  ^ {t} \rho _ {i} $
 +
is called its complexity. Every Boolean function that does not vanish identically can be defined by a disjunctive normal form which is, generally speaking, not unique. The same applies to conjunctive normal forms and functions that do not identically vanish.
 +
 
 +
From a table defining a Boolean function  $  f(x _ {1} \dots x _ {n} ) $
 +
one easily obtains the perfect disjunctive normal form  $  \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {s} $,
 +
where  $  \mathfrak A _ {i} = x _ {1} ^ {\sigma _ {i1} } \dots x _ {n} ^ {\sigma _ {in} } $,
 +
$  i = 1 \dots s $,
 +
and the sets  $  \sigma _ {i1} \dots \sigma _ {in} $
 +
are such that  $  f( \sigma _ {i1} \dots \sigma _ {in} ) = 1 $.
 +
The perfect disjunctive normal form realizing a Boolean function  $  f $
 +
is unique. The perfect conjunctive normal form is defined similarly.
 +
 
 +
Since for "almost-all" Boolean functions the number of unit sets varies between $  2  ^ {n-1} - \sqrt n \cdot 2  ^ {n/2} $
 +
and $  2  ^ {n-1} + \sqrt n \cdot 2  ^ {n/2} $,  
 +
the asymptotic complexity of the perfect disjunctive normal form for "almost-all" Boolean functions is $  n \cdot {2  ^ {n-1} } $.  
 +
The maximal complexity of the perfect disjunctive normal forms for functions in $  n $
 +
variables is attained for functions that vanish at a single point. This complexity is $  n \cdot ( {2  ^ {n} } - 1) $.
  
 
The main problem in the theory of normal forms of Boolean functions is that of minimizing Boolean functions, i.e. the construction of conjunctive or disjunctive normal forms of minimal complexity — minimal conjunctive or disjunctive normal forms for any given Boolean function (cf. [[Boolean functions, minimization of|Boolean functions, minimization of]]; [[Algorithm, local|Algorithm, local]]). Here, by virtue of the duality principle, it is sufficient to consider disjunctive normal forms only. In connection with the problem of minimizing Boolean functions one also considers abridged dead-end, shortest and minimal disjunctive normal forms. An important problem in the theory of disjunctive normal forms is the search for numerical characteristics of them, and characteristics connecting various types of disjunctive normal forms of a given function.
 
The main problem in the theory of normal forms of Boolean functions is that of minimizing Boolean functions, i.e. the construction of conjunctive or disjunctive normal forms of minimal complexity — minimal conjunctive or disjunctive normal forms for any given Boolean function (cf. [[Boolean functions, minimization of|Boolean functions, minimization of]]; [[Algorithm, local|Algorithm, local]]). Here, by virtue of the duality principle, it is sufficient to consider disjunctive normal forms only. In connection with the problem of minimizing Boolean functions one also considers abridged dead-end, shortest and minimal disjunctive normal forms. An important problem in the theory of disjunctive normal forms is the search for numerical characteristics of them, and characteristics connecting various types of disjunctive normal forms of a given function.
  
The abridged disjunctive normal form is uniquely constructed from a Boolean function by means of a fairly simple algorithm. Its most important property is the fact that every minimal disjunctive normal form of a function and at least one shortest form can be obtained from the abridged disjunctive normal form by the elimination of certain elementary conjunctions. Therefore many minimization algorithms employ the abridged disjunctive normal form as the initial specification of a Boolean function. It is of major interest in this context to define the complexity of abridged disjunctive normal forms for "almost-all" functions and to determine the absolute maximum of this complexity. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697029.png" /> is the number of elementary conjunctions in the abridged disjunctive normal form of a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697030.png" /> and if
+
The abridged disjunctive normal form is uniquely constructed from a Boolean function by means of a fairly simple algorithm. Its most important property is the fact that every minimal disjunctive normal form of a function and at least one shortest form can be obtained from the abridged disjunctive normal form by the elimination of certain elementary conjunctions. Therefore many minimization algorithms employ the abridged disjunctive normal form as the initial specification of a Boolean function. It is of major interest in this context to define the complexity of abridged disjunctive normal forms for "almost-all" functions and to determine the absolute maximum of this complexity. If $  S _ {f} (n) $
 +
is the number of elementary conjunctions in the abridged disjunctive normal form of a Boolean function $  f(x _ {1} \dots x _ {n} ) $
 +
and if
  
<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/b016970/b01697031.png" /></td> </tr></table>
+
$$
 +
S (n)  = \
 +
\max _ {f (x _ {1} \dots x _ {n} ) } \
 +
S _ {f} (n),
 +
$$
  
 
then the following estimates hold:
 
then the following estimates hold:
  
<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/b016970/b01697032.png" /></td> </tr></table>
+
$$
 +
C _ {1}
 +
\frac{3  ^ {n} }{n}
 +
  \lce \
 +
S (n)  \lce \
 +
C _ {2} \cdot
 +
 
 +
\frac{3  ^ {n} }{\sqrt n }
 +
,
 +
$$
  
and for "almost-all" Boolean functions
+
and 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/b016970/b01697033.png" /></td> </tr></table>
+
$$
 +
n ^ {(1 - \epsilon )  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n }
 +
2  ^ {n}  < S _ {f} (n)  < \
 +
n ^ {(1 + \epsilon )  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n } 2  ^ {n} ,
 +
$$
  
<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/b016970/b01697034.png" /></td> </tr></table>
+
$$
 +
\epsilon \rightarrow 0 \textrm{ as }  n \rightarrow \infty .
 +
$$
  
It is clear from these results and from the estimates of the complexity of the perfect disjunctive normal form that the complexity of the abridged disjunctive normal form is much higher than that of the perfect disjunctive normal form, both in the "typical" and in the "record-breaking" cases. Unlike the perfect and the abridged disjunctive normal form, a given Boolean function may have many dead-end and minimal disjunctive normal forms. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697035.png" /> be the number of dead-end disjunctive normal forms and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697036.png" /> be the number of minimal disjunctive normal forms of a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697037.png" />,
+
It is clear from these results and from the estimates of the complexity of the perfect disjunctive normal form that the complexity of the abridged disjunctive normal form is much higher than that of the perfect disjunctive normal form, both in the "typical" and in the "record-breaking" cases. Unlike the perfect and the abridged disjunctive normal form, a given Boolean function may have many dead-end and minimal disjunctive normal forms. Let $  t _ {f} (n) $
 +
be the number of dead-end disjunctive normal forms and let $  m _ {f} (n) $
 +
be the number of minimal disjunctive normal forms of a Boolean function $  f(x _ {1} \dots x _ {n} ) $,
  
<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/b016970/b01697038.png" /></td> </tr></table>
+
$$
 +
t (n)  = \
 +
\max _ {f (x _ {1} \dots x _ {n} ) } \
 +
t _ {f} (n),\ \
 +
m (n)  = \
 +
\max _ {f (x _ {1} \dots x _ {n} ) } \
 +
m _ {f} (n).
 +
$$
  
 
Then the following estimates hold:
 
Then the following estimates hold:
  
<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/b016970/b01697039.png" /></td> </tr></table>
+
$$
 +
(2 ^ {2  ^ {n} } ) ^ {\sqrt n }  \leq  \
 +
t (n)  \leq  \
 +
(2 ^ {2  ^ {n} } )  ^ {n/2} ,\ \
 +
m (n)  > (2 ^ {2  ^ {n} } ) ^ {\textrm{ const } \cdot \sqrt n } ,
 +
$$
  
and for "almost-all" Boolean functions
+
and 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/b016970/b01697040.png" /></td> </tr></table>
+
$$
 +
(2 ^ {2 ^ {n - 1 } } ) ^ {(1 - \epsilon )
 +
\mathop{\rm log} _ {2}  n  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n }
 +
< t _ {f} (n) <
 +
$$
  
<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/b016970/b01697041.png" /></td> </tr></table>
+
$$
 +
< \
 +
(2 ^ {2 ^ {n - 1 } } ) ^ {(1 + \epsilon )  \mathop{\rm log} _ {2}  n  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n } ,
 +
$$
  
<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/b016970/b01697042.png" /></td> </tr></table>
+
$$
 +
\epsilon \rightarrow 0 \textrm{ as }  n \rightarrow \infty .
 +
$$
  
A non-trivial upper estimate for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697043.png" /> and a non-trivial estimate for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697044.png" /> for "almost-all" functions are as yet (1977) not known. Complexity estimates of dead-end and of minimal disjunctive normal forms are of great interest in problems of minimization of Boolean functions. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697045.png" /> be the number of elementary conjunctions in a dead-end disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697046.png" /> of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697047.png" />; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697048.png" /> be the number of elementary conjunctions in a shortest disjunctive normal form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697049.png" />,
+
A non-trivial upper estimate for $  m (n) $
 +
and a non-trivial estimate for $  m _ {f} (n) $
 +
for "almost-all" functions are as yet (1977) not known. Complexity estimates of dead-end and of minimal disjunctive normal forms are of great interest in problems of minimization of Boolean functions. Let $  {\lambda _ {f}  ^ {T} } (n) $
 +
be the number of elementary conjunctions in a dead-end disjunctive normal form $  T $
 +
of the function $  f(x _ {1} \dots x _ {n} ) $;  
 +
let $  {l _ {f} } (n) $
 +
be the number of elementary conjunctions in a shortest disjunctive normal form of $  f(x _ {1} \dots x _ {n} ) $,
  
<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/b016970/b01697050.png" /></td> </tr></table>
+
$$
 +
\lambda (n)  = \
 +
\max _ {f, T } \
 +
\lambda _ {f}  ^ {T} (n),\ \
 +
l (n)  = \max _ { f } \
 +
l _ {f} (n).
 +
$$
  
 
The following estimates then hold:
 
The following estimates then hold:
  
<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/b016970/b01697051.png" /></td> </tr></table>
+
$$
 +
\lambda (n)  \sim  2  ^ {n} ,\ \
 +
l (n)  = 2 ^ {n - 1 } .
 +
$$
 +
 
 +
For "almost-all" Boolean functions  $  f(x _ {1} \dots x _ {n} ) $
 +
and for almost-all dead-end disjunctive normal forms  $  T $:
 +
 
 +
$$
 +
\lambda _ {f}  ^ {T} (n)  \sim \
 +
2 ^ {n - 1 } .
 +
$$
 +
 
 +
For "almost-all" Boolean functions  $  f(x _ {1} \dots x _ {n} ) $:
 +
 
 +
$$
  
For "almost-all" Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697052.png" /> and for almost-all dead-end disjunctive normal forms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697053.png" />:
+
\frac{2 ^ {n} }{ \mathop{\rm log} _ {2} n  \cdot  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n }
 +
  < \
 +
l _ {f} (n)  < \
  
<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/b016970/b01697054.png" /></td> </tr></table>
+
\frac{2  ^ {n} }{ \mathop{\rm log} _ {2}  n }
 +
.
 +
$$
  
For  "almost-all" Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697055.png" />:
+
These estimates show that the shortest (and also the minimal) disjunctive normal forms of "almost-all" Boolean functions account for only a small fraction of the number of dead-end disjunctive normal forms. There are also estimates of the relative complexity of dead-end and shortest disjunctive normal forms of Boolean functions. Let  $  {\lambda _ {f} } (n) $
 +
be the maximal number of elementary conjunctions in a dead-end disjunctive normal form of a function  $  f(x _ {1} \dots x _ {n} ) $.  
 +
For "almost-all" Boolean functions
  
<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/b016970/b01697056.png" /></td> </tr></table>
+
$$
 +
\mathop{\rm log} _ {2}  n  < \
  
These estimates show that the shortest (and also the minimal) disjunctive normal forms of "almost-all" Boolean functions account for only a small fraction of the number of dead-end disjunctive normal forms. There are also estimates of the relative complexity of dead-end and shortest disjunctive normal forms of Boolean functions. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697057.png" /> be the maximal number of elementary conjunctions in a dead-end disjunctive normal form of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697058.png" />. For "almost-all" Boolean functions
+
\frac{\lambda _ {f} (n) }{l _ {f} (n) }
 +
  < \
 +
  \mathop{\rm log} _ {2} n \cdot  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2} n.
 +
$$
  
<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/b016970/b01697059.png" /></td> </tr></table>
+
The maximum value of the ratio  $  {\lambda _ {f} } (n)/ {l _ {f} } (n) $
 +
can be estimated from below by  $  2 ^ {n(1 - \epsilon ) } $,
 +
$  \epsilon \rightarrow 0 $
 +
as  $  n \rightarrow \infty $.  
 +
Estimates of  $  y(f) $—
 +
the so-called scatter of  $  f(x _ {1} \dots x _ {n} ) $—
 +
have also been obtained. Here
  
The maximum value of the ratio <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697060.png" /> can be estimated from below by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697062.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697063.png" />. Estimates of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697064.png" /> — the so-called scatter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697065.png" /> — have also been obtained. Here
+
$$
 +
y (f)  = \
 +
\max _ {\begin{array}{c}
 +
{} \\
 +
T ^ { \prime } , T ^ { \prime\prime }
 +
\end{array}
 +
} \
  
<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/b016970/b01697066.png" /></td> </tr></table>
+
\frac{L (T ^ { \prime } ) }{L (T ^ { \prime\prime } ) }
 +
,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697067.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697068.png" /> are arbitrary dead-end disjunctive normal forms realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697069.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697070.png" /> is the number of characters in the dead-end disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697071.png" />. Examples of Boolean functions with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016970/b01697072.png" /> have been constructed; it has been established, however, that for "almost-all" Boolean functions
+
where $  T ^ { \prime } $
 +
and $  T ^ { \prime\prime } $
 +
are arbitrary dead-end disjunctive normal forms realizing $  f(x _ {1} \dots x _ {n} ) $,  
 +
and $  L(T) $
 +
is the number of characters in the dead-end disjunctive normal form $  T $.  
 +
Examples of Boolean functions with $  y(f) \geq  2 ^ {n(1 - o(1)) } $
 +
have been constructed; it has been established, however, that for "almost-all" Boolean functions
  
<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/b016970/b01697073.png" /></td> </tr></table>
+
$$
 +
y (f)  \leq  \
 +
\mathop{\rm log} _ {2}  n  \cdot  \mathop{\rm log} _ {2}  \mathop{\rm log} _ {2}  n.
 +
$$
  
 
The estimates above give a fairly complete idea of the difficulties that arise when Boolean functions are minimized according to the scheme: perfect disjunctive normal form — abridged disjunctive normal form — dead-end disjunctive normal form — minimal disjunctive normal form.
 
The estimates above give a fairly complete idea of the difficulties that arise when Boolean functions are minimized according to the scheme: perfect disjunctive normal form — abridged disjunctive normal form — dead-end disjunctive normal form — minimal disjunctive normal form.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> Yu.L. Vasil'ev,   "On comparing the complexity of typical and disjunctive normal forms" ''Problemy Kibernet.'' : 10 (1963) pp. 5–61 (In Russian)</TD></TR><TR><TD valign="top">[2]</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">[3]</TD> <TD valign="top"> A.D. Korshunov,   "The upper complexity bound of the shortest disjunctive normal forms of almost all Boolean functions" ''Cybernetics'' , '''5''' : 6 (1969) pp. 705–715 ''Kibernetika (Kiev)'' : 6 (1969) pp. 1–8</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> A.A. Sapozhenko,   "On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions" ''Math. Notes'' , '''4''' : 6 (1968) pp. 881 ''Mat. Zametki'' , '''4''' : 6 (1968) pp. 649–658</TD></TR></table>
+
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> Yu.L. Vasil'ev, "On comparing the complexity of typical and disjunctive normal forms" ''Problemy Kibernet.'' : 10 (1963) pp. 5–61 (In Russian)</TD></TR><TR><TD valign="top">[2]</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) {{MR|225634}} {{ZBL|}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> A.D. Korshunov, "The upper complexity bound of the shortest disjunctive normal forms of almost all Boolean functions" ''Cybernetics'' , '''5''' : 6 (1969) pp. 705–715 ''Kibernetika (Kiev)'' : 6 (1969) pp. 1–8</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> A.A. Sapozhenko, "On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions" ''Math. Notes'' , '''4''' : 6 (1968) pp. 881 ''Mat. Zametki'' , '''4''' : 6 (1968) pp. 649–658 {{MR|}} {{ZBL|0177.02001}} </TD></TR></table>

Latest revision as of 06:28, 30 May 2020


Formulas of a special kind realizing Boolean functions. One distinguishes between disjunctive normal forms (cf. Boolean functions, minimization of) and conjunctive normal forms. A product $ x _ {i _ {1} } ^ {\sigma _ {1} } \dots x _ {i _ {k} } ^ {\sigma _ {k} } $, where $ x ^ \sigma = x $ if $ \sigma = 1 $ and $ x ^ \sigma = Cx $ if $ \sigma = 0 $, is called an elementary conjunction of rank $ k $ if all its variables are different; "1" is considered to be an elementary conjunction of rank zero. A logical sum $ x _ {j _ {1} } ^ {\sigma _ {1} } \lor {} \dots \lor x _ {j _ {r} } ^ {\sigma _ {r} } $ is called an elementary disjunction of rank $ r $ if all its variables are different; "0" is considered to be an elementary disjunction of rank zero.

A formula $ \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {l} $, where $ \mathfrak A _ {1} \dots \mathfrak A _ {l} $ are distinct elementary conjunctions of ranks $ r _ {1} \dots r _ {l} $, respectively, is called a disjunctive normal form, and the number $ \sum _ {i=1 } ^ {l} r _ {i} $ is called its complexity; a formula $ \mathfrak B _ {1} \dots \mathfrak B _ {t} $, where $ \mathfrak B _ {1} \dots \mathfrak B _ {t} $ are different elementary disjunctions of ranks $ \rho _ {1} \dots \rho _ {t} $, respectively, is called a conjunctive normal form, and the number $ \sum _ {i=1 } ^ {t} \rho _ {i} $ is called its complexity. Every Boolean function that does not vanish identically can be defined by a disjunctive normal form which is, generally speaking, not unique. The same applies to conjunctive normal forms and functions that do not identically vanish.

From a table defining a Boolean function $ f(x _ {1} \dots x _ {n} ) $ one easily obtains the perfect disjunctive normal form $ \mathfrak A _ {1} \lor \dots \lor \mathfrak A _ {s} $, where $ \mathfrak A _ {i} = x _ {1} ^ {\sigma _ {i1} } \dots x _ {n} ^ {\sigma _ {in} } $, $ i = 1 \dots s $, and the sets $ \sigma _ {i1} \dots \sigma _ {in} $ are such that $ f( \sigma _ {i1} \dots \sigma _ {in} ) = 1 $. The perfect disjunctive normal form realizing a Boolean function $ f $ is unique. The perfect conjunctive normal form is defined similarly.

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

The main problem in the theory of normal forms of Boolean functions is that of minimizing Boolean functions, i.e. the construction of conjunctive or disjunctive normal forms of minimal complexity — minimal conjunctive or disjunctive normal forms for any given Boolean function (cf. Boolean functions, minimization of; Algorithm, local). Here, by virtue of the duality principle, it is sufficient to consider disjunctive normal forms only. In connection with the problem of minimizing Boolean functions one also considers abridged dead-end, shortest and minimal disjunctive normal forms. An important problem in the theory of disjunctive normal forms is the search for numerical characteristics of them, and characteristics connecting various types of disjunctive normal forms of a given function.

The abridged disjunctive normal form is uniquely constructed from a Boolean function by means of a fairly simple algorithm. Its most important property is the fact that every minimal disjunctive normal form of a function and at least one shortest form can be obtained from the abridged disjunctive normal form by the elimination of certain elementary conjunctions. Therefore many minimization algorithms employ the abridged disjunctive normal form as the initial specification of a Boolean function. It is of major interest in this context to define the complexity of abridged disjunctive normal forms for "almost-all" functions and to determine the absolute maximum of this complexity. If $ S _ {f} (n) $ is the number of elementary conjunctions in the abridged disjunctive normal form of a Boolean function $ f(x _ {1} \dots x _ {n} ) $ and if

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

then the following estimates hold:

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

and for "almost-all" Boolean functions

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

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

It is clear from these results and from the estimates of the complexity of the perfect disjunctive normal form that the complexity of the abridged disjunctive normal form is much higher than that of the perfect disjunctive normal form, both in the "typical" and in the "record-breaking" cases. Unlike the perfect and the abridged disjunctive normal form, a given Boolean function may have many dead-end and minimal disjunctive normal forms. Let $ t _ {f} (n) $ be the number of dead-end disjunctive normal forms and let $ m _ {f} (n) $ be the number of minimal disjunctive normal forms of a Boolean function $ f(x _ {1} \dots x _ {n} ) $,

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

Then the following estimates hold:

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

and for "almost-all" Boolean functions

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

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

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

A non-trivial upper estimate for $ m (n) $ and a non-trivial estimate for $ m _ {f} (n) $ for "almost-all" functions are as yet (1977) not known. Complexity estimates of dead-end and of minimal disjunctive normal forms are of great interest in problems of minimization of Boolean functions. Let $ {\lambda _ {f} ^ {T} } (n) $ be the number of elementary conjunctions in a dead-end disjunctive normal form $ T $ of the function $ f(x _ {1} \dots x _ {n} ) $; let $ {l _ {f} } (n) $ be the number of elementary conjunctions in a shortest disjunctive normal form of $ f(x _ {1} \dots x _ {n} ) $,

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

The following estimates then hold:

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

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

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

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

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

These estimates show that the shortest (and also the minimal) disjunctive normal forms of "almost-all" Boolean functions account for only a small fraction of the number of dead-end disjunctive normal forms. There are also estimates of the relative complexity of dead-end and shortest disjunctive normal forms of Boolean functions. Let $ {\lambda _ {f} } (n) $ be the maximal number of elementary conjunctions in a dead-end disjunctive normal form of a function $ f(x _ {1} \dots x _ {n} ) $. For "almost-all" Boolean functions

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

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

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

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

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

The estimates above give a fairly complete idea of the difficulties that arise when Boolean functions are minimized according to the scheme: perfect disjunctive normal form — abridged disjunctive normal form — dead-end disjunctive normal form — minimal disjunctive normal form.

References

[1] Yu.L. Vasil'ev, "On comparing the complexity of typical and disjunctive normal forms" Problemy Kibernet. : 10 (1963) pp. 5–61 (In Russian)
[2] V.V. Glagolev, "Certain estimates of the disjunctive normal forms of functions of the algebra of logic" Problemy Kibernet. , 19 (1967) pp. 75–94 (In Russian) MR225634
[3] A.D. Korshunov, "The upper complexity bound of the shortest disjunctive normal forms of almost all Boolean functions" Cybernetics , 5 : 6 (1969) pp. 705–715 Kibernetika (Kiev) : 6 (1969) pp. 1–8
[4] A.A. Sapozhenko, "On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions" Math. Notes , 4 : 6 (1968) pp. 881 Mat. Zametki , 4 : 6 (1968) pp. 649–658 Zbl 0177.02001
How to Cite This Entry:
Boolean functions, normal forms of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_functions,_normal_forms_of&oldid=16364
This article was adapted from an original article by Yu.I. Zhuravlev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article