
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{multicol}
\setcounter{MaxMatrixCols}{21}
\usepackage{tikz}
\usepackage{hyperref}

\def\udcs{519.716} %Здесь автор определяет УДК своей работы
\def\mscs{08A99} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
        {\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[О позитивной полноте и позитивно замкнутых множествах]{О позитивной полноте и позитивно замкнутых множествах мультифункций ранга 2}
\author{{И.К. ШАРАНХАЕВ}}%
\address{Ivan Konstantinovich Sharankhaev  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Dorzhi Banzarov Buryat State University,
\newline\hphantom{iii} 24a, Smolina str.,
\newline\hphantom{iii} 670000, Ulan-Ude, Russia}%
\email{goran5@mail.ru}%

\thanks{\sc Sharankhaev, I.K.
On positive completeness and positively closed sets of multifunctions of rank 2}
\thanks{\copyright \ 2021 Шаранхаев И.К.}
\thanks{\rm Исследование выполнено за счет гранта Российского научного фонда №22--21--20013,  https://rscf.ru/project/22-21-20013/ и Правительства Республики Бурятия.}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2015 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } In article the problem of expressibility of multifunctions of rank 2 by positive closure operator is considered. A necessary and sufficient condition for the positive completeness of an arbitrary set of multifunctions and all positively closed sets of multifunctions are found.\medskip

\noindent{\bf Keywords:} multifunction, positive closure, superposition, completeness, k-valued logic.
 \end{quote}
}


\section{Введение}

В теории функций $k$-значной логики традиционной проблемой является исследование решетки так называемых замкнутых классов. Число замкнутых классов булевых функций является счетным, а для функций $k$-значной логики при $k>2$ и вовсе континуальным. Счетная решетка для булевых функций описана Э. Постом \cite{Post}, при больших значениях $k$ описание данной решетки вызывает серьезные трудности.

В связи с этим предлагается подход, при котором рассматриваются более сильные операторы замыкания в отличие от суперпозиции, которые позволяют «сжать» эту решетку до конечного множества. В работах \cite{mar1} -- \cite{riab1} исследуется оператор позитивного замыкания. Этот оператор рассматривался для таких классов дискретных функций как булевы функции, функции трехзначной логики, частичные булевы функции и гиперфункции ранга 2.
В настоящей статье данный оператор удалось определить на множестве мультифункций. Автором найден критерий позитивной полноты произвольного множества мультифункций на двухэлементном множестве, описаны все позитивно замкнутые множества мультифункций.


\section{Основные понятия и определения}

Пусть $E=\{0, 1\}$ и $F=\{\varnothing, \{0\}, \{1\}, \{0, 1\}\}$. Определим
следующие множества функций:

$P_{2,n} = \{f | f:E^n \rightarrow E\}$, $P_2 = \bigcup \limits_{n} P_{2,n};$

$P^*_{2,n} = \{f | f:E^n \rightarrow E \cup \{\varnothing\}\}$, $P^*_2 = \bigcup \limits_{n} P^*_{2,n};$

$P^-_{2,n} = \{f | f:E^n \rightarrow F \setminus \{\varnothing\}\}$, $P^-_2 = \bigcup \limits_{n} P^-_{2,n};$

$M_{2,n} = \{f | f:E^n \rightarrow F\}$, $M_2 = \bigcup \limits_{n} M_{2,n}.$

Функции из $P_2$ называют булевыми функциями, из $P^*_2$ -- частичными функциями на $E$, из $P^-_2$ -- гиперфункциями на $E$, а из $M_2$ -- мультифункциями на $E$ (мультифункциями ранга 2). Очевидно, что $P_2\subset P^*_2 \subset M_2$, $P_2\subset P^-_2 \subset M_2.$

Для того, чтобы суперпозиция $$f(f_1(x_1, \dots, x_m), \dots, f_n(x_1, \dots, x_m)),$$ где $f, f_1, \dots, f_n \in M_2$, определяла мультифункцию $g(x_1, \dots, x_m)$ определим значения мультифункции $f$ на наборах из множества $F$ следующим образом:
если $(\alpha_1, \dots, \alpha_m) \in E^m$, то

$$g(\alpha_1, \dots, \alpha_m)=
        \bigcup \limits_{\beta_i \in f_i(\alpha_1, \dots, \alpha_m)} f(\beta_1, \dots, \beta_n).
$$

На наборах, содержащих $\varnothing$, мультифункция принимает значение $\varnothing$.

Данное определение позволяет вычислить значение мультифункции $$f(x_1, \dots, x_n)$$  на любом наборе $(\sigma_1, \dots, \sigma_n) \in F^n$. С учетом этого факта назовем расширением мультифункции $f$ функцию $f^*: F^n \rightarrow F$, для которой $$f^*(\sigma_1, \dots, \sigma_n)=f(\sigma_1, \dots, \sigma_n)$$ для любого набора $(\sigma_1, \dots, \sigma_n) \in F^n$.

Подробное описание понятия суперпозиции мультифункций смотрите, например, в \cite{pantag}.

Замыканием множества мультифункций $K$ называется множество всех мультифункций, полученных из мультифункций множества $K$ с помощью суперпозиции, добавления и удаления фиктивных переменных. Замыкание множества $K$ обозначается через $[K]$. Множество мультифункций $K$ называется замкнутым (замкнутым классом), если $K=[K]$.

Множество $B$ называется полным, если $[B]$ совпадает с множеством всех мультифункций.

Для упрощения записи используется кодировка: $\{\varnothing\} \leftrightarrow *$,
$\{0\} \leftrightarrow 0$, $\{1\} \leftrightarrow 1$,
$\{0, 1\} \leftrightarrow -$, тогда $F=\{0, 1, *, -\}$.

Пусть $R^s$ -- $s$-местный предикат, заданный на множестве $F$. Будем говорить, что мультифункция $f(x_1, \dots, x_n)$ сохраняет предикат $R^s$, если для любых наборов $$(\alpha_{11}, \dots, \alpha_{s1}), \dots, (\alpha_{1n}, \dots, \alpha_{sn}),$$ принадлежащих предикату $R^s$, набор $$(f^*(\alpha_{11}, \dots, \alpha_{1n}), \dots, f^*(\alpha_{s1}, \dots, \alpha_{sn}))$$
принадлежит $R^s$, где $f^*$ -- расширение $f$.

Обозначим через $S$ множество всех самодвойственных булевых функций.

Обозначим через $S^*$ множество всех частичных функций, сохраняющих предикат $$\begin{pmatrix}
    0 & 1 & * \\
    1 & 0 & *
\end{pmatrix}.$$

Обозначим через $S^-$ множество всех гиперфункций, сохраняющих предикат $$\begin{pmatrix}
    0 & 1 & - \\
    1 & 0 & -
\end{pmatrix}.$$

Обозначим через $K_8$ множество всех мультифункций, сохраняющих предикат $$\begin{pmatrix}
    0 & 1 & * & - \\
    1 & 0 & * & -
\end{pmatrix}.$$

Символами языка $Pos$ являются переменные $x_1, x_2, \dots, x_n, \dots$, символы $f_i$ для обозначения мультифункций, символ включения $\subseteq$, логические связки конъюнкция $\&$ и дизъюнкция $\vee$, квантор существования $\exists$, левая и правая скобки, запятая.

Введем понятие терма:

-- любая переменная есть терм;

-- если $x_{i_1}, \dots, x_{i_n}$ -- переменные (возможно различные), а $f$ -- символ $n$-местной мультифункции, то $f(x_{i_1}, \dots, x_{i_n})$ есть терм;

-- если $t_1, \dots, t_n$ -- термы, $f$ -- символ $n$-местной мультифункции, то $f(t_1, \dots, t_n)$ есть терм.

Всякий терм $t$ языка $Pos$ определяет некоторую мультифункцию $h$. Если $f_1, \dots, f_n$ -- символы мультифункций, входящих в терм $t$, то будем говорить, что терм $t$ выражает мультифункцию $h$ через мультифункции $f_1, \dots, f_n$.

Понятие формулы определяется следующим образом:

-- если $t_1, t_2$ -- термы языка $Pos$, то выражение $(t_1 \subseteq t_2)$ называется элементарной формулой;

-- если $\Phi_1, \Phi_2$ -- формулы, а $x_i$ -- переменная, то $(\Phi_1 \& \Phi_2)$, $(\Phi_1 \vee \Phi_2)$, $(\exists x_i) \Phi_1$ -- формулы языка $Pos$ (позитивные формулы).

Любая формула языка $Pos$ c $n$ свободными переменными определяет $n$-местное отношение (предикат) на $E$.
Пусть $P$ -- произвольное множество мультифункций, $[P]$ -- замыкание $P$ относительно суперпозиции, $f(x_1, \dots, x_n)$ -- некоторая мультифункция, $\Phi(x_1, \dots, x_n, y)$ -- формула языка $Pos$ со свободными переменными $x_1, \dots,x_n, y$, все функциональные символы которой являются обозначениями мультифункций из $[P]$, формула $\Phi(x_1, \dots, x_n, y)$ определяет отношение $\rho(x_1, \dots,x_n, y)$ на множестве $E$. Будем говорить, что формула $\Phi(x_1, \dots, x_n, y)$ позитивно выражает отношение $\rho(x_1, \dots,x_n, y)$ через мультифункции множества $P$.

Очевидно, что любая $n$-местная мультифункция $f(x_1, \dots,x_n)$ однозначно определяет $(n+1)$-местное отношение, позитивно выраженное формулой $y \subseteq f(x_1,\dots,x_n)$, и наоборот.
Будем говорить, что формула $\Phi(x_1, \dots, x_n, y)$ позитивно выражает мультифункцию $f(x_1, \dots,x_n)$ через мультифункции множества $P$, если формулы $\Phi(x_1, \dots, x_n, y)$ и $y \subseteq f(x_1,\dots,x_n)$ позитивно выражают одно и тоже отношение на $E$.

Заметим, что данное определение позитивной формулы применительно для булевых функций и гиперфункций совпадает с определениями из \cite{mar1} и \cite{riab1}.

Множество всех мультифункций, позитивно выразимых через мультифункции множества $P$, назовем позитивным замыканием множества $P$ и обозначим $Pos[P]$. Отметим, что $P$ может быть равным пустому множеству $\varnothing$, т. е. в этом случае в формулах не используются функциональные символы. Заметим также, что множество всех проекций является подмножеством $Pos[\varnothing]$ \cite{mar1}. Множество $P$, совпадающее со своим позитивным замыканием, называется позитивным замкнутым.

Множество $B$ называется позитивно полным, если $Pos[B]$ совпадает с множеством всех мультифункций.

\section{Вспомогательные утверждения}

В этом разделе доказываются некоторые утверждения, необходимые при получении основных результатов.

\begin{lemma}
Множество $K_8$ является позитивно замкнутым.
\end{lemma}
\begin{proof}
Пусть позитивная формула $\Phi(x_1, \dots, x_n, y)$ получена с
помощью $g_1,\dots,g_k$ из $K_8$. Покажем, что если такая
формула и $y \subseteq f(x_1,\dots,x_n)$ будут выражать одно и то же отношение, то $f(x_1,\dots,x_n)$ также принадлежит $K_8$.
Для этого покажем, что таблица истинности формулы $\Phi$ является
симметричной, т. е. на противоположных наборах формула принимает
одинаковые истинностные значения.

Доказательство проведем индукцией по построению формулы $\Phi$.

Базис индукции. Рассмотрим элементарную формулу
$$\Phi(x_1, \dots, x_n, y) = g_1(z_1,\dots,z_p) \subseteq g_2(w_1,\dots,w_q),$$ где $\{z_1,\dots,z_p\} \subseteq \{x_1,\dots,x_n, y\}$, $\{w_1,\dots,w_q\} \subseteq \{x_1,\dots,x_n, y\}$ и $g_1, g_2 \in K_8$.

Построим для этой формулы таблицу истинности и определим истинность формулы на произвольном наборе $(\alpha_1,\dots,\alpha_n, \alpha_0)$ и его отрицании. Для этого на данном наборе рассмотрим возможные значения
мультифункций $g_1, g_2$. Будем считать, что
$$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) = g_1(\beta_1,\dots,\beta_p) \subseteq g_2(\gamma_1,\dots,\gamma_q),$$
где $\{\beta_1,\dots,\beta_p\} \subseteq \{\alpha_1,\dots,\alpha_n, \alpha_0\}$ и $\{\gamma_1,\dots,\gamma_q\} \subseteq \{\alpha_1,\dots,\alpha_n, \alpha_0\}$.

