|
УДК 519.71 О глубине функций k-значной логики в бесконечных базисах / А. В. Кочергин // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2011. № 1. С. 22-26. Рассматривается реализация функций k-значной логики схемами из функциональных элементов над произвольным бесконечным полным базисом B. Изучается поведение функции Шеннона DB(n) глубины схем над базисом B (здесь при любом натуральном n значение DB(n) равно наименьшей глубине схем, достаточной для реализации над базисом B любой функции k-значной логики от n переменных). Устанавливается, что при любом фиксированном k ≥ 2 для любого бесконечного полного базиса B функций k-значной логики либо существует константа α ≥ 1, такая, что DB(n) = α при всех достаточно больших n, либо существуют константы β (β > 0), γ, δ, такие, что β log2n ≤ DB(n) ≤ γ log2n + δ при всеx n. Ключевые слова: k-значные логики, глубина схем, бесконечный базис. Библиогр. 7.
 
|