Dead-end disjunctive normal form

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.

Comments

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.