Автор приносит глубокую благодарность А.Э. Гутерману и А.В. Михалеву за постановку задачи и постоянное внимание к работе. <...> Вычисление длин матричных подалгебр специального вида // Фунд. и прикл. матем. <...> Поступила в редакцию 21.05.2012 УДК 519.71 О ГЛУБИНЕ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ В КОНЕЧНЫХ БАЗИСАХ А. В. <...> Кочергин1 Рассматриваются схемы из функциональных элементов, реализующие функции k-значной логики над произвольным конечным полным базисом B. <...> Исследуется асимптотическое поведение функции Шеннона DB(n) глубины схем над базисом B, определяемой как минимальная глубина схем, достаточная для реализации над базисом B любой функции k-значной логики от n переменных. <...> №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. <...> 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-значной логики f над базисом B понимается минимальная глубина схем, реализующих функцию f над базисом B. <...> Для каждого базиса B введем функцию Шеннона DB(n), характеризующую максимальную глубину функций от n переменных и определяемую равенством DB(n)=maxDB(f), где максимум берется по всем функциям k-значной логики f, зависящим от n переменных. <...> В [1] установлено, что в случае двузначной логики (k =2) для любого <...>