1. Пусть $g_1(\beta_1,\dots,\beta_p)=a$, где $a \in E$. Рассмотрим возможные
значения $g_2$. Если $g_2(\gamma_1,\dots,\gamma_q)=a$, то в силу того, что $g_1, g_2 \in K_8$, получим $g_1(\bar{\beta}_1,\dots,\bar{\beta}_p)=\bar{a}$ и $g_2(\bar{\gamma}_1,\dots,\bar{\gamma}_q)=\bar{a}$. В этом случае
$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=И.

Если $g_2(\gamma_1,\dots,\gamma_q)=\bar{a}$, то $g_1(\bar{\beta}_1,\dots,\bar{\beta}_p)=\bar{a}$ и $g_2(\bar{\gamma}_1,\dots,\bar{\gamma}_q)=a$. Тогда
$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=Л.

Если $g_2(\gamma_1,\dots,\gamma_q)=-$, то $g_2(\bar{\gamma}_1,\dots,\bar{\gamma}_q)=-$. Тогда
$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=И.

Если $g_2(\gamma_1,\dots,\gamma_q)=*$, то $g_2(\bar{\gamma}_1,\dots,\bar{\gamma}_q)=*$. Тогда
$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=Л.

2. Пусть $g_1(\beta_1,\dots,\beta_p)=-$. Если $g_2(\gamma_1,\dots,\gamma_q) \in E$, то $\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=Л.

