Вестник Московского Университета. Математика, Механика - Содержание


УДК 519.95

О равномерности систем монотонных функций / Сафин Р.Ф. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2003. N.2 C. 15-20.

Для предполных классов монотонных функций $k$-значной логики при $k \le 7$ показано, что для всякой конечной системы функций $A$, порождающей один из этих классов, найдутся такие константы $c$ и $d$, что для любой функции $f$ из $[A]$ глубина $D(f)$ и сложность $L(f)$ функции $f$ в классе формул над $A$ связаны соотношением $D(f) \le c \log_2 L(f) + d$.

Библиогр. 5.

К оглавлению номера  Go!