RUS  ENG
Полная версия
ЖУРНАЛЫ // Фундаментальная и прикладная математика // Архив

Фундамент. и прикл. матем., 2015, том 20, выпуск 6, страницы 155–158 (Mi fpm1691)

Эта публикация цитируется в 1 статье

О глубине функций $k$-значной логики над произвольными базисами

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

Институт прикладной математики им. М. В. Келдыша Российской академии наук

Аннотация: Изучается поведение функции Шеннона глубины функций $k$-значной логики при реализации схемами из функциональных элементов (или формулами) над произвольным полным базисом. При всех $k$, $k \ge 3$, для произвольного базиса функций $k$-значной логики установлено существование асимптотики функции Шеннона глубины: для конечных базисов асимптотика является линейной, для бесконечных — константной или логарифмической. Тем самым получена полная картина асимптотического поведения функции Шеннона глубины при всех $k$, $k \ge 2$.

Ключевые слова: $k$-значная логика, глубина схем, глубина формул, функция Шеннона глубины, конечный базис, бесконечный базис.

УДК: 519.7


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2018, 233:1, 100–102


© МИАН, 2024