\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

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

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

\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

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

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



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


\thispagestyle{empty}

\title[\sc О параметрическом замыкании множества $\mathcal M$]{\large О параметрическом замыкании множества мультиопераций ранга 2}
\author[В.И. ПАНТЕЛЕЕВ]{{\bf \large \textsc{В.И. Пантелеев}}\protect\orcidicon{0000-0003-4766-486X}}
\author[Л.В. РЯБЕЦ]{{\bf \large \textsc{Л.В. Рябец}}\protect\orcidicon{0000-0003-4047-9573} 
%\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
\address{Vladimir Innokent'yevich Panteleev % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Dorzhi Banzarov Buryat State University,
\newline\hphantom{iii} 24a, Smolina str.,
\newline\hphantom{iii} 670000, Ulan-Ude, Russia }%
\email{\textcolor{blue}{vl.panteleyev@gmail.com}} %
\address{Leonid Vladimirovich Ryabets % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Institute of Mathematics and Information Technologies, Irkutsk State University, 
\newline\hphantom{iii} K. Marx st, 1,
\newline\hphantom{iii} 664000, Irkutsk, Russia}%
\email{\textcolor{blue}{l.riabets@gmail.com}} %

\thanks{\sc Panteleev V.I., Ryabets L.V.
Parametric closed sets of multioperations on two-element set}
\thanks{\copyright \ 2024 Пантелеев В.И., Рябец Л.В.}
\thanks{\rm Исследование первого автора выполнено за счет гранта
	Российского научного фонда № 24-21-00011, https://rscf.ru/project/24-21-00011/}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} In this paper the problem of classifying a set of multioperations of rank 2 with respect to the parametric closure operator is considered.
A completeness criterion was found and it was shown that the set of all multioperations contains two parametrically closed classes.  \medskip

\noindent{\bf Keywords:} multifunction, multioperation, parametric closure, superposition, completeness criterion, $k$-valued logic.
 \end{quote}
}

\bigskip

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

Классификация --- одно из важнейших направлений исследований в теории дискретных функций. Основное направление классификации связано с оператором суперпозиции и основано на  принадлежности функций замкнутым относительно суперпозиции множествам. 

Наряду с классическими функциональными системами, в которых основным  множеством является множество функций $k$-значной логики, достаточно давно изучаются и функциональные системы, в которых рассматриваются обобщения функций $k$-значной логики: частичные функции, гипер- и  мультифункции --- функции, заданные на конечном множестве~$A$ и принимающие в качестве своих значений подмножества (с некоторыми ограничениями или без) множества $A$.  

Однако, для функций $k$-значной логики при $k>2$ классификация, основанная только на суперпозиции, приводит к континууму замкнутых множеств. Аналогичный результат справедлив для частичных функций задаваемых даже на 2-х элементном множестве~\cite{Frei1998}.  Впрочем, как показал Н.~Machida~\cite{Mach2002}, и суперпозиция гиперфункций на 2-х элементном множестве также  приводит к континууму замкнутых классов. Исследования классификаций функций, заданных на конечном множестве и принимающих в качестве своих значений подмножества этого множества (все или некоторые), относительно оператора суперпозиции представлены в~\cite{lo-1988,lo-1988b,T1975,Pant2005,Mach2002,MachPant2008,Rom1998}.

Попытки сократить континуальные классификации приводят к необходимости изучения более сильных операторов замыкания. Одним из таких является оператор параметрического замыкания, предложенный А.В.~Кузнецовым~\cite{K1979}. Этот оператор порождает 25 параметрически замкнутых классов булевых функций, 2986 параметрически замкнутых классов функций 3-х значной логики \cite{D1977,D1978}. При $k\geqslant 4$ конечность числа
параметрически замкнутых классов множества функций $k$-значной логики доказана в~\cite{B1987}. Подробное описание параметрически замкнутых классов булевых функций представлено в работе~\cite{M2000}. 

Одним из расширений оператора параметрического замыкания является оператор позитивного замыкания. Исследования, посвященные этому оператору над различными множествами функций, представлены в работах~\cite{M1999,M2008,M2014}. 


В \cite{R2016ISU,R2016} идея оператора параметрического замыкания была расширена на множество гиперфункций, заданных на двухэлементном множестве. Оказалось, что язык формул, используемый при параметрическом описании, обладает сильными выразительными возможностями, которые привели к тому, что число замкнутых классов гиперфункций оказалось равно~13, несмотря на то, что множество булевых функций является подмножеством множества всех гиперфункций.



В соответствии с алгебраическим подходом, наряду с терминами (частичная, гипер-, мульти-) функция используют и термины (частичная, \mbox{гипер-,} мульти-) операция (см., например, \cite{Pouza2010}). %Нами также используется алгебраический подход. 

В настоящей работе показывается, что на множестве всех мультиопераций ранга 2 выразительные возможности языка параметрического описания являются очень сильными, что приводит к 2-м замкнутым классам. Этот результат остается неизменным и при переходе к позитивному замыканию~\cite{Sha2023}. 



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

Пусть $E_2=\{0,1\}$ и $\alpha_{i} \in E_2, \; i \in \{1,\dots,n\}$, тогда выражение \linebreak[4]
$\left( \alpha_1,\alpha_2, \dots, \alpha_n \right)$
называется двоичным набором или
просто набором и обозначается $\tilde{\alpha}$, а
число $n$ называется длиной этого набора. Если длина набора $\tilde{\alpha}$ явно не
указана, она определяется по контексту.
Набор $\tilde{\beta}$ назовем противоположным набору $\tilde{\alpha}$, если длины этих наборов совпадают и $\beta_i = \overline{\alpha}_i$ (как обычно, $\overline{0}=1$ и $\overline{1}=0$) для всех $i\in \{1,\dots,n\}$. Для набора, противоположного набору $\tilde{\alpha}$, будем использовать обозначение~$\overline{\tilde{\alpha}}$. 
Набор $(0,\ldots,0)$ называется нулевым и обозначается через $\tilde{0}$, а набор  $(1,\ldots,1)$ --- единичным и обозначается через $\tilde{1}$.
Для произвольного конечного множества $A$ через $|A|$ обозначим  мощность.

Для целого положительного $n$ отображение $ f:E_2^n \rightarrow 2^{E_2}$ назовем $n$-местной мультиоперацией ранга 2 или просто мультиоперацией. Множество всех $n$-местных мультиопераций обозначим как ${\mathcal M}_{n}$, а множество всех мультиопераций как ${\mathcal M}$. Очевидно, что  ${\mathcal M} =\bigcup_n {\mathcal M}_{n}$.

В множестве ${\mathcal M}$ выделим множество всех булевых операций (${\mathcal O}$) и множество гиперопераций (${\mathcal H}$)  следующим образом:
\begin{gather*}
		{\mathcal O}_{n}=
	\left\{
	f \mid f \in {\mathcal M}_{n} \text{ и } 
	|f(\tilde{\alpha})|=1 \text{ для всех }
	\tilde{\alpha} \in E_2^n
	\right\}, \; 	{\mathcal O} =\bigcup_n 	{\mathcal O}_{n},\\
	{\mathcal H}_{n}=
	\left\{
	f \mid f \in {\mathcal M}_{n} \text{ и } 
	|f(\tilde{\alpha})|\geqslant1 \text{ для всех }
	\tilde{\alpha} \in E_2^n
	\right\}, \; {\mathcal H} =\bigcup_n {\mathcal H}_{n}.
\end{gather*}

При дальнейшем изложении мы не будем различать множество из одного элемента и элемент этого множества. Для множества $E_2$ будем использовать обозначение <<$-$>> (прочерк), для пустого множества --- <<$\ast$>>. Под <<$-$>> и <<$\ast$>> будем понимать также мультиоперации, которые на любом своем наборе принимают значение $E_2$  и $\varnothing$, соответственно. Местность таких операций зависит от контекста.

Для одноместной мультиоперации $f \in {\mathcal M}$ будем использовать запись в виде вектора $(f(0)\,f(1))$. Например, вектором $(-\,0)$ обозначается такая мультиоперация
$f$, что $f(0)=-$ и $f(1)=0$. Для $n$-местной мультиоперации $f$ будем также использовать запись в виде вектора 
$(\alpha_{\tilde{0}}\ldots\alpha_{\tilde{1}})$ длины $2^n$, где каждый элемент $\alpha_{\tilde{\sigma}}=f(\tilde{\sigma})$.    

Пусть $f_0$ --- $n$-местная мультиоперация, $f_1,\ldots,f_n$ --- $m$-местные мультиоперации. Суперпозиция с внешней операцией $f_0$
и внутренними операциями $f_1,\ldots,f_n$
определяет $m$-местную мультиоперацию $$s(f_0,f_1,\ldots,f_n)$$  следующим образом:
для набора $(\alpha_1,\ldots,\alpha_m) \in E_2^m$ по определению\footnote{Определение суперпозиции мультиопераций позволяет находить значение мультиопераций не только на двоичных наборах. Подробно  можно посмотреть в~\cite{Pan2021}.}
\begin{equation}
	s(f_0,f_1,\ldots,f_n)(\alpha_1,\ldots,\alpha_m) = 
	\bigcup_{\substack{\beta_i\in f_i(\alpha_1,\ldots,\alpha_m)\\i\in\{1,\ldots,n\}}}
	f_0(\beta_1,\ldots,\beta_n).
	\label{eq-superposition}
\end{equation}
В соответствии с этим определением, если значение какой-либо мультиоперации $f_i$ на наборе $(\alpha_1,\ldots,\alpha_m)$ есть $\ast$, то и вся суперпозиция принимает значение $\ast$.

В дальнейшем мультиоперации будем рассматривать с точностью до фиктивных аргументов. Переменные для обозначения аргументов  используем  обычным образом, как и понятие <<мультиоперация-перемен\-ная>>. Также обычным образом используем понятие замыкание относительно суперпозиции множества операций $Q$, для которого будем использовать обозначение $[Q]$. Считаем известными обозначения для булевых операций от 2-х аргументов.


Пусть $A$ --- некоторое множество мультиопераций. Определим понятие <<мультиоперация над $A$>>: 
\begin{itemize}
	
	\item[$\bullet$]если $f\in A$, то  $f$ --- мультиоперация над $A$;
	
	\item[$\bullet$] если $f$ --- мультиоперация над  $A$, то операция, полученная из $f$ перестановкой или отождествлением аргументов является мультиоперацией над $A$;
	
	\item[$\bullet$] если $f_0$ --- $n$-местная, $f_i$ --- $m$-местные мультиоперации над $A$  или муль\-ти\-операции-перемен\-ные ($i\in\{1,\ldots,n\}$), то мультиоперация  $s(f_0,
	f_1, \ldots, f_n)$ есть мультиоперация над $A$. 
\end{itemize}

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

Определим понятия <<терм $t$ языка Par>> и <<множество переменных терма $t$>> --- $FV(t)$:
\begin{itemize}
	\item любая переменная является термом, $FV(t)=\{x\}$;
	\item[$\bullet$] если $x_{i_1}, \ldots, x_{i_n}$ --- переменные (не обязательно различные), а $f$ --- символ $n$-местной мультиоперации, то $f(x_{i_1}, \ldots, x_{i_n})$ есть терм, $FV(t)=\{x_{i_1}, \ldots, x_{i_n}\}$;
	\item[$\bullet$] если $t_1, \ldots, t_n$ --- термы, $f$ --- символ $n$-местной мультиоперации, то $s(f,t_1, \ldots, t_n)$ есть терм, $FV(t)=\bigcup\limits_{i\in\{1,\ldots,n\}} FV(t_i)$. 
\end{itemize}


Значение терма $t$ на наборе $(\alpha_1,\ldots,\alpha_m)$ значений переменных из множества $FV(t)$ определяется следующим образом:
\begin{itemize}
	\item если терм $t$ есть переменная $x$, то значение терма совпадает со значением этой переменной;
	\item если терм $t$ есть $f(x_{i_1}, \ldots, x_{i_n})$, то $t(\alpha_1,\ldots,\alpha_m) =f(\alpha_{i_1}, \ldots, \alpha_{i_n})$;
	\item если терм $t$ есть $s(f,t_1, \ldots, t_n)$, то $$t(\alpha_1,\ldots,\alpha_m)=\bigcup\limits_{\beta_i\in t_i(\alpha_1,\ldots,\alpha_m)} f(\beta_1,\ldots,\beta_n).$$
\end{itemize} 

Всякий терм $t$ определяет некоторую мультиоперацию.

Определим понятие <<формула языка Par>> (параметрическая формула). Если $t_1, t_2$ --- термы, то выражение ($t_1 \subseteq t_2$)  называется элементарной формулой. Остальные формулы определяем следующим образом:
если $\Phi_1, \Phi_2$ --- формулы, а $x_i$ --- переменная, то
$
\Phi_1 \; \& \; \Phi_2,  (\exists x_i) \Phi_1 
$--- формула.

Пусть $Q\subseteq \mathcal{M}$, $f(x_1, \ldots, x_n) \in \mathcal{M},$ $\Phi(x_1, \ldots x_n,y)$ --- формула языка Par со свободными переменными $x_1, \ldots x_n,y$, все операциональные символы которой являются обозначениями мультиопераций над~$Q$. Будем говорить, что формула $\Phi$ параметрически выражает мультиоперацию $f$ через мультиоперации множества~$Q$ (определяет отношение $y \subseteq f(x_1, \ldots, x_n)$), если множества истинности формулы $\Phi$ и отношения $y \subseteq f(x_1, \ldots, x_n)$ совпадают. Множество всех мультиопераций, параметрически выразимых через операции множества~$Q$, назовем параметрическим замыканием множества~$Q$ и обозначим $\mathrm{Par}[Q]$. Множество~$Q$, которое совпадает со своим параметрическим замыканием, называется параметрически замкнутым классом.
Множество $Q$ является параметрически полным, если его параметрическое замыкание совпадает с $\mathcal{M}$.	

\begin{example}
Пусть $f_1(x_1,x_2) = (-01-)$, $f_2(x_1,x_2) = (1-10)$ и  $g(x_1,x_2) = (001-)$ --- двухместные мультиоперации.
Рассмотрим  множество мультиопераций $Q=\{f_1, f_2\}.$ С помощью мультиопераций из $Q$ построим следующие формулы языка Par.
\begin{gather*}
	\Phi_1(x_1,x_2,y) = y \subseteq f_1(x_1,x_2),\\
	\Phi_2(x_1,x_2,y) = f_2(x_1,y) \subseteq f_1(x_2,y).	
\end{gather*}

Формула $\Phi(x_1,x_2,y)=\Phi_1(x_1,x_2,y)\;\&\;\Phi_2(x_1,x_2,y)$ параметрически выражает операцию $g$ через операции множества $Q$. Соответствующие таблицы истинности представлены ниже.
\begin{center}
	\begin{tabular}{ccc|c|c|c|c}
		$x_1$&$x_2$&$y$& $\Phi_1$&$\Phi_2$&$\Phi(x_1,x_2,y)$&$y \subseteq g(x_1,x_2)$\\ \hline
		0&0&0&И&И&И &И \\
		0&0&1&И&Л&Л &Л \\ \hline
		0&1&0&И&И&И &И \\
		0&1&1&Л&И&Л &Л \\  \hline
		1&0&0&Л&И&Л &Л \\
		1&0&1&И&И&И &И \\ \hline
		1&1&0&И&И&И &И \\
		1&1&1&И&И&И &И \\
	\end{tabular}
\end{center}
\end{example}

\begin{state}
	Любой параметрически замкнутый класс мультиопераций замкнут относительно операции суперпозиции.
\end{state}
\begin{proof}
	Пусть $Q$ --- параметрически замкнутый класс мультиопераций, $f_0, f_1, \ldots f_n \in Q$ и
	$$
	g(x_1,\ldots, x_m) = s(f_0, f_1, \ldots, f_n)(x_1,\ldots, x_m).
	$$
	Покажем, что $g \in Q$.
	
	Обозначим через
	$$
	\Phi_0(x_1, \ldots, x_n, y), \quad \Phi_1(x_1, \ldots, x_m, y), \quad
	\ldots, \quad 
	\Phi_n(x_1, \ldots, x_m, y)
	$$ 
	формулы языка Par, которые параметрически выражают отношения 
	$$
	y \subseteq f_0(x_1, \ldots, x_n), \quad
	y \subseteq f_1(x_1, \ldots, x_m), \quad
	\ldots, \quad
	y \subseteq f_n(x_1, \ldots, x_m)
	$$
	через операции множества $Q$. Тогда формула 
	\begin{multline*}
		(\exists y_1)\ldots(\exists y_n)(\Phi_1(x_1, \ldots, x_m, y_1)\;\& \ldots\\
		\ldots \& \; \Phi_n(x_1, \ldots, x_m, y_n) \; \& \; \Phi_0(y_1, \ldots, y_n,z))
	\end{multline*}
	параметрически выражает отношение $z \subseteq g(x_1, \ldots, x_m)$ через операции множества $Q$. Таким образом, $g\in Q.$
\end{proof}

\begin{state}
	Если $[Q]=\mathcal{O}$, то $\mathrm{Par} [Q]=\mathcal{M}.$
\end{state}
\begin{proof}
	
	Пусть мультиоперация $f(x_1,\ldots,x_n) \in \mathcal{M}$. По $f$ построим $f_1, f_2\in \mathcal{O}$ следующим образом:  для набора $\tilde\alpha\in E_2^n$
	\begin{itemize}
		\item если $f(\tilde\alpha)=0$, то $f_1(\tilde\alpha)=f_2(\tilde\alpha)=0$;
		\item если $f(\tilde\alpha)=1$, то $f_1(\tilde\alpha)=f_2(\tilde\alpha)=1$;
		\item если $f(\tilde\alpha)=-$, то $f_1(\tilde\alpha)=0,f_2(\tilde\alpha)=1$;
		\item если $f(\tilde\alpha)=\ast$, то $f_1(\tilde\alpha)=1,f_2(\tilde\alpha)=0$.
	\end{itemize}
	
	Формула $$\Phi(\tilde x,y)=(f_1\rightarrow f_2)\subseteq 1\& (\overline{y+f_1}\vee\overline{y+f_2}\subseteq 1)  $$ параметрически выражает отношение $y\subseteq f(\tilde x)$.
\end{proof}


\begin{lemma}
	Мультиоперации $(01)$, $(--)$ и $(\ast\ast)$ содержатся в каждом параметрически замкнутом классе мультиопераций.
	\label{lemma1}
\end{lemma}
\begin{proof}
	Действительно, формула $y\subseteq x$ определяет отношение $y \subseteq (01)$, любая тождественно истинная параметрическая формула, например 
	$
	x \subseteq x \;\&\; y\subseteq y,
	$ 
	определяет отношение $y \subseteq (--)$~\cite{R2016ISU}, а формула $(--)(x)\subseteq y$   определяет отношение $y \subseteq (\ast\ast)$.
\end{proof}

\begin{lemma}[\cite{R2016ISU}]
	Каждая гипероперация из множества $\{(0-)$,$(-1)$, $(-0)$, $(1-)\}$ параметрически полна в множестве~$\mathcal{H}$.
	\label{lemma2} 
\end{lemma}

\begin{lemma}
	Любая мультиоперация из множеств $A=\{(0\ast)$,$(1\ast)$,$(-\ast)$, $(\ast0)$, $(\ast1)$, $(\ast-)\}$ или $B=\{(00), (11)\}$ параметрически полна в множестве~$\mathcal{M}$.
	\label{lemma3}
\end{lemma}

\begin{proof}
	Как известно, множество $\mathcal{H}\cup\{\ast\}$ является предполным в $\mathcal{M}$~\cite{Pant2005}. Операции из множества $A$ не принадлежат множеству $\mathcal{H}$,  поэтому для доказательства леммы достаточно получить операции из леммы \ref{lemma2}.
	
	
	Рассмотрим формулу $f(x)\subseteq f(y)$. Для первых трех мультиопераций из множества $A$ она становится истинной в следующих случаях: если $x=0$, то $y$ может быть равным только 0, а если $x=1$, то $y$ может быть равным и 0 и 1. Это означает, что формула $f(x)\subseteq f(y)$ определяет отношение $y\subseteq (0-)$.
	
	Для оставшихся мультиопераций из $A$
	рассматриваемая формула принимает истинное значение в следующих случаях: если $x=0$, то $y$ может быть равным и 0 и 1, а если $x=1$, то $y$ может быть равным только 1, т.\,е. формула $f(x)\subseteq f(y)$ определяет отношение $y\subseteq (-1)$.
	
	
	Аналогичным образом убеждаемся,  что формула $x\subseteq f(y)$ определяет отношение $y\subseteq (-\ast)$ для $f=(00)$ и  $y\subseteq (\ast-)$ для  $f=(11)$.
\end{proof}

\begin{lemma}
	Мультиоперация $(0001)$ параметрически полна в классе~$\mathcal{M}$.%
	\label{lemma4}
\end{lemma}
\begin{proof}
	Пусть $f(x_1,x_2)=(0001)$. Тогда формула $f(x_1,x_2)\subseteq f(x_1,y)$ задает отношение $y\subseteq (--01)$ и, соответственно, операцию $f_2=(--01)$.
	
	Формула $f_2(x_1,x_2)\subseteq f(x_1,y)$ задает отношение $y\subseteq (\ast\ast01)$.
	Отождествление переменных у операции $(\ast\ast01)$ позволяет получить операцию $(\ast1)$, которая параметрически полна по лемме \ref{lemma3}.
\end{proof}

\begin{lemma}
	Справедливо $(10)\in\mathrm{Par}\big[\{(01),(--),(\ast\ast)\}\big].$%
	\label{lemma5}
\end{lemma}
\begin{proof}
	Пусть $f=(0101)$. Тогда формула $f(x_1,x_2)\subseteq f(y,x_1)$ определяет операцию $(-\ast\ast-)=g$. Формула $g(x_1,x_2)\subseteq f(x_1,y)$ определяет операцию $(\ast--\ast)=h$, а $h(x_1,x_2)\subseteq g(x_1,y)$ определяет операцию $u=(-01-)$.
	Наконец, формула $u(x_1,x_2)\subseteq h(x_1,y)$ определяет операцию~$(10)$.
\end{proof}

Введем в рассмотрение мультиоперацию $d_3(x_1, x_2, x_3) = (00010111)$.

\begin{lemma}
	Справедливо $d_3\in \mathrm{Par}\big[\{(01),(--),(\ast\ast),(10)\}\big].$
	\label{lemma6}
\end{lemma}
\begin{proof}
	В лемме \ref{lemma5} рассматривались операции  $f,g,h,u$. Из операции $u=(-01-)$ несложно получить операцию $u_1=(-10-)$. Формула $u(x_1,x_2)\subseteq u(x_1,y)$ определяет операцию $v=(0--1)$, а формула $v(x_1,x_2)\subseteq f(x_1,y)$ определяет операцию $w=(0\ast\ast1)$.
	
	Построим операции $f_1(x,y,z)=f(y,z)$ и $h_1(x,y,z)= h(x,y)$.
	
	Рассмотрим суперпозицию с внешней операцией $f_1(x,y,z)$ и внутренними операциями $h_1, x, z$. Обозначим $f_2(x,y,z) = s(f_1,h_1,x,z)(x,y,z)$. Тогда $f_2(x,y,z)=(\ast\ast0101\ast\ast)$, а формула $f_2(x_1,x_2,x_3)\subseteq f_1(x_1,x_2,y)$ определяет, соответственно, операцию $f_3=(--0101--)$.
	
	Построим операции $w_1(x,y,z)=w(y,z)$ и $u_{11}(x,y,z)=u_1(y,z)$.
	
	Тогда $s(w_1,x_2,x_1,u_{11})(x_1,x_2,x_3)$ задает операцию $(0\ast0011\ast1)$. Применяя отрицание, можно получить операцию $f_4=(\ast000111\ast).$
	Далее строим суперпозицию 
	$s(f_1,f_4,x_2,x_3)(x_1,x_2,x_3) =(\ast101010\ast)=f_5.$
	
	Формула $f_5(x_1,x_2,x_3)\subseteq f_1(x_1,x_2,y)$ позволяет определить операцию $f_6=(-101010-)$.
	И, наконец, формула $f_3(x_1,x_2,x_3)\subseteq f_6(x_1,x_2,y)$ определяет отношение $y\subseteq d_3(x_1,x_2,x_3)$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

Через $S^{-\ast}$ обозначим  множество мультиопераций, которые на любой паре противоположных наборов возвращают либо противоположные значения $(0,1)$ и $(1,0)$, либо два прочерка $(-,-)$, либо $(\ast,\ast)$.

\begin{lemma} 
	Класс $S^{-\ast}$ является параметрически замкнутым.%
	\label{lemma7}
\end{lemma}
\begin{proof}
	Пусть параметрическая формула $\Phi(\tilde{x},y)$ получена с помощью мультиопераций $g_1, \ldots, g_k$ из класса $S^{-\ast}$. Покажем, что такая формула будет представлять отношение $y \subseteq f(\tilde{x})$, где мультиоперация $f(\tilde{x})$ также принадлежит классу $S^{-\ast}$. 
	
	Для этого покажем, что таблица истинности формулы $\Phi$ является симметричной, т.е. на противоположных наборах формула принимает одинаковые истинностные значения, а именно 
	$$
	\Phi(\tilde{x},y) = \Phi(\overline{\tilde{x}}, \overline{y})
	$$
	для любого набора $\tilde{x} \in E_2^n, y \in E_2$.
	Доказательство будем проводить индукцией по построению формулы $\Phi$.
	
	Базис индукции. Рассмотрим элементарную параметрическую формулу
	\begin{equation}
		\Phi(x_1,\ldots, x_n, y) = g_1(z_1,\ldots, z_p) \subseteq g_2(w_1,\ldots, w_q),
		\label{eq-lemma7}
	\end{equation}
	где $\{z_1,\ldots, z_p\} \subseteq \{x_1, \ldots, x_n, y\}$, $\{w_1,\ldots, w_q \} \subseteq \{x_1, \ldots, x_n, y\}$ и $g_1, g_2 \in S^{-\ast}$.
	Построим для этой формулы таблицу истинности и определим истинность формулы на произвольном наборе $\{\alpha_1, \ldots, \alpha_n, \alpha_0\}$ и его отрицании. Для этого на указанном наборе рассмотрим возможные значения мультиопераций $g_1, g_2$. Для упрощения записи будем считать, что 
	$$
	\Phi(\alpha_1,\ldots, \alpha_n, \alpha_0) = g_1(\beta_1,\ldots, \beta_p) \subseteq g_2(\gamma_1,\ldots, \gamma_q),
	$$ 
	где $\{\beta_1,\ldots, \beta_p\}\subseteq \{\alpha_1, \ldots, \alpha_n, \alpha_0\}$ и $\{\gamma_1,\ldots, \gamma_q \} \subseteq \{\alpha_1, \ldots, \alpha_n, \alpha_0\}.$
	
	1.~Пусть $g_1(\beta_1,\ldots, \beta_p) = a,$ где $a \in E_2.$ Рассмотрим возможные значения мультиоперации $g_2.$ Если $g_2(\gamma_1,\ldots, \gamma_q)$ тоже принимает значение $a$, то в силу того, что $g_1, g_2 \in S^{-\ast}$, получим 
	$g_1(\overline{\beta}_1,\ldots, \overline{\beta}_p) = \overline{a}$ и 
	$g_2(\overline{\gamma}_1,\ldots, \overline{\gamma}_q) = \overline{a}.$ В этом случае $\Phi(\tilde{\alpha},\alpha_0) = \Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0)= \text{И}$. 
	
	Если $g_2(\gamma_1,\ldots, \gamma_q)=\overline{a}$, то 
	$g_1(\overline{\beta}_1,\ldots, \overline{\beta}_p) = \overline{a}$ и 
	$g_2(\overline{\gamma}_1,\ldots, \overline{\gamma}_q) = a.$ Тогда $\Phi(\tilde{\alpha},\alpha_0) = \Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0)= \text{Л}$. 
	
	Если $g_2(\gamma_1,\ldots, \gamma_q)=-$, то $g_2(\overline{\gamma}_1,\ldots, \overline{\gamma}_q)=-$. 
	Тогда формулы $a \subseteq -$ и $\overline{a} \subseteq -$ истинны и 	
	$$
	\Phi(\tilde{\alpha},\alpha_0) = \text{И},\;\; 
	\Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0) = \text{И}.
	$$
	
	А если $g_2(\gamma_1,\ldots, \gamma_q)=\ast$, то $g_2(\overline{\gamma}_1,\ldots, \overline{\gamma}_q)=\ast$. 
	Тогда формулы $a \subseteq \ast$ и $\overline{a} \subseteq \ast$ ложны и 	
	$$
	\Phi(\tilde{\alpha},\alpha_0) = \text{Л},\;\; 
	\Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0) = \text{Л}.
	$$	
	
	2.~Пусть $g_1(\beta_1,\ldots, \beta_p) = -.$ Если $g_2(\gamma_1,\ldots, \gamma_q) \in E_2$ или возвращает~$\ast$, то формула $\Phi(\tilde{\alpha},\alpha_0)$ ложна и $\Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0)$ также ложна. 
	
	Если $g_2(\gamma_1,\ldots, \gamma_q)=-$, то $\Phi(\tilde{\alpha},\alpha_0)$ истинна и $\Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0)$ истинна. 
		
	3.~Пусть $g_1(\beta_1,\ldots, \beta_p) = \ast.$ В этом случае формула  $\Phi(\tilde{\alpha},\alpha_0)$ истинна и $\Phi(\overline{\tilde{\alpha}},\overline{\alpha}_0)$ также истинна. 
		
	Следовательно, формула вида (\ref{eq-lemma7}) на противоположных наборах принимает одинаковые истинностные значения.
	
	Шаг индукции. Рассмотрим параметрическую формулу вида $\Phi_1 \& \Phi_2$. В силу индуктивного предположения формулы $\Phi_1, \Phi_2$ на противоположных наборах принимают одинаковые истинностные значения. Следовательно, рассматриваемая формула на противоположных наборах также принимает одинаковые значения.	
	
	При рассмотрении формулы вида $\exists x_1 \Phi_1$ воспользуется очевидным фактом, что истинность формул 
	$$\exists x_1 \Phi_1(x_1, \overline{x}_2, \dots, \overline{x}_n, \overline{y}), \quad 
	\exists x_1 \Phi_1(\overline{x}_1, \overline{x}_2, \dots, \overline{x}_n, \overline{y})$$
	совпадает. 
		
	Таким образом, если параметрическая формула $\Phi(\tilde{x},y)$ получена с помощью мультиопераций $g_1, \ldots, g_k \in S^{-\ast}$ и представляет отношение $y \subseteq f(\tilde{x})$, то операция $f(\tilde{x})$ также принадлежит классу $S^{-\ast}.$    
