ИСТИНА

Изучается модель обобщенной глубины схем из функциональных элементов в произвольном конечном полном базисе, в которой глубина базисного элемента - положительная целочисленная величина - по любому из его входов складывается из двух компонент: глубины межэлементного соединения входа с выходом предыдущего элемента и, собственно, внутренней глубины рассматриваемого элемента. Глубины элемента по разным входам, вообще говоря, считаются независимыми величинами. Установлено точное по порядку значение так называемой ранговой функции базиса действительного арумента t, которая равна наибольшему рангу формул, ограниченной величиной t глубины. Из этих результатов следуют асимптотические оценки функции Шеннона для обобщенной глубины функций алгебры логики от заданных n переменных и обобщенной глубины мультиплексорной функции порядка n, имеющие точность O(log log n).