The realization of Boolean functions from closed classes of functions by formulas over finite bases of these classes is considered. Asymptotically exact by order bounds for Shannon function (characterizing the depth of formulas) are found for each class of functions.

Boolean functions, formulas, formula complexity

Mathematical problems and theory of numerical methods