Эта публикация цитируется в
3 статьях
Импликативно селекторные множества
А. Н. Дёгтев Тюменский государственный университет
Аннотация:
Пусть
$A\subseteq \mathbf N=\{0,1,2,\dots\}$ и
$\beta$ –
$n$-местная булева функция. Множество
$A$ называется
$\beta$-импликативно селекторным (
$\beta$-ИС) множеством, если существует
$n$-местная селекторная общерекурсивная функция
$f$ такая, что $(\forall x_,\dots,x_n)(\beta(\chi(x_1),\dots,\chi(x_n))=1$
$\Rightarrow$ $f(x_1,\dots,x_n)\in A)$, где
$\chi$ – характеристическая функция множества
$A$. Пусть
$F^{(m)}$,
$m\geq1$, – семейство всех
$d_{m+1}^*$-ИС множеств, где $d^*_{m+1}=\underset{1\leq i<j\leq m+1}\&(x_i\vee x_j)$,
$F^{(0)}=\mathbf N$,
$F^{(\infty)}$ – класс всех подмножеств
$\mathbf N$. Основной результат статьи – семейство всех
$\beta$-ИС множеств совпадает с одним из
$F^{(m)}$,
$m\geq0$, или с
$F^{(\infty)}$, причем имеют место строгие включения $F^{(0)}\subset F^{(1)}\subset\dotsb\subset F^{(\infty)}$.
УДК:
510.5 Поступило: 12.10.1994