УДК 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.

К оглавлению номера  Go!