Автор приносит глубокую благодарность А.Э. Гутерману и А.В. Михалеву за постановку задачи и постоянное внимание к работе. <...> Вычисление длин матричных подалгебр специального вида // Фунд. и прикл. матем. <...> Поступила в редакцию 21.05.2012 УДК 519.71 О ГЛУБИНЕ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ В КОНЕЧНЫХ БАЗИСАХ А. В. <...> Кочергин1 Рассматриваются схемы из функциональных элементов, реализующие функции k-значной логики над произвольным конечным полным базисом B. <...> Исследуется асимптотическое поведение функции Шеннона DB(n) глубины схем над базисом B, определяемой как минимальная глубина схем, достаточная для реализации над базисом B любой функции k-значной логики от n переменных. <...> Показано, что при любом натуральном k 2 для 1Кочергин Алексей Вадимович — асп. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: alexeykoch@mail.ru. вестн. моск. ун-та. сер. <...> №1 произвольного конечного полного базиса B функций k-значной логики существует такая положительная константа αB, что при n→∞выполняется соотношение DB(n) ∼ αBn. <...> Realization of functions of k-valued logic by circuits is considered over an arbitrary finite complete basis B. <...> Asymptotic behaviour of the Shannon function DB(n) of the circuit depth over B is examined. <...> The value DB(n) is the minimal depth sufficient to realize every function of k-valued logic on n variables by a circuit over B. <...> It is shown that for each natural k 2 and for any finite complete basis B there exists a positive constant αB such that DB(n) ∼ αBn for n→∞. <...> В работе рассматривается глубина функций k-значной логики (k 2) при реализации схемами из функциональных элементов над произвольным базисом. <...> Под базисом понимается произвольное конечное множество функций k-значной логики, такое, что суперпозициями функций этого множества можно реализовать любую функцию k-значной логики. <...> Глубиной схемы называется максимальное число элементов в ориентированных цепях, ведущих от какого-либо из входов схемы к ее выходу <...>