Поступила в редакцию 28.05.2012 55 УДК 519.7 О ГЛУБИНЕ БУЛЕВЫХ ФУНКЦИЙ ПРИ РЕАЛИЗАЦИИ СХЕМАМИ НАД ПРОИЗВОЛЬНЫМ БЕСКОНЕЧНЫМ БАЗИСОМ О. М. <...> Касим-Заде1 Для всех бесконечных базисов найдены оценки схемной глубины всех булевых функций с точностью до небольшой аддитивной постоянной. <...> Ключевые слова: булева функция, схема из функциональных элементов, глубина схемы. <...> Bounds for the circuit depth of all Boolean functions tight up to a small additive constant are obtained for all infinite bases. <...> Key words: Boolean function, circuit of functional elements, circuit depth. <...> Базис называется конечным, если число существенных переменных входящих в него функций ограничено сверху, т.е. найдется такое число m, что любая функция этого базиса существенно зависит не более чем от m переменных; в противном случае базис называется бесконечным. <...> Рассмотрим реализацию булевых функций схемами из функциональных элементов над произвольным фиксированным базисом B.Под глубиной схемы понимается наибольшее число функциональных элементов, составляющих ориентированную цепь, ведущую от входов схемы к ее выходу. <...> Наименьшая глубина схемы над базисом B, достаточная для реализации булевой функции f,называется глубиной функции f над базисом B и обозначается через DB(f). <...> Базису B ставится в соответствие функция Шеннона глубины DB(n), определяемая при всяком натуральном n соотношением DB(n)=max f DB(f), где максимум берется по всем булевым функциям f от n переменных. <...> Подробные определения этих и других используемых в работе понятий можно найти в [1, 2]. <...> Известно [1], что для всякого конечного базиса B асимптотика функцииШеннона глубины при n→∞ имеет вид DB(n)= αn + o(n),где α =(log2m)−1, m — наибольшее число существенных переменных у функций базиса B. <...> В работе [3] показано, что для всякого бесконечного базиса B порядок роста функции Шеннона достаточно больших n, либо существуют постоянные γ 2 и δ, такие, что logγ n DB(n) logγ n+δ глубины DB(n) при n →∞ равен либо 1 <...>