|
Алгебра и логика, 1990, том 29, номер 4, страницы 421–429
(Mi al2113)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Слабые комбинаторно-селекторные свойства подмножеств натуральных чисел
А. Н. Дёгтев
Аннотация:
Пусть $A\subseteq N$ и $\beta$ — $n$-местная булева функция. Назовем $A$ слабо $\beta$-селекторным множеством, если существует $n$-местная ЧРФ $f$ такая, что выполнены следующие условия:
(а) $(\forall x_1,\dots, x_n)(f(x_1,\dots, x_n)\downarrow\Rightarrow f(x_1,\dots, x_n)\in\{x_1,\dots, x_n\})$;
(б) $(\forall x_1,\dots, x_n)(x_1,\dots, x_n\in A\Rightarrow f(x_1,\dots, x_n)\downarrow)$;
(c) $(\forall x_1,\dots, x_n)(f(x_1,\dots, x_n)\downarrow\Rightarrow (f(x_1,\dots, x_n)\in A\Rightarrow\beta(\chi(x_1),\dots,\chi(x_n))=1))$,
где $f(x_1,\dots,x_n)\downarrow$ означает, что $f(x_1,\dots,x_n)$ определено, $\chi$ — характеристическая функция $A$. Назовем множество $A\subseteq N$ слабо полурекурсивным (селекторным), если оно слабо $\beta$-селекторное, где $\beta=x\vee y$ (соответственно $\beta=(x\wedge y)\vee(x\wedge z)\vee(y\wedge z)$). Доказывается
Теорема. Пусть булева функция $\beta$ такова, что $\beta(x,\dots, x)=x$, и $\beta\not\equiv x$.
Тогда класс $\beta$-селекторных множеств совпадает или с классом всех РПМ, или с классом слабо полурекурсивных, или с классом слабо селекторных множеств.
Затем выясняются некоторые свойства множеств из этих классов (в частности, класс слабо селекторных множеств строго содержит класс слабо полурекурсивных множеств).
Поступило: 06.04.1988
Образец цитирования:
А. Н. Дёгтев, “Слабые комбинаторно-селекторные свойства подмножеств натуральных чисел”, Алгебра и логика, 29:4 (1990), 421–429
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2113 https://www.mathnet.ru/rus/al/v29/i4/p421
|
|