Аннотация:
Пусть $A$ — конечная система булевых функций. Через $[A]$ обозначим множество функций, реализуемых нетривиальными формулами над $A$. Если $f \in [A]$, то через $L(f)$ и $D(f)$ будем обозначить минимальную сложность и глубину реализации функции $f$ формулами над системой A соответственно. Конечная система $A$ функций из многозначной логики называется равномерной, если существуют константы $c$ и $d$, такие, что для любой функции $f$ из $[A]$ выполнено $D(f) \leq c \log_2 L(f) + d$ (нетрудно заметить, что данная верхняя оценка для $D(f)$ наилучшая по порядку). Известно, что все конечные системы булевых функций равномерны.
Для многозначной логики известны тривиальные примеры неравномерных систем, а также некоторые достаточные условия для равномерности систем, порождающих предполные классы. Я расскажу о некоторых необходимых и достаточных условиях равномерности в $k$-значной логике, а также о некоторых других соотношениях между глубиной и сложностью реализации функций формулами.
|
