О сложности функций многозначной логики в одном бесконечном базисе

Исследуется сложность реализации функций $k$-логики $(k\ge3)$ схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т.е. функции $x+1\pmod k$, и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функции $f$ установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки сложности вида $3\log_3(d(f)+1)+O(1)$, где $d(f)$ – максимальное (максимум берётся по всем возрастающим цепям наборов значений переменных) число изменений значений функции $f$ с большего значения на меньшее. Найдено точное значение соответствующей функции Шеннона, характеризующей сложность реализации самой сложно реализуемой функции от заданного числа переменных. Ил. 4, библиогр. 24.