Depth of \alpha-completions of systems of Boolean functions / D. V. Truschin. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2009. № 2. P.  [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 87-90].

A problem of implementation of Boolean functions by \alpha-formulas is considered. These formulas are such that each subformula contains not more that one nontrivial principal subformula. The depth is considered as a complexity measure of a formula. Upper and lower polynomial estimates of Shannon functions for \alpha-supplements of finite systems of Boolean functions are obtained.

Key words: Boolean function, formula, complexity, depth.

№ 2/2009