|
Алгебра и логика, 1990, том 29, номер 3, страницы 303–314
(Mi al2105)
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Рекурсивно-комбинаторные свойства подмножеств натуральных чисел
А. Н. Дёгтев
Аннотация:
Пусть $A\subseteq N$ и $\beta$ — произвольная $n$-местная булева функция. Говорим, что $A$ — $\beta$-комбинаторно, если существует $n$-местная ОРФ $f$ такая, что
\begin{equation}
(\forall x_1,\dots,x_n)(f(x_1,\dots,x_n)\in A\Leftrightarrow \beta(\chi(x_1),\dots,\chi(x_n))=1), \tag{*}
\end{equation}
где $\chi$ — характеристическая функция $A$. Показывается, что если $\alpha\ne0, 1$ — булева функция, $A\ne\varnothing$, $N$, то $A$ — $\alpha$-комбинаторно $\Leftrightarrow$ $A$ — $\beta$-комбинаторно, где $\beta$ — одна из следующих семи функций:
\begin{equation}
x, \quad \overline{x}, \quad x+y, \quad x\wedge y, \quad x\vee y, \quad (x\wedge y)\vee z, \quad x\to y.\tag{**}
\end{equation}
Описываются все семь семейств подмножеств $N$, являющихся $\beta$-комбинаторными, когда $\beta$ пробегает функции из (**), а также полностью выясняются все возможные включения между этими семействами. Если же в (*) потребовать, чтобы $f(x_1,\dots,x_n)\in \{x_1,\dots,x_n\}$ и $\beta\ne x$, но $\beta(x_1,\dots,x_n)=x$, то семейство таких $\beta$-комбинаторных множеств совпадает либо с семейством рекурсивных, либо с семейством полурекурсивных множеств.
Поступило: 25.03.1988
Образец цитирования:
А. Н. Дёгтев, “Рекурсивно-комбинаторные свойства подмножеств натуральных чисел”, Алгебра и логика, 29:3 (1990), 303–314
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2105 https://www.mathnet.ru/rus/al/v29/i3/p303
|
Статистика просмотров: |
Страница аннотации: | 46 | PDF полного текста: | 22 |
|