УДК 519.71
О глубине функций k-значной логики в конечных базисах / А. В. Кочергин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. № 1. С. 56-59.
Рассматриваются схемы из функциональных элементов, реализующие функции k-значной логики над произвольным конечным полным базисом B. Исследуется асимптотическое поведение функции Шеннона DB(n) глубины схем над базисом B, определяемой как минимальная глубина схем, достаточная для реализации над базисом B любой функции k-значной логики от n переменных. Показано, что при любом натуральном k≥2 для произвольного конечного полного базиса B функций k-значной логики существует такая положительная константа αB, что при n→∞ выполняется соотношение DB(n)∼αBn.
Ключевые слова: k-значные логики, глубина схем, конечный базис.
Библиогр. 3.