\end{proof}

\begin{lemma}
	Любую мультиоперацию из класса $S^{-\ast}$ можно параметрически выразить с помощью операции $d_3$, т.е. $\mathrm{Par}\big[\{d_3\}\big]=S^{-\ast}.$
	\label{lemma8}
\end{lemma}
\begin{proof}
	Пусть $f(x_1, \ldots, x_n)\in S^{-\ast} $. С использованием операции $d_3$ построим параметрическую формулу $\Phi(\tilde{x},y)$ для представления операции $f$. 
	
	Заметим, что $d_3(0,x_2,x_3) = (0001)$. Таким образом, согласно лемме~\ref{lemma4} операция $d_3(0,x_2,x_3)$ позволяет получить любую мультиоперацию из класса $\mathcal{M}$. Построим с ее помощью  формулу $\Psi(x_2,\ldots, x_n,y)$ представляющую отношение $y \subseteq f(0,x_2,\ldots,x_n)$. 
	
	Теперь положим, что $\Phi(0,x_2,\ldots,x_n,y) = \Psi(x_2,\ldots, x_n,y)$ и заменим все вхождения $0$ на переменную $x_1$. Формула  $\Phi(x_1,x_2,\ldots,x_n,y)$ построена из операции $d_3$, принадлежащей множеству $S^{-\ast}$. Поэтому такая формула на противоположных наборах принимает одинаковые истинностные значения, и, значит, определяет операцию из класса  $S^{-\ast}$. С учетом того, что на наборах $(0,x_2,\ldots,x_n,y)$ истинностное значение формулы $\Phi$ совпадает с истинностным значением отношения  $y \subseteq f(0,x_2,\ldots,x_n)$, получаем, что на наборах $(x_1,x_2,\ldots,x_n,y)$ истинностное значение формулы~$\Phi(x_1,x_2,\ldots,x_n,y)$ совпадает с истинностным значением отношения $y \subseteq f(x_1,x_2,\ldots,x_n)$. 
