Поступила в редакцию 29.10.2010 УДК 519.714 О СЛОЖНОСТИ ФУНКЦИЙ ИЗ НЕКОТОРЫХ КЛАССОВ ТРЕХЗНАЧНОЙ ЛОГИКИ Д. А. <...> Дагаев1 Рассматривается задача о сложности реализации функций трехзначной логики, принимающих значения из множества {0, 1}, формулами в неполных базисах. <...> Получены верхние и нижние асимптотические оценки для соответствующих функцийШеннона. <...> The problem of the complexity of realization of functions of the three-valued logic taking values from the set {0, 1} by formulas over incomplete generating systems is considered. <...> Key words: functions of three-valued logic, formulas, complexity of formulas. <...> В данной работе рассматривается задача о сложности реализации функций трехзначной логики, принимающих значения из множества {0, 1}, формулами над конечными системами. <...> Все определения можно найти в [2–6]. чать через Pk, а множество всех функций трехзначной логики, принимающих значения только из мно α =(α1,. ,αn),таких,что α1,. ,αn ∈ Ek. <...> Множество всех функций k-значной логики будем обознаПусть k 2, n 1. <...> Обозначим через En k множество всех наборов f(x1,. ,xn) ∈ [G], Φ — формула над G, реализующая функцию f,а F ⊆ [G]. <...> Обозначим через L(Φ) число символов переменных и констант, входящих в формулу Φ (сложность формулы Φ), через LG(f) — сложность функции f, а через LG(F(n)) — функциюШеннона для множества F.Пусть x — переменная, входящая в формулу Φ. <...> Обозначим через [G] замкнутый класс, порожденный системой G, а через G(n) — множество всех функций из G, зависящих от переменных x1,. ,xn, n 1. <...> Пусть шение О. Б. Лупанов [4] показал, что для любой полной системы булевых функций G выполняется соотно2n LG(P2(n)) ∼ log2 n (см. также [2, 3]). <...> Известно [7], что для любой конечной системы G ⊆ P2 найдется константа c = c(G), такая, что для любой функции f(x1,. ,xn) из [G] имеет место неравенство LG(f) cn. <...> Пример последовательности функций 4-значной логики, сложность реализации которых в классе формул над некоторой конечной неполной системой имеет сверхэкспоненциальный <...>