Dead-end disjunctive normal form

From Encyclopedia of Mathematics
Jump to: navigation, search

A disjunctive form, representing a given Boolean function, that cannot be reduced, neither by crossing-out letters in some conjunction, nor by disregarding some conjunction. A minimal disjunctive normal form is obtained from a reduced disjunctive normal form by deleting some conjunctions; this is not a single-valued process and it ramifies into "dead-ends", i.e. into disjunctive normal forms in which no term can be deleted. Such forms are called dead-end disjunctive normal forms. A dead-end disjunctive normal form need not be minimal.

The value of this concept consists, at one side, in the fact that the dead-end disjunctive normal forms model, in the optimization problem, the local minima among which the global minima (the minimal disjunctive normal forms) have to be found. On the other hand, when minimizing Boolean functions in practice one often restricts to the construction of a dead-end disjunctive normal form. An estimation of the complexity of dead-end disjunctive normal forms is exemplified by: 1) the fast growth of the number of dead-end disjunctive normal forms with the growth of the number $n$ of variables of Boolean functions (the order is $2^{2cn}$); 2) the small part (tending to zero as $n\to\infty$) of minimal disjunctive normal forms among the dead-end ones; and 3) the unrestricted growth (as $n\to\infty$) of the complexity of transforming a given dead-end disjunctive normal form to a minimal disjunctive normal form. These statements hold both for the "worst" functions and in "typical" cases, i.e. for a totality of functions whose ratio to all functions tends to one as $n\to\infty$.

See also Boolean functions, normal forms of.


The phrase "dead-end disjunctive normal form" is not used in Western literature. The notion covered by it is often unnamed, or goes by a phrase like irreducible disjunct(ive) normal form.

How to Cite This Entry:
Dead-end disjunctive normal form. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by V.V. Glagolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article