|
Вестник Московского университета. Серия 1: Математика. Механика, 2013, номер 5, страницы 41–46
(Mi vmumm437)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 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$.
Ключевые слова:
равномерность конечных систем, многозначная логика, полиномиальная эквивалентность, мажоритарная функция.
Поступила в редакцию: 22.02.2013
Образец цитирования:
П. Б. Тарасов, “О некоторых достаточных условиях равномерности систем функций многозначной логики”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, № 5, 41–46; Moscow University Mathematics Bulletin, 68:5 (2013), 253–257
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm437 https://www.mathnet.ru/rus/vmumm/y2013/i5/p41
|
Статистика просмотров: |
Страница аннотации: | 64 | PDF полного текста: | 29 | Список литературы: | 16 |
|