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

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, номер 2, страницы 61–64 (Mi vmumm398)

Эта публикация цитируется в 3 статьях

Краткие сообщения

О равномерности некоторых систем функций многозначной логики

П. Б. Тарасов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Рассматривается конечная система $A$ функций многозначной логики, принимающих значения $0$ и $1$, причем проекция системы $A$ порождает класс всех монотонных булевых функций. Показано, что найдутся константы $c$ и $d$, такие, что для любой функции $f$ из $[A]$ глубина $D(f)$ и сложность $L(f)$ функции $f$ в классе формул над $A$ связаны соотношением $D(f)\leq c\log_2 L(f)+d$.

Ключевые слова: равномерность конечных систем, многозначная логика, монотонные функции, полиномиальная эквивалентность.

УДК: 511

Поступила в редакцию: 12.09.2012


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

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


© МИАН, 2024