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

О глубине и полиномиальной эквивалентно сти формул для замкнутых классов двузначной логики

А. Б. Угольников


Аннотация: Показано, что для любой конечной системы булевых функций $\mathfrak{A}$ существуют константы $c$ и $d$ (зависящие только от $\mathfrak{A}$) такие, что для всякой функции $f$ из $[\mathfrak{A}]$ выполняется неравенство, связывающее глубину и сложность формул:
$$ l_{\mathfrak{A}}(f)\leqslant c\log_2L_{\mathfrak{A}}(f)+d. $$
Показано также, что для любых двух конечных систем булевых функций $\mathfrak{A}$ и $\mathfrak{B}$ таких, что $[\mathfrak{A}]\subseteq[\mathfrak{B}]$, существуют такие константы $c_1$ и $d_1$ что для всякой функции $f$ из $[\mathfrak{A}]$ имеет место соотношение $L_{\mathfrak{B}}(f)\leqslant d_1(L_{\mathfrak{A}}(f))^{c_1}$.
Кроме того, показано, что аналогичные теоремы для функций многозначной логики места не имеют. Библиогр. 15 назв.

УДК: 519.95

Поступило: 11.04.1986

 Англоязычная версия: Mathematical Notes, 1987, 42:4, 832–837

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

• 
• 
•