|
Дискретная математика, 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$.
Статья поступила: 03.09.1988
Образец цитирования:
В. Б. Алексеев, “О числе функций в некоторых замкнутых классах частичной $k$-значной логики”, Дискрет. матем., 1:1 (1989), 32–42; Discrete Math. Appl., 1:1 (1991), 23–33
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm895 https://www.mathnet.ru/rus/dm/v1/i1/p32
|
Статистика просмотров: |
Страница аннотации: | 479 | PDF полного текста: | 180 | Первая страница: | 4 |
|