On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions

The maximal numberl(f) of conjunctions in a dead-end disjunctive normal form (d.n.f.) of a Boolean functionf and the number (f) of dead-end d.n.f. are important parameters characterizing the complexity of algorithms for finding minimal d.n.f. It is shown that for almost all Boolean functionsl(f)2^n–1, log₂ (f)2^n–1log₂nlog₂log₂n (n).Translated from Matematicheskie Zametki, Vol. 4, No. 6, pp. 649–658, December, 1968.