Некоторые особенности задачи синтеза булевых формул в полных базисах с прямыми и итеративными переменными

В работе рассмотрены вопросы сложности формул в различных базисах, состоящих из функций алгебры логики с прямыми и итеративными переменными. Показано, что “стандартное” поведение функции Шеннона для сложности формул $(2^n/\log n)$ не всегда имеет место, приведены примеры нетривиальных семейств базисов с порядком роста этой функции, равным $2^n$. Такие примеры существуют среди каждого из семейств в классификации полных базисов по их итеративным замыканиям, кроме двух, в которых функция Шеннона ведет себя стандартно. Для оператора итеративного замыкания $\delta$, введенного в работе [Ложкин С. А. О полноте и замкнутых классах функций алгебры логики с прямыми и итеративными переменными // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. – 1999. – № 3. – С. 35–41], получено новое представление. Отдельно рассмотрен вопрос о сложности линейной функции в некоторых классах базисов и приведены примеры кардинального изменения этой сложности в различных базисах одного семейства.