УДК 519.71

О глубине функций k-значной логики в бесконечных базисах / А. В. Кочергин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2011. № 1. С. 22-26.

Рассматривается реализация функций k-значной логики схемами из функциональных элементов над произвольным бесконечным полным базисом B. Изучается поведение функции Шеннона D_B(n) глубины схем над базисом B (здесь при любом натуральном n значение D_B(n) равно наименьшей глубине схем, достаточной для реализации над базисом B любой функции k-значной логики от n переменных). Устанавливается, что при любом фиксированном k ≥ 2 для любого бесконечного полного базиса B функций k-значной логики либо существует константа α ≥ 1, такая, что D_B(n) = α при всех достаточно больших n, либо существуют константы β (β > 0), γ, δ, такие, что β log₂n ≤ D_B(n) ≤ γ log₂n + δ при всеx n.

Ключевые слова: k-значные логики, глубина схем, бесконечный базис.

Библиогр. 7.