Эта публикация цитируется в
1 статье
Математика
О некоторых достаточных условиях равномерности систем функций многозначной логики
П. Б. Тарасов Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Для произвольной конечной системы
$A$ функций
$k$-значной логики, принимающих значения из множества
$E_s=\{0,\ldots,s-1\}$,
$k\geq s\geq2$, такой, что замкнутый класс, порожденный ограничением функций из
$A$ на множество
$E_s$, содержит мажоритарную функцию, доказано существование констант
$c$ и
$d$, таких, что для любой функции
$f \in [A]$ глубина
$D_A(f)$ и сложность
$L_A(f)$ функции
$f$ в классе формул над
$A$ связаны соотношением
$D_A(f)\leq c\log_2 L_A(f)+d$.
Ключевые слова:
равномерность конечных систем, многозначная логика, полиномиальная эквивалентность, мажоритарная функция.
УДК:
511 Поступила в редакцию: 22.02.2013