О глубине булевых функций над произвольным бесконечным базисом

Рассматривается реализация булевых функций схемами из функциональных элементов над произвольным бесконечным полным базисом. Под глубиной схемы понимается наибольшее число функциональных элементов, составляющих ориентированную цепь, ведущую от входов схемы к её выходу. Вводится функция Шеннона глубины: при каждом натуральном $n$ её значение $D_B(n)$ равно наименьшей глубине схем, достаточной для реализации над базисом $B$ любой булевой функции от $n$ переменных. Показано, что для любого бесконечного базиса $B$ либо существует константа $\beta\geqslant 1$ такая, что $D_B(n)=\beta$ при всех достаточно больших $n$, либо существуют целочисленная константа $\gamma\geqslant 2$ и константа $\delta$ такие, что $\log_\gamma n\geqslant D_b(n)\geqslant\log_\gamma n+\delta$ при всех $n$.
Библ. 16.