Если $g_2(\gamma_1,\dots,\gamma_q)=-$, то $\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=И.

Если $g_2(\gamma_1,\dots,\gamma_q)=*$, то
$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=Л.

3. Пусть $g_1(\beta_1,\dots,\beta_p)=*$. Если $g_2(\gamma_1,\dots,\gamma_q) \in E$, то $\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=И.

Если $g_2(\gamma_1,\dots,\gamma_q)=-$, то $\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=И.

Если $g_2(\gamma_1,\dots,\gamma_q)=*$, то
$\Phi(\alpha_1,\dots,\alpha_n, \alpha_0) =\Phi(\bar{\alpha}_1,\dots,\bar{\alpha}_n, \bar{\alpha}_0)$=И.

Шаг индукции. Рассмотрим формулу вида $(\Phi_1 \& \Phi_2)$ или $(\Phi_1 \vee \Phi_2)$.
В силу индуктивного предположения формулы $\Phi_1$, $\Phi_2$ на противоположных наборах принимают одинаковые истинностные значения. Таким образом, рассматриваемая формула на противоположных наборах также принимает одинаковые истинностные значения.

Рассмотрим формулу вида $(\exists x_1) \Phi_1$. В силу индуктивного предположения формула $\Phi_1$ на противоположных наборах принимает одинаковые истинностные значения. Очевидно, что $(\exists x_1) \Phi_1$ на противоположных наборах также принимает одинаковые истинностные значения.
\end{proof}

