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

В работе рассматриваются полиномиальные нормальные формы для функций $k$-значных логик (при простых $k$). Полиномиальная нормальная форма по модулю $k$ (п.н.ф.) – это сумма по модулю $k$ произведений переменных или переменных с одним или несколькими отрицаниями Поста, взятых с некоторыми коэффициентами. Длиной п.н.ф. называется число ее различных слагаемых с ненулевыми коэффициентами. Если $k$ – простое число, то каждая функция $k$-значной логики может быть представлена различными п.н.ф. Длиной функции $k$-значной логики в классе п.н.ф. называется минимальная длина среди всех п.н.ф., представляющих эту функцию. Функция Шеннона $L_k^{p.n.f.}(n)$ длины функций $k$-значной логики в классе п.н.ф. – это максимальная длина функции в классе п.н.ф. среди всех функций $k$-значной логики, зависящих от $n$ переменных. В работе устанавливается порядок функции Шеннона $L_k^{p.n.f}(n)$ (при простых $k$): $L_k^{p.n.f.}(n)=\Theta\left(\frac{k^n}n\right)$.
Работа поддержана РФФИ, грант 13-01-00958-а и частично грант 13-01-00684-а.