Последнее утверждение объясняет, почему присоединение к дифференциальной алгебре D2[σ−1 иррационального элемента w1 имеют место равенста gi,j(t)/w3(t)= ci,j · w1 3 3 Следствие. <...> Поступила в редакцию 11.01.2012 УДК 519.95 О СЛОЖНОСТИ РЕАЛИЗАЦИИ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ ФОРМУЛАМИ СПЕЦИАЛЬНОГО ВИДА Д. В. <...> Трущин1 Рассматривается задача о реализации функций многозначной логики формулами специального вида. <...> Для каждого простого k, k =2, установлены верхние оценки сложности вида kn для произвольной функции k-значной логики. <...> Пусть n 1, A — конечная система функций из Pk. <...> Формулу над A,не содержащую символов переменных, за исключением x1,. ,xn, обозначим через Φ(x1,. ,xn). <...> Значение формулы Φ на го двух, получены верхние оценки сложности произвольной функции k-значной логики над системой, состоящей из всех бинарных операций с правым сокращением. <...> Обозначим через Pk множество всех функций k-значной логики. <...> Сложность и глубину над системой A произвольной функции f из [A] обозначим через LA(f) и DA(f) соответственно. <...> Известно [3], что для любой полной конечной системы A булевых функций и любой булевой функции α =(α1,. ,αn) ∈ En k обозначим через Φ(˜ f(x1,. ,xn) выполнено соотношение LA(f) 2n конечной системы A булевых функций и любой функции f(x1,. ,xn) ∈ [A] справедливы неравенства LA(f) rn log2 n. <...> В работах [4, 5] показано, что для произвольной Следуя [6], определим индуктивно понятие α-формулы над конечной системой A функций алгебры 1 и DA(f) r2n,где r1 и r2 — некоторые константы, зависящие от A. логики. <...> Символ нульместной функции из A является α-формулой. <...> Выражение вида u(Φ),где Φ — α-формула над A,а u — символ одноместной функции из A, является α-формулой. <...> Наконец, выражение вида g(Φ,xi2 над A, m 2, g — символ m-местной функции из A,а xi2 Отметим, что каждая α-формула является формулой над A. <...> В работе [9] показано, что для любой конечной системы A булевых функций существует многочлен <...>