О ГЛУБИНЕ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ В КОНЕЧНЫХ БАЗИСАХ

Рассматриваются схемы из функциональных элементов, реализующие функции k-значной логики над произвольным конечным полным базисом B. Исследуется асимптотическое поведение функции Шеннона DB(n) глубины схем над базисом B, определяемой как минимальная глубина схем, достаточная для реализации над базисом B любой функции k-значной логики от n переменных. Показано, что при любом натуральном k  2 для произвольного конечного полного базиса B функций k-значной логики существует такая положительная константа αB, что при n →∞выполняется соотношение DB(n) ∼ αBn.

• Кочергин А.В.

• Прикладные науки. Медицина. Технология

• Естественные науки