Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/vestnik/DATA/2000/6/node16
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 02:27:18 2016
Кодировка: Windows-1251
Вестник МГУ. Математика. Механика
Вестник Московского Университета. Математика, Механика - Содержание


УДК 519.95

О глубине и сложности формул в некоторых классах $k$-значной логики / Сафин Р.Ф. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2000. N.6 C. 65-68.

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

Библиогр. 7.

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