\begin{lemma}
Любое позитивно замкнутое множество мультифункций замкнуто относительно суперпозиции.
\end{lemma}
\begin{proof}
Полностью аналогично доказательству утверждения 1 из \cite{riab2}.
\end{proof}

В \cite{pant} доказана следующая

\begin{lemma}
Множество $U \cup \{h\}$, где $U$ -- множество всех одноместных мультифункций, $h=(*0000000)$, полно.
\end{lemma}

\begin{lemma} Верно, что
$P^*_2 \subseteq Pos[\{0, 1\}]$ и $S^* \subseteq Pos[\{\bar{x}\}]$.
\end{lemma}
\begin{proof} Докажем, что $P^*_2 \subseteq Pos[\{0, 1\}]$.
В \cite{mar3} доказано, что $\{0, 1\}$ позитивно порождает $P_2$, т. е. $$P_2 \subseteq Pos[\{0, 1\}].$$ Пусть $f(x_1, \dots, x_n) \in P^*_2$. Определим булевы функции $f_0$ и $f_1$ следующим образом: если для набора $(a_1, \dots, a_n)$ верно, что  $f(a_1, \dots, a_n) \in \{0, 1\}$, то $$f(a_1, \dots, a_n)=f_0(a_1, \dots, a_n)=f_1(a_1, \dots, a_n),$$
а если $f(a_1, \dots, a_n)=*$, то $$f_0(a_1, \dots, a_n) \neq f_1(a_1, \dots, a_n).$$
Тогда $f(x_1, \dots, x_n)$ позитивно выражается формулой
$$(f_0(x_1, \dots, x_n) \subseteq f_1(x_1, \dots, x_n)) \& (y \subseteq f_0(x_1, \dots, x_n)).$$

