The depth of \alpha-completions of systems of Boolean functions / D. V. Truschin. //Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2009. № 2. P. 72-75
[Moscow Univ. Math. Bulletin.
Vol. 64,
N 2, 2009. 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.
