О глубине функций k-значной логики в бесконечных базисах

k-значные логики глубина схем бесконечный базис

Об устойчивости течения Куэтта идеально жесткопластического тела, Задача навигации внутритрубного диагностического снаряда, ...

Рассматривается реализация функций k-значной логики схемами из функциональных элементов над произвольным бесконечным полным базисом B. <...> Изучается поведение функции Шеннона DB(n) глубины схем над базисом B (здесь при любом натуральном n значение DB(n) равно наименьшей глубине схем, достаточной для реализации над базисом B любой функции k-значной логики от n переменных). <...> Устанавливается, что при любом фиксированном k >= 2 для любого бесконечного полного базиса B функций k-значной логики либо существует константа α >= 1, такая, что DB(n)=α при всех достаточно больших n, либо существуют константы β (β>0), γ, δ, такие, что β log2 n <= DB(n) <=γ log2 n + δ при всеx n. <...> Рассматривается реализация функций k-значной логики схемами из функциональных элементов над произвольным бесконечным полным базисом B. <...> Изучается поведение функции Шеннона DB(n) глубины схем над базисом B (здесь при любом натуральном n значение DB(n) равно наименьшей глубине схем, достаточной для реализации над базисом B любой функции k-значной логики от n переменных). <...> Устанавливается, что при любом фиксированном k >= 2 для любого бесконечного полного базиса B функций k-значной логики либо существует константа α >= 1, такая, что DB(n)=α при всех достаточно больших n, либо существуют константы β (β>0), γ, δ, такие, что β log2 n <= DB(n) <=γ log2 n + δ при всеx n. <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт