Том 14, серия 1, номер 1, 2007 г., Стр. 45-69

УДК 519.7
О. М. Касим-Заде
О глубине булевых функций над произвольным бесконечным базисом

Аннотация:
Рассматривается реализация булевых функций схемами из функциональных элементов над произвольным бесконечным полным базисом. Под глубиной схемы понимается наибольшее число функциональных элементов, составляющих ориентированную цепь, ведущую от входов схемы к её выходу. Вводится функция Шеннона глубины: при каждом натуральном $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.

Касим-Заде О. М. ¹
1. МГУ, мех.-мат. факультет,
Воробьевы горы, 119992 Москва, Россия
е-mail: kasimz@mech.math.msu.su

Статья поступила 5 февраля 2007 г.