Ясно, что для n =1 в (4) имеет место равенство. <...> . Теперь воспользуемся доказанной леммой и продолжим неравенство (6): k −2 j lnj n j! <...> Об оценке некоторых арифметических сумм с числом делителей // Матем. заметки. <...> Дагаев1 В работе получены верхние и нижние оценки сложности функций трехзначной логики, которые принимают значения из множества {0, 1} и ограничения которых на множестве наборов из нулей и единицявляются линейными функциями. <...> Рассматривается задача о реализации функций трехзначной логики формулами над конечными системами. <...> О.Б. Лупанов [1] для любой полной системы булевых функций получил асимптотически точную оценку функции Шеннона. <...> В работе [2] показано, что для произвольной конечной системы Ψ булевых функций всякая функция из [Ψ] может быть реализована формулой со сложностью, имеющей не более чем экспоненциальный порядок роста от числа переменных. <...> Пример последовательности функций четырехзначной логики, сложность которых в классе формул над некоторой конечной неполной системой имеет порядок роста “двойной экспоненты” от числа переменных, приведен в [3]. <...> В [4, 5] для некоторых замкнутых классов трехзначной логики получены верхние оценки соответствующих функций Шеннона. <...> В настоящей работе исследуется сложность функций трехзначной логики, которые принимают значения 1Дагаев Дмитрий Александрович — асп. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: ddagaev@gmail.com. <...> №2 из множества {0, 1} и ограничения которых на множестве наборов из нулей и единиц являются линейными булевыми функциями. <...> Множество всех функций k-значной логики обозначим через Pk, а множество всех функций из P3, принимающих значения только из множества E2, — через P3,2. <...> Обозначим через [F] замыкание множества F относительно операций суперпозиции и введения несущественной Пусть Ek = {0, 1,. ,k − 1}, k 2. <...> Обозначим через En k множество всех наборов α =(α1,. ,αn), переменной (см. <...> Определим следующие множества булевых функций: L — множество всех линейных <...>