Докажем, что $S^* \subseteq Pos[\{\bar{x}\}]$.
В \cite{mar3} доказано, что $S \subseteq Pos[\{\bar{x}\}].$ Пусть $f(x_1, \dots, x_n) \in S^*$. Определим булевы функции $f_0$ и $f_1$ следующим образом: если для набора $(a_1, \dots, a_n)$ верно, что  $f(a_1, \dots, a_n) \in \{0, 1\}$, то $$f(a_1, \dots, a_n)=f_0(a_1, \dots, a_n)=f_1(a_1, \dots, a_n),$$
а если $f(a_1, \dots, a_n)=*$, то $$f_0(0, a_2, \dots, a_n)=0,  f_1(0, a_2, \dots, a_n)=1,$$ $$f_0(1, a_2, \dots, a_n)=1,  f_1(1, a_2, \dots, a_n)=0.$$
Тогда $f(x_1, \dots, x_n)$ позитивно выражается формулой
$$(f_0(x_1, \dots, x_n) \subseteq f_1(x_1, \dots, x_n)) \& (y \subseteq f_0(x_1, \dots, x_n)).$$

\end{proof}



\begin{lemma}
Верно, что $S^* \cup S^- \subseteq Pos[\varnothing]$.
\end{lemma}
\begin{proof}
В \cite{riab1} доказано, что $S^- \subseteq Pos[\varnothing]$, т. е. любая мультифункция из $S^-$ позитивно выражается из любого множества мультифункций. По лемме 4 имеем $S^* \subseteq Pos[\{\bar{x}\}]$. Поскольку $\bar{x} \in S^-$ имеем $S^* \cup S^- \subseteq Pos[\varnothing]$.

\end{proof}


\begin{lemma}
Любая из мультифункций $(00)$, $(11)$, $(*0)$, $(*1)$, $(0*)$, $(1*)$, $(*-)$, $(-*)$, $(-0)$, $(-1)$, $(0-)$, $(1-)$ дает одноэлементное позитивно полное множество.
\end{lemma}

\begin{proof} Как следует из \cite{riab1}, каждая из $(00)$, $(11)$, $(-0)$, $(-1)$, $(0-)$, $(1-)$ дает все мультифункции из $P^{-}_2$. Так как по лемме 4 имеем $P^*_2 \subseteq Pos[\{0, 1\}]$, то в силу лемм 2, 3 доказываемое утверждение верно в этих случаях.

В случаях $(*0)$, $(*1)$, $(0*)$, $(1*)$ с помощью $(--)$, которую имеем по лемме 5, опять получим константу 0 или 1.

В случаях $(*-)$, $(-*)$ заметим сначала, что с помощью $(10)$, которую имеем по лемме 5, в любом варианте получим $(*-)$.

Далее с помощью этой мультифункции, леммы 5 и следующих суперпозиций

$$\begin{pmatrix} * \\ *\\-\\- \end{pmatrix}
\begin{pmatrix} 0&-\\-&0\\-&1\\1&- \end{pmatrix}
=\begin{pmatrix} *\\-\\-\\- \end{pmatrix},$$

$$\begin{pmatrix} 0 \\ 0\\1\\1 \end{pmatrix}
\begin{pmatrix} 0&*\\0&-\\1&-\\1&- \end{pmatrix}
=\begin{pmatrix} *\\0\\1\\1 \end{pmatrix}$$
получим мультифункцию $(*011)$. Из нее отождествлением переменных имеем мультифункцию $(*1)$, а этот случай рассмотрен. Лемма доказана.

\end{proof}



\begin{lemma}
Верно, что $K_8 \subseteq Pos[\varnothing]$.
\end{lemma}

\begin{proof} В силу лемм 2, 5 достаточно показать, что любую мультифункцию из $K_8$ можно выразить с помощью мультифункций из $S^* \cup S^-$.

Пусть $f(x_1, \dots, x_n)$ -- произвольная мультифункция из $K_8$. Обозначим через $f_1(x_1, \dots, x_n)$ гиперфункцию такую, что для любого набора $\tilde{\alpha}$ верно, что $f_1(\tilde{\alpha})=f(\tilde{\alpha})$, если $f(\tilde{\alpha}) \neq *$, и $f_1(\tilde{\alpha})=-$, если $f(\tilde{\alpha})=*$. Очевидно, что $f_1 \in S^-$.

