Аннотация:Поляризованная полиномиальная форма (ППФ) (по модулю k) – это сумма по модулю k произведений переменных x1, . . . , xn или их отрицаний Поста, причем число отрицаний каждой переменной определяется вектором поляризации этой ППФ. Длиной ППФ называется число ее попарно различных слагаемых. Длиной функции k-значной логики f(x1, . . . , xn) в классе ППФ называется минимальная длина среди всех ППФ, реализующих эту функцию. В работе построена такая последовательность симметрических функций трехзначной логики fn(x1, . . . , xn), что длина каждой из функций fn в классе ППФ не меньше, чем ⌊3n+1/4⌋, где ⌊a⌋ обозначает наибольшее целое число, не превосходящее число a. Сложностью системы ППФ, имеющих один и тот же вектор поляризации, называется число попарно различных слагаемых, встречающихся во
всех этих ППФ. Сложностью L(F) системы F = {f1, . . . , fm} функций
k-значной логики, зависящих от переменных x1, . . . , xn, в классе ППФ называ-
ется минимальная сложность среди всех таких систем ППФ {p1, . . . , pm}, что
все ППФ p1, . . . , pm имеют один и тот же вектор поляризации, и ППФ pj ре-
ализует функцию fj , j = 1, . . . ,m. Пусть L_k(m, n) = max L(F), где индекс F пробегает по всем системам, содержащим m функций k-значной логики, зависящих от переменных x1, . . . , xn. Понятно, что при простых k верна оценка L_k(m, n) ⩽ k^n. В работе доказано, что L_2(m, n) = 2^n и L_3(m, n) = 3^n для всех m ⩾ 2, n = 1, 2, . . . . Более того, доказано, что оценки остаются такими же, если рассматривать только системы симметрических функций.