RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1991, том 3, выпуск 4, страницы 128–142 (Mi dm827)

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

О степени равномерного id-разложения замкнутых классов в $P_k$

С. С. Марченков


Аннотация: Рассматривается представление функций $f(x_1,\dots,x_n)$ из $P_k$ в виде $h(F_2^1,\dots,F_m^1,F_1^m,\dots,F_{m-1}^m)$, где $2\leqslant m\leqslant n$ и $F_j^i=f(x_1,\dots,x_{j-1},x_j,x_{j+1},\dots,x_n)$ ри $i\ne j$. Степенью равномерного id-разложения класса $R$ из $P_k$ называется наименьшее число $m$, для которого существует такая функция $h$ от $m(m-1)$ переменных, что указанное выше представление имеет место при $n\geqslant m$ для любой функции $f(x_1,\dots,x_n)$ из $R$. Доказано, что для класса $P_k$ и большинства предполных в $P_k$ классов степени равномерного id-разложения равны $2k$.

УДК: 519

Статья поступила: 11.11.1990



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


© МИАН, 2024