\end{proof}

\begin{corollary}
	$S^{-\ast}=\mathrm{Par}[\varnothing].$
\end{corollary}
Действительно, согласно леммам \ref{lemma1} и \ref{lemma5} мультиоперации $(01)$, $(--)$, $(\ast\ast)$ и $(10)$ содержатся в каждом параметрически замкнутом классе мультиопераций. Лемма~\ref{lemma6} показывает, что с использованием этих мультиопераций мы можем получить мультиоперацию $d_3$. Далее воспользуемся леммой~\ref{lemma8}.   

\begin{theorem}
	Множество мультиопераций $B$ параметрически полно тогда и только тогда, когда $B$ не содержится в множестве $S^{-\ast}$.
\end{theorem}
\begin{proof}
	Так как $B$ не содержится в множестве $S^{-\ast}$, то существует операция $f(x_1,\ldots,x_n)$, которая на некоторой паре противоположных наборов дает следующие возможные пары значений:
	$(00),(0\ast),(0-),$ $(11),(1\ast),(1-),(\ast1),(\ast0),$ $(\ast-),(-0),(-1),(-\ast).$
	
	Противоположным наборам соответствуют операции $(01)$ и $(10)$, которые есть в каждом параметрически замкнутом классе. Подставляя эти операции в качестве внутренних операций в суперпозицию с внешней мультиоперацией $f$ вместо соответствующих переменных $x_1,\ldots,x_n$, будем получать либо полное множество, либо одну из операций $$(0-),(-0),(-1), (1-). $$
	
	С учетом имеющейся операции отрицания достаточно рассмотреть случай получения операции $f(x)=(0-)$. 
	Формула $f(x)\subseteq f(y)$ определяет операцию $g(x)=(-1)$. А формула  
	$f(x)\subseteq g(y)$ операцию $h(x)=(00)$.
