Поступила в редакцию 25.05.2011 УДК 519.95 ОБ ОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ А. А. <...> Андреев1 Рассматривается задача о реализации функций многозначной логики формулами. <...> Приводится метод получения сверхэкспоненциальных оценок сложности для последовательностей функций. <...> 1Андреев Александр Андреевич — студ. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: sanchez 14@mail.ru. вестн. моск. ун-та. сер. <...> №6 Ключевые слова: функции многозначной логики, формулы, сложность формул, реализация функций формулами. <...> В работе [4] приведен пример последовательности функций fn(x1,. ,xn) 4-значной логики, сложность которых в классе формул над некоторой неполной системой превосходит 2C[n/2] n , т.е. имеет рост “двойной экспоненты” от числа переменных (см. также [5, 6]). <...> В настоящей работе (на основе статьи [6]) предлагается метод, позволяющий для любых натуральных m и r для некоторого k(r) строить последовательность fn(x1,. ,xn) функций из Pk(r), сложность которых в классе формул над некоторой конечной системой превосходит mrn ки, сложность которых превосходит 23n . <...> Этот метод демонстрируется на примере последовательности функций 10-значной логи. <...> Обозначим через L(Φ) число символов переменных и констант, входящих в Φ (сложность формулы), а через D(Φ) — глубину формулы Φ. <...> Сложностью функции Fn+1 — множество всех наборов из En+1, имеющих не менее n вхождений символов 3, 4, 5. <...> Будем обозначать через [A] замкнутый класс, порождаемый функциями из A. <...> Пусть f(x0,x1,. ,xn) — функция из [A]; Φ(x0,x1,. ,xn) — формула над A, реализующая функцию f и такая, что все входящие в нее символы переменных принадлежат множеству X = {x0,x1,. ,xn}; α =(α0,α1,. ,αn) — произвольный набор, компоненты которого принадлежат множеству E = E10 = функций имеет не более чем экспоненциальный порядок роста от числа переменных. <...> Обозначим через P10 множество всех функций 10-значной логики. <...> Поставим в соответствие формуле Φ дерево T =(V,E) с корнем v∗ (где V — множество вершин, E — множество ребер, v∗ ∈ V ), в котором висячим вершинам <...>