22 УДК 519.71 О ГЛУБИНЕ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ В БЕСКОНЕЧНЫХ БАЗИСАХ А. В. <...> Кочергин1 Рассматривается реализация функций k-значной логики схемами из функциональных элементов над произвольным бесконечным полным базисом B. <...> Изучается поведение функции Шеннона DB(n) глубины схем над базисом B (здесь при любом натуральном n значение DB(n) равно наименьшей глубине схем, достаточной для реализации над базисом B любой функции k-значной логики от n переменных). <...> Устанавливается, что при любом фиксированном k 2 для любого бесконечного полного базиса B функций k-значной логики либо существует константа α 1, такая, чтоDB(n)= α при всех достаточно больших n, либо существуют константы β (β> 0), γ, δ, такие, что β log2 n DB(n) γ log2 n + δ при всеx n. <...> The implementation of functions of the k-valued logic by circuits is considered over an arbitrary infinite complete basis B. <...> The Shannon function DB(n) of the circuit depth over B is examined (for any positive integer n the value DB(n) is the minimal depth sufficient to implement every function of the k-valued logic of n variables by a circuit over B). <...> It is shown that for each fixed k 2 and for any infinite complete basis B either there exists a constant α 1 such that DB(n)= α for all sufficiently large n, or there exist constants β (β> 0), γ, δ such that β log2 n DB(n) γ log2 n+δ for all n. <...> Рассматривается реализация функций k-значной логики схемами из функциональных элементов над произвольным бесконечным базисом. <...> Под базисом будем понимать любое множество функций k-значной логики (k 2), такое, что суперпозициями функций этого множества можно реализовать любую функцию k-значной логики. <...> Базис называется бесконечным, если для любого натурального числаmсуществует функция из этого базиса, существенно зависящая более чем от m переменных. <...> Глубиной схемы <...>