\end{proof}
	
\begin{corollary}
	Множество $\mathcal{M}$ содержит два параметрически замкнутых класса --- $S^{-\ast}$ и $\mathcal{M}$.
\end{corollary}
	


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

\bibitem{B1987} S. Barris, R. Willard, \href{https://doi.org/10.1090/S0002-9939-1987-0908642-5}{\it Finitely many primitive positive clones}, Proc. Amer. Math. Soc., \textbf{101}:3 (1987), 427--430.

\bibitem{D1977}  A.F. Danil’chenko, \href{https://doi.org/10.1007/BF01669278}{\it Parametric expressibility of functions of three-valued logic}, Algebra and Logic, \textbf{16} (1977), 266--280.

\bibitem{D1978} A.F. Danil’chenko, {\it Parametrically closed classes of functions of three-valued logic}, Izvestiya AN MSSR, \textbf{2} (1978), 13--20.

\bibitem{K1979} A.V. Kuznecov, {\it Means for detection of nondeducibility and inexpressibility}, Logical Inference, Nauka, Moscow, 1979, 5--33. 

\bibitem{R2016}	L.V. Riabets, \href{http://mi.mathnet.ru/ista93}{\it Operators of parametric and positive closure on the set of hyperfunctions of rank 2}, Intelligent systems. Theory and applications, \textbf{20}:3 (2016), 79--84.

\bibitem{R2016ISU} L.V. Riabets, \href{http://mi.mathnet.ru/iigum272}{\it Parametric closed classes of hyperfunctions of rank 2}, Bulletin of Irkutsk State University. Series Mathematics, \textbf{17} (2016), 46--61.

\bibitem{Pan2021} V.I. Panteleev, E.S. Taglasov, \href{http://mi.mathnet.ru/ista303}{\it $ES_I$-closure of rank 2 multifunctions: completeness criterion, classification, and types of bases}, Intelligent systems. Theory and applications, \textbf{25}:2 (2021), 55--80.

\bibitem{lo-1988} Lo Czu Kai, {\it Maximal closed classes on the set of partial
many-valued logic}, Kiberneticheskiy Sbornik, \textbf{25} (1988), 131–-141. 

\bibitem{lo-1988b} Lo Czu Kai, {\it Completeness theory on partial many-valued logic functions},
Kiberneticheskiy Sbornik, \textbf{25} (1988), 142-157.

\bibitem{M2000} S.S. Marchenkov, {\it Closed classes of Boolean functions}, Nauka, Fizmatlit., Moscow, 2000.

\bibitem{M1999} S.S. Marchenkov, \href{https://doi.org/10.4213/dm400}{\it On the expressibility of functions of many-valued logic in some logical-functional classes}, Discrete Math. Appl., \textbf{4} (1999), 110--126.

\bibitem{M2014} S.S. Marchenkov, \href{https://doi.org/10.1134/S1990478914020124}{\it Positive closed classes of three-valued logic}, J. Appl. Indust. Math., \textbf{8}:2 (2014), 256--266.

\bibitem{M2008} S.S. Marchenkov, A.A. Popova, \href{https://doi.org/10.3103/S0278641908030059}{\it Positively closed classes of partial Boolean functions}, Mosc.
Univ. Comput. Math. Cybern., \textbf{32} (2008), 147--151. 

\bibitem{R2014} V.I. Panteleev, L.V.Riabets, \href{http://mi.mathnet.ru/iigum211}{\it The closure operator with the equality predicate branching on the set of hyperfunctions on two-element set}, The Bulletin
of Irkutsk State University. Series Mathematics, \textbf{10} (2014), 93--105. 

\bibitem{T1975}V.V. Tarasov, {\it Completeness criterion for partial logic functions}, Problemy Kibernetiki, Nauka, Moscow, \textbf{30} (1975), 319--325.

\bibitem{Sha2023} I.K. Sharankhaev, \href{DOI 10.33048/semi.2023.20.079}{ \it On positive completeness and positively closed sets of multifunctions of rank 2}, Siberian Electronic Mathematical Reports, \textbf{20}:2 (2023), 1313--1319.

\bibitem{Pant2005}
R. Doroslova$\check{\text{c}}$ki,  J. Pantovi$\acute{\text{c}}$, 
G. Vojvodi$\acute{\text{c}}$, \href{https://doi.org/10.1007/s10587-005-0059-0}{\it One interval in the lattice of partial hyperclones}, Czech Math J., \textbf{55} (2005), 719--724.

\bibitem{Pouza2010}M. Pouzet, I.G. Rosenberg,  \href{https://doi.org/10.1007/s00012-010-0063-6}{Small clones and the projection property}. Algebra Univers. 63, 37–44 (2010). 

\bibitem{Mach2002} H. Machida, {\it Hyperclones on a two-element set}, Multiple-Valued Logic. An International Journal, \textbf{8}:4 (2002), 495--501.

\bibitem{MachPant2008} H. Machida, J. Pantovi$\acute{\text{c}}$, \href{https://doi.org/10.1109/ISMVL.2008.44}{\it On maximal hyperclones on $\{0, 1\}$ – a	new approach}, Proc. of 38th IEEE International Symposium on Multiple-Valued Logic (ismvl 2008), (2008), 32--37.

\bibitem{Rom1998} B.A. Romov, \href{https://doi.org/10.1109/ISMVL.1997.601378}{\it Hyperclones on a finite set}, Proc. of 27th International Symposium on Multiple-Valued Logic, (1997), 83--88.

\bibitem{Frei1998}  R.V. Freiwald, \href{http://mi.mathnet.ru/dan32237}{ \it Completeness criterion of partial Boolean functons and multiple-valued logic}, DAN USSR, \textbf{167}:6 (1966), 1249–1250.
\end{thebibliography}
\end{document}
