Multilevel [Boolean] formulas

DNF formulas always have depth 2. By allowing larger depths one can potentially find smaller formulas for functions. A major result from the 1980s is that it requires a formula with depth at leastLog[n]/(c + Log[Log[n]]) to make it possible to represent anXor ofn variables using a polynomial number ofAnd,Or andNot operations. If one chooses ann-variable Boolean function at random out of the2²ⁿ possibilities, it is typical that regardless of depth a formula involving at least2ⁿ/n operations will be needed to represent it. A formula of polynomial size and logarithmic depth exists only when a function is the computational complexity class NC discussed on page1149.

Little is known about systematic minimization of Boolean formulas with depths above 2. Nevertheless, some programs for circuit design such as SIS do include a few heuristics. And this for example allows SIS to generate higher depth formulas somewhat smaller than the minimal DNF for the first three steps of rule 30 evolution.