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

Дискрет. матем., 1989, том 1, выпуск 1, страницы 32–42 (Mi dm895)

О числе функций в некоторых замкнутых классах частичной $k$-значной логики

В. Б. Алексеев


Аннотация: Если $Q$ – произвольный класс функций в некоторой функциональной системе, замкнутый относительно переименования переменных без отождествления, то важной характеристикой этого класса является число функций в нем, зависящих от $n$ фиксированных переменных. В ряде работ эта величина исследовалась для замкнутых классов из алгебры логики $P_2$ и $k$-значной логики $P_k$.
В работах китайского математика Ло Чжукая описаны все максимальные замкнутые (предполные) классы в частичной $k$-значной логике $P_k^*$. Все они, кроме одного, являются классами типа $U^*(R)$ функций, сохраняющих некоторое отношение $R$ на множестве $E_k=\{0,1,\dots,k-1\}$. В статье рассматриваются те предполные классы в $P_k^*$, которые являются классами типа $U^*(R)$, где $R=R(y_1,y_2)$ – двухместное отношение, и для каждого такого класса устанавливается асимптотика логарифма числа функций от $n$ переменных в данном классе при $n\to\infty$ в зависимости от свойств отношения $R$.

УДК: 519.716

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


 Англоязычная версия: Discrete Mathematics and Applications, 1991, 1:1, 23–33

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


© МИАН, 2024