Abstract:
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.
Fulltext:
PDF file (220 kB)