Нижние мощностные оценки для сложности реализации функций из $P_k$ схемами из функциональных элементов в произвольном базисе

В данной работе устанавливается теорема, позволяющая для широкого класса управляющих систем получать нижние мощностные оценки. Для класса схем из многозначных функциональных элементов найдена оценка числа схем заданной сложности. На основе этих двух фактов получена нижняя мощностная оценка для функции Шеннона при реализации функций из $P_k$ схемами из многозначных элементов. Причем, существуют функциональные базисы, в которых данные оценки существенно лучше, чем ранее известные.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 93–011-1525.