RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, номер 5, страницы 41–46 (Mi vmumm437)

Эта публикация цитируется в 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


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2013, 68:5, 253–257

Реферативные базы данных:


© МИАН, 2024