Рассмотрим $f_1(x_1, \dots, x_{n-1}, g(x_1, \dots,x_n))$, где
$g(x_1, \dots, x_n)$ такая, что на всех наборах верно, что $g(x_1, \dots, x_n)=x_n$ кроме тех наборов $\beta$ таких, что $f(\tilde{\beta})=*$, в этих случаях $g(\tilde{\beta})=*$. Очевидно, что $g \in S^*$ и $$f(x_1, \dots, x_n)=f_1(x_1, \dots, x_{n-1}, g(x_1, \dots,x_n)).$$ Лемма доказана.

\end{proof}

\section{Основные результаты}

В этом разделе предлагается теорема, дающая необходимое и достаточное условие позитивной полноты произвольного множества мультифункций, и доказано, что существует ровно 2 позитивно замкнутых множества мультифункций.

\begin{theorem}
    Множество мультифункций $B$ является позитивно полным тогда и только тогда, когда выполнено условие, что $B \not \subseteq K_8$.
\end{theorem}

\begin{proof} Необходимость. От противного. Пусть $B \subseteq K_8$. Тогда $$Pos[B]=M_2 \subseteq K_8.$$ Противоречие в силу леммы 1.

Достаточность. Пусть $f \not \in K_8$. Заметим, что по лемме 7 отрицание позитивно выражается из любого множества мультифункций. Тогда с помощью $f$, отождествления переменных и отрицаний получим одну из $(00)$, $(11)$, $(*0)$, $(*1)$, $(0*)$, $(1*)$, $(*-)$, $(-*)$, $(-0)$, $(-1)$, $(0-)$, $(1-)$. В силу леммы 6 утверждение доказано.

\end{proof}


\begin{theorem} Существует ровно 2 позитивно замкнутых множества $K_8$ и $M_2$.
\end{theorem}

\begin{proof} Следует из леммы 7 и теоремы 1.

\end{proof}



\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).


\bibitem{Post} E.L. Post, {\it Introduction to a General Theory of Elementary Proposition}, Amer. J. Math., \textbf{43}:4 (1921),163--185.

\bibitem{mar1} S.S. Marchenkov, {\it Closed classes of Boolean functions}, Fizmatlit, M., 2000.

\bibitem{mar2} S.S. Marchenkov,  {\it A criterion for positive completeness in ternary logic}, Journal of Applied and Industrial Mathematics, \textbf{1}:4 (2007), 481--488. \url{https://www.mathnet.ru/links/0e3caeff4c253e43a89c45ca37c95e25/da34.pdf}

\bibitem{mar3} S.S. Marchenkov, A.A. Popova {\it Positively closed classes of partial Boolean functions}, Vestnik of Moscow university. Ser. 15. Computational math. and cybern., \textbf{3} (2008), 30--34.

\bibitem{mar4} S.S. Marchenkov,  {\it Positive closed classes in the three-valued logic}, Journal of Applied and Industrial Mathematics, \textbf{8}:2 (2014), 256--266.
\url{https://www.mathnet.ru/links/22d1239ac1926c78710a2a8f7843946e/da761.pdf}

\bibitem{riab1} L.V. Riabets, {\it Operators of parametric and positive closure on the set of hyperfunctions of rank 2}, Intelligent systems. Theory and applications, {\bf 20}:3 (2016), 79--84.
\url{https://www.mathnet.ru/links/7364b7e5fc1a1d8c5b36cc43e7a70d4a/ista93.pdf}

\bibitem{pantag} V.I. Panteleyev, E.S. Taglasov, {\it $ES_I$--closure of rank 2 multi-functions: completeness criterion,
classification and types of bases}, Intelligent systems. Theory and applications, {\bf 25}:2 (2021), 55--80.
\url{https://www.mathnet.ru/links/14b34cca5e050bbcec870b534c12beb8/ista303.pdf}

\bibitem{riab2} L.V. Riabets, {\it Parametric closed classes of hyperfunctions of rank 2}, Izvestiya Irk. Gos. Univ. Ser. Matematika, {\bf 17} (2016), 46--61.
\url{https://www.mathnet.ru/links/d4e7c0f49d3fa403f81a9d80b4aa2739/iigum272.pdf}

\bibitem{pant} V.I. Panteleyev, {\it Completeness criterion for sub-defined partial Boolean functions},  Vestnik Novosibir. Gos. Univ. Ser.: Matem., Mechan., Inform., \textbf{9}:3 (2009), 95--114.
\url{https://www.mathnet.ru/links/03c6afc79775397933f75cd6323509a6/vngu185.pdf}


\end{thebibliography}
\end{document}
