
\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}

\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{Sergei Alexandrovich Badmaev, Alexandr Evgenevich Dugarov, Irina Vladimirovna Fomina, 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{badmaevsa@mail.ru, dugarov\_aleksandr@mail.ru, fomina-irina0104@yandex.ru, goran5@mail.ru}%

\thanks{\sc Badmaev, S.A., Dugarov, A.E., Fomina, I.V., Sharankhaev, I.K.
On some intervals in the lattice of ultraclones of rank 2}
\thanks{\copyright \ 2021 Бадмаев С.А., Дугаров А.Е., Фомина И.В., Шаранхаев И.К.}
\thanks{\rm Работа поддержана грантом Бурятского государственного университета им. Доржи Банзарова}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2015 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } In article the intervals in the lattice of ultraclones of rank 2 are considered. The well-known classes of all monotone $M$, all self-dual $S$ and all linear $L$ Boolean functions are ultraclones of rank 2. We proved that each of the intervals $\Im (M, H_2)$, $\Im (S, H_2)$, $\Im(L, H_2)$, where $H_2$ is complete ultraclone of rank 2, contains exactly 4 elements.\medskip

\noindent{\bf Keywords:} hyperfunction, Boolean function, monotone function, self-dual function, linear function, superposition, closed set, clone, ultraclone, lattice, interval of lattice.
 \end{quote}
}


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

В теории функций \emph{k}-значной логики одно из основных направлений исследований связано с подмножествами функций, замкнутыми относительно суперпозиции. Традиционной задачей здесь является описание решетки замкнутых классов или клонов функций. Первые результаты в этом направлении были получены американским математиком Э. Постом \cite{Post}, который полностью описал решетку замкнутых классов булевых функций.
Результаты, полученные в двузначной логике, способствовали дальнейшему развитию исследований теории функций \emph{k}-значной логики. При этом выделяются два направления: первое связано с увеличением мощности основного множества, второе – с рассмотрением функций, которые определены не на всех наборах. Не всюду определенные функции удобно рассматривать как отображения из декартовой степени \emph{k}-элементного множества \emph{A} во множество всех его подмножеств, причем одноэлементные подмножества отождествляются с элементами \emph{A}, а остальные подмножества понимаются как неопределенности. Очевидно, что суперпозиция в обычном смысле для работы с этими функциями не подходит. Существует несколько способов расширения суперпозиции, каждый из которых позволяет находить значения суперпозиции на наборах с неопределенностями. В зависимости от вида и числа неопределенностей, а также измененной суперпозиции их называют частичными, недоопределенными, доопределяемыми, гиперфункциями, мультифункциями. Такие функции возникают при изучении многозначных логик, решении функциональных уравнений, моделировании схем с неисправностями. Естественно, что и для них также ставится задача описания решетки замкнутых классов. В связи с тем, что полное решение этой задачи вызывает определенные трудности, исследуются отдельные фрагменты решетки, различные интервалы. Отметим, что некоторые интервалы в решетке ультраклонов ранга 2 описаны в работах \cite{PanteleyevHaltanova, Haltanova}.

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

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

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

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

Функции из $O_2$ называют булевыми функциями, а из $H_2$ -- гиперфункциями на $E$. Очевидно, что $O_2\subset H_2.$

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

$$g(\alpha_1, \dots, \alpha_m)=\left\{
\begin{array}{ll}
	\bigcap \limits_{\beta_i \in f_i(\alpha_1, \dots, \alpha_m)}f(\beta_1, \dots, \beta_n), & \mbox{если пересечение не пусто};\\
	\bigcup \limits_{\beta_i \in f_i(\alpha_1, \dots, \alpha_m)} f(\beta_1, \dots, \beta_n), & \mbox{в противном случае. }
\end{array} \right.$$

Далее гиперфункцию будем называть просто функцией, если это не вызывает недоразумений.

Для любого натурального $n$ и любого $i$, где $1 \leq i  \leq n$, обозначим через $e_i^n(x_1,\dots, x_i,\dots, x_n)$  функцию, значения которой совпадают со значениями переменной $x_i$. Функции $e^n_i$ называются проекциями или селекторными функциями.

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

Ультраклоном ранга 2 (клоном) называется замкнутое множество функций (булевых функций), содержащее все проекции. Множество всех функций $H_2$ называется полным ультраклоном ранга 2. Далее для краткости любой ультраклон ранга 2 будем называть просто ультраклоном. Заметим, что любой клон является  ультраклоном.

Ультраклон $K$ называется максимальным, если не существует ультраклона $K_1$ такого, что $K \subset K_1 \subset H_2$.

Интервалом $\Im(Q,R)$ называется частично упорядоченное по включению множество всех ультраклонов, в котором любой элемент $K$ удовлетворяет условиям $Q \subseteq K$ и $K \subseteq R$. Интервалы для наглядности изображаются в виде диаграмм, где ультраклоны обозначены точками, а точка, представляющая $Q_1$, расположена выше и соединена отрезком с точкой, представляющей $R_1$, если $R_1 \subset Q_1$ и не существует ультраклона $P$ такого, что $R_1 \subset P \subset Q_1$.

Через $M$ обозначим клон всех булевых монотонных функций, $S$ -- клон всех булевых самодвойственных функций, $L$ -- клон всех булевых линейных функций.

Пусть $R^s$ -- $s$-местный предикат, заданный на множестве $F$. Будем говорить, что функция $f(x_1, \dots, x_n)$, определенная на множестве $F$, сохраняет предикат $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$.

Для набора $(\alpha_1, \dots, \alpha_n) \in F^n$ набор $(\beta_1, \dots, \beta_n) \in \{0, 1\}^n$, где $\beta_i \leq \alpha_i$ для всех $i \in \{1, \dots, n\}$, называется  уточнением.

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

Константную функцию, принимающую на всех наборах значение $-$, обозначим через $f^-$, а через $d_3$ -- трехместную функцию с вектором значений $(00010111)$.

В \cite{Panteleyev2009} доказано, что максимальными ультраклонами ранга 2 являются только следующие 11 множеств:

1) $O_2$ -- множество всех булевых функций;

2) $T_0^{-}$ -- множество функций, которые сохраняют нуль, т. е. на наборе из всех нулей функции принимают значение $0$;

3) $T_1^{-}$ -- множество функций, которые сохраняют единицу, т. е. на наборе из всех единиц функции принимают значение $1$;

4) $S^-$ -- множество функций, сохраняющих предикат

$$R_S=\begin{pmatrix}
	0 & 1 & - \\
	1 & 0 & -
\end{pmatrix};$$

5) $L^-$ -- множество функций, сохраняющих предикат

$$R_L=\begin{pmatrix}
	0 & 0 & 1 & 1 & - \\
	0 & 1 & 0 & 1 & -
\end{pmatrix};$$

6) $M^-$ -- множество функций, сохраняющих предикат

$$R_M=\begin{pmatrix}
	0 & 0 & 1 & 0 & - & - \\
	0 & 1 & 1 & - & 1 & -
\end{pmatrix};$$

7) $K_1$ -- множество функций, сохраняющих предикат

$$R_1=\begin{pmatrix}
	0 & 1 & 1 & - & 1 & - \\
	1 & 0 & 1 & 1 & - & -
\end{pmatrix};$$

8) $K_2$ -- множество функций, сохраняющих предикат

$$R_2=\begin{pmatrix}
	0 & 0 & 1 & 0 & - & - \\
	0 & 1 & 0 & - & 0 & -
\end{pmatrix};$$

9) $K_3$ -- множество функций, сохраняющих предикат $R_3$, определяемый матрицей

$$\begin{pmatrix}
	0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & - & - & 0 & 1 & - & - & 1 & 1 & - & - \\
	0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & - & 1 & - & 0 & 1 & - & - & 1 & - & 1 & - & 1 & - \\
	0 & 1 & 0 & 1 & 1 & 0 & 1 & - & 0 & - & 1 & 1 & 0 & - & - & - & 1 & - & 1 & 1 & -
\end{pmatrix};$$

10) $K_4$ -- множество функций, сохраняющих предикат

$$R_4=\begin{pmatrix}
	0 & 0 & 0 & 1 & 0 & 0 & - & 0 & - & - & - \\
	0 & 0 & 1 & 1 & 0 & - & 0 & - & 0 & - & - \\
	0 & 1 & 0 & 1 & - & 0 & 0 & - & - & 0 & -
\end{pmatrix};$$

11) $K_5$ -- множество, состоящее из всех функций, существенно зависящих не более чем от одной переменной, а также из функций, принимающих два значения, одно из которых есть $-$.

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



\begin{lemma}
Из 11 максимальных ультраклонов ранга 2 только $O_2$ и $M^-$ содержат $M$.
\end{lemma}

\begin{proof}
Методом от противного покажем, что $M\subset M^-$. Пусть найдутся функция $f(x_1,\dots,x_n)$ и наборы $\tilde{\alpha}=(\alpha_1,\dots,\alpha_n)$ и $\tilde{\beta}=(\beta_1,\dots,\beta_n)$ такие, что $f\in M$, $f\begin{pmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ - \end{pmatrix}, \begin{pmatrix}  - \\ 0 \end{pmatrix}\end{Bmatrix}$  и $\begin{pmatrix} \alpha_i \\ \beta_i \end{pmatrix}\in R_M$  для всех $i\in\{1,\dots,n\}$. Если $f\begin{pmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ - \end{pmatrix}\end{Bmatrix}$, то для набора $\tilde{\beta}$  возьмем уточнение $\tilde{\tau}$, которое обязательно найдется, поскольку $f\in O_2$  и  $f(\tilde{\beta})\in \{0,-\}$, такое, что  $f(\tilde{\tau})=0$, а для набора $\tilde{\alpha}$  выберем уточнение $\tilde{\delta}$  так, чтобы  $\begin{pmatrix} \delta_i \\ \tau_i \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ 0 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \end{pmatrix}\end{Bmatrix}$  для всех  $i\in\{1,\dots,n\}$. Нетрудно заметить, что булева функция $f$  на любом уточнении набора $\tilde{\alpha}$  принимает значение $1$. Тогда  $f\begin{pmatrix} \tilde{\delta} \\ \tilde{\tau} \end{pmatrix}=\begin{pmatrix}  1 \\ 0 \end{pmatrix}$, что противоречит  $f\in M$. Если  $f\begin{pmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{pmatrix}=\begin{pmatrix}  - \\ 0 \end{pmatrix}$, то для набора $\tilde{\alpha}$   выберем уточнение  $\tilde{\delta}$  такое, что  $f(\tilde{\delta})=1$, а для набора $\tilde{\beta}$  возьмем уточнение $\tilde{\tau}$  так, чтобы  $\begin{pmatrix} \delta_i \\ \tau_i \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ 0 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \end{pmatrix}\end{Bmatrix}$  для всех  $i\in\{1,\dots,n\}$. Тогда $f\begin{pmatrix} \tilde{\delta} \\ \tilde{\tau} \end{pmatrix}=\begin{pmatrix}  1 \\ 0 \end{pmatrix}$, что противоречит  $f\in M$.

Очевидно, что $M \subset O_2$. Далее справедливость леммы следует из того, что константа $1$ не принадлежит $T_0^{-}$, константа 0 не принадлежит $T_1^{-}$, конъюнкция не принадлежит $S^-$, $L^-$,  $K_1$,  $K_3$, $K_5$, дизъюнкция не принадлежит $K_2$, $K_4$.
\end{proof}

\begin{corollary} Верно, что
$O_2\cap M^- = M$.
\end{corollary}

\begin{proof}
Заметим, что $M$ в точности совпадает с множеством булевых функций, сохраняющих предикат
$\begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 1
\end{pmatrix}$ (см., например, \cite{Marchenkov}). Тогда, очевидно, что для любой $f\in M^-$ и любых двоичных наборов $\tilde{\alpha}$ и $\tilde{\beta}$ таких, что $\tilde{\alpha}\leq\tilde{\beta}$ и $f(\tilde{\alpha}), f(\tilde{\beta})\in \{0,1\}$ выполняется $f(\tilde{\alpha})\leq f(\tilde{\beta})$. Отсюда следует, что $O_2\cap M^- \subseteq M$. В обратную сторону включение верно в силу леммы 1.
\end{proof}

\begin{lemma}
Для любой $f\in M^-\setminus M$  справедливо  $M^-=[M\cup \{f\}]$.
\end{lemma}

\begin{proof}
Включение $[M\cup \{f\}]\subseteq M^-$  очевидно. Покажем, что любая гиперфункция  $g(x_1,\dots,x_n)\in M^-$  может быть выражена с помощью суперпозиции монотонных булевых функций и $f\in M^-\setminus M$. В силу следствия 1 достаточно рассмотреть случай, когда  $g(x_1,\dots,x_n)\in M^-\setminus M$.

Обозначим через $\tilde{\alpha}_1,\dots,\tilde{\alpha}_s$  наборы, на которых значение гиперфункции $g$  равно $0$, через $\tilde{\beta}_1,\dots,\tilde{\beta}_l$ -- наборы, на которых значение гиперфункции   равно $1$, а через $\tilde{\gamma}_1,\dots,\tilde{\gamma}_t$ -- наборы, на которых значение гиперфункции   равно $-$. Заметим, что для любых наборов  $\tilde{\alpha}_i$,  $\tilde{\beta}_j$,  $\tilde{\gamma}_k$, где  $i\in\{1,\dots,s\}$,  $j\in\{1,\dots,l\}$,  $k\in\{1,\dots,t\}$, либо  $\tilde{\alpha}_i\leq\tilde{\beta}_j$,  $\tilde{\gamma}_k\leq\tilde{\beta}_j$, либо эти наборы не находятся в отношении предшествования. Иначе получим, что $g\begin{pmatrix} \tilde{\beta}_j \\ \tilde{\alpha}_j \end{pmatrix}=\begin{pmatrix}  1 \\ 0 \end{pmatrix}$  и  $g\begin{pmatrix} \tilde{\beta}_j \\ \tilde{\gamma}_k \end{pmatrix}=\begin{pmatrix}  1 \\ - \end{pmatrix}$, что противоречит  $g\in M^-$.

С помощью гиперфункции $f$  и констант $0$, $1$ получим константную гиперфункцию  $f^-$. Далее выберем монотонную функцию $\phi(x_1,\dots,x_m,y)$  такую, что  $\phi(\tilde{\alpha}_i,0)=0$,  $\phi(\tilde{\beta}_j,0)=1$,  $\phi(\tilde{\gamma}_k,0)=0$,  $\phi(\tilde{\alpha}_i,1)=0$,  $\phi(\tilde{\beta}_j,1)=1$,  $\phi(\tilde{\gamma}_k,1)=1$, где  $i\in\{1,\dots,s\}$,  $j\in\{1,\dots,l\}$,  $k\in\{1,\dots,t\}$.

Покажем, что  $\phi(x_1,\dots,x_m,f^-(x_m))=g(x_1,\dots,x_m)$. Действительно,
$$\phi(\tilde{\alpha}_i,-)=\phi(\tilde{\alpha}_i,0)\cap \phi(\tilde{\alpha}_i,1)=0=g(\tilde{\alpha}_i),$$
$$\phi(\tilde{\beta}_j,-)=\phi(\tilde{\beta}_j,0)\cap \phi(\tilde{\beta}_j,1)=1=g(\tilde{\beta}_j),$$
$$\phi(\tilde{\gamma}_k,-)=\phi(\tilde{\gamma}_k,0)\cup \phi(\tilde{\gamma}_k,1)=-=g(\tilde{\gamma}_k),$$
где  $i\in\{1,\dots,s\}$,  $j\in\{1,\dots,l\}$,  $k\in\{1,\dots,t\}$.

Следовательно,  $M^-\subseteq [M\cup \{f\}]$.
\end{proof}

\begin{corollary} Верно, что
$M^- = [\{0,1,\vee,\wedge,f^-\}]$.
\end{corollary}

\begin{proof} Следует из $M=[\{0,1,\vee,\wedge\}]$  (см., например, \cite{Marchenkov}).
\end{proof}


\begin{lemma}
Из 11 максимальных ультраклонов ранга 2 только $O_2$ и $S^-$ содержат $S$.
\end{lemma}

\begin{proof}
Методом от противного покажем, что $S\subset S^-$. Пусть найдутся функция $f(x_1,\dots,x_n)$ и набор $\tilde{\alpha}=(\alpha_1,\dots,\alpha_n)$ такие, что $f\in S$, $f\begin{pmatrix} \tilde{\alpha} \\ \bar{\tilde{\alpha}} \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \end{pmatrix}, \begin{pmatrix}  0 \\ - \end{pmatrix}, \begin{pmatrix}  - \\ 0 \end{pmatrix}, \begin{pmatrix}  - \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ - \end{pmatrix}\end{Bmatrix}$  и $\begin{pmatrix} \alpha_i \\ \bar{\alpha}_i \end{pmatrix}\in R_M$  для всех $i\in\{1,\dots,n\}$. Если $f\begin{pmatrix} \tilde{\alpha} \\ \bar{\tilde{\alpha}} \end{pmatrix}=\begin{pmatrix}  c \\ c \end{pmatrix}$, где $c\in \{0,1\}$, то для набора $\tilde{\alpha}$  возьмем уточнение $\tilde{\delta}$, такое, что  $f(\tilde{\delta})=c$, а для набора $\bar{\tilde{\alpha}}$  выберем уточнение $\tilde{\tau}$  так, чтобы  $\begin{pmatrix} \delta_i \\ \tau_i \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \end{pmatrix}\end{Bmatrix}$  для всех  $i\in\{1,\dots,n\}$. Нетрудно заметить, что булева функция $f$  на любом уточнении набора $\bar{\tilde{\alpha}}$  принимает значение $c$. Тогда  $f\begin{pmatrix} \tilde{\delta} \\ \tilde{\tau} \end{pmatrix}=\begin{pmatrix}  c \\ c \end{pmatrix}$, что противоречит  $f\in M$. Если $f\begin{pmatrix} \tilde{\alpha} \\ \bar{\tilde{\alpha}} \end{pmatrix}=\begin{pmatrix}  - \\ c \end{pmatrix}$, где $c\in \{0,1\}$, то для набора $\tilde{\alpha}$  возьмем уточнение $\tilde{\delta}$, которое обязательно найдется, поскольку $f\in O_2$  и  $f(\tilde{\beta})=-$, такое, что  $f(\tilde{\delta})=c$, а для набора $\bar{\tilde{\alpha}}$  выберем уточнение $\tilde{\tau}$  так, чтобы  $\begin{pmatrix} \delta_i \\ \tau_i \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \end{pmatrix}\end{Bmatrix}$  для всех  $i\in\{1,\dots,n\}$. Нетрудно заметить, что булева функция $f$  на любом уточнении набора $\bar{\tilde{\alpha}}$  принимает значение $c$. Тогда  $f\begin{pmatrix} \tilde{\delta} \\ \tilde{\tau} \end{pmatrix}=\begin{pmatrix}  c \\ c \end{pmatrix}$, что противоречит  $f\in M$. Случай $f\begin{pmatrix} \tilde{\alpha} \\ \bar{\tilde{\alpha}} \end{pmatrix}=\begin{pmatrix}  c \\ - \end{pmatrix}$, где $c\in \{0,1\}$, аналогичен предыдущему.
	
Очевидно, что $S \subset O_2$. Далее справедливость леммы следует из того, что $T_0^{-}$, $T_1^{-}$, $M^-$, $K_1$, $K_2$, $K_3$, $K_4$  не содержат отрицание, классы  $L^-$,  $K_5$  -- функцию $d_3$.
\end{proof}

\begin{corollary} Верно, что
$O_2\cap S^- = S$.
\end{corollary}
\begin{proof} Заметим, что класс $S$ в точности совпадает с множеством булевых функций, сохраняющих предикат
$\begin{pmatrix}
	0 & 1  \\
	1 & 0
\end{pmatrix}$ (см., например, \cite{Marchenkov}). Тогда, очевидно, что для любой $f\in S^-$ и любого двоичного набора $\tilde{\alpha}$ такого, что $f(\tilde{\alpha})\in \{0,1\}$ выполняется $f(\tilde{\alpha})=\overline{f(\bar{\tilde{\alpha}})}$. Отсюда следует, что $O_2\cap S^- \subseteq S$. В обратную сторону включение верно в силу леммы 3.
\end{proof}

\begin{lemma}
Для любой $f\in S^-\setminus S$  справедливо  $S^-=[S\cup \{f\}]$.
\end{lemma}

\begin{proof}
Включение $[S\cup \{f\}]\subseteq S^-$  очевидно. Покажем, что любая гиперфункция  $g(x_1,\dots,x_n)\in S^-$  может быть выражена с помощью суперпозиции самодвойственных булевых функций и гиперфункции  $f\in S^-\setminus S$. В силу следствия 3 достаточно рассмотреть случай, когда  $g(x_1,\dots,x_n)\in S^-\setminus S$.
	
Обозначим через $\tilde{\alpha}_1,\dots,\tilde{\alpha}_s$  наборы, на которых значение гиперфункции $g$  равно $0$, через $\tilde{\beta}_1,\dots,\tilde{\beta}_l$ -- наборы, на которых значение гиперфункции $g$  равно $1$, а через $\tilde{\gamma}_1,\dots,\tilde{\gamma}_t$ -- наборы, на которых значение гиперфункции  $g$ равно $-$. Тогда значение гиперфункции $g$ на наборах $\bar{\tilde{\alpha}}_1,\dots,\bar{\tilde{\alpha}}_s$ равно $1$, на наборах $\bar{\tilde{\beta}}_1,\dots,\bar{\tilde{\beta}}_l$ равно $0$, на наборах $\bar{\tilde{\gamma}}_1,\dots,\bar{\tilde{\gamma}}_t$ равно $-$.
	
С помощью гиперфункции $f$  и отрицания получим константную гиперфункцию  $f^-$. Далее выберем самодвойственную функцию $\phi(x_1,\dots,x_m,y)$  такую, что  $\phi(\tilde{\alpha}_i,0)=0$,  $\phi(\tilde{\beta}_j,0)=1$,  $\phi(\tilde{\gamma}_k,0)=0$, $\phi(\bar{\tilde{\alpha}}_i,0)=1$,  $\phi(\bar{\tilde{\beta}}_j,0)=0$,  $\phi(\bar{\tilde{\gamma}}_k,0)=0$,  $\phi(\tilde{\alpha}_i,1)=0$,  $\phi(\tilde{\beta}_j,1)=1$,  $\phi(\tilde{\gamma}_k,1)=1$, $\phi(\bar{\tilde{\alpha}}_i,1)=1$,  $\phi(\bar{\tilde{\beta}}_j,1)=0$,  $\phi(\bar{\tilde{\gamma}}_k,1)=1$, где  $i\in\{1,\dots,s\}$,  $j\in\{1,\dots,l\}$,  $k\in\{1,\dots,t\}$.
	
Покажем, что  $\phi(x_1,\dots,x_m,f^-(x_m))=g(x_1,\dots,x_m)$. Действительно,
	
	$\phi(\tilde{\alpha}_i,-)=\phi(\tilde{\alpha}_i,0)\cap \phi(\tilde{\alpha}_i,1)=0=g(\tilde{\alpha}_i)$,
	
	$\phi(\tilde{\beta}_j,-)=\phi(\tilde{\beta}_j,0)\cap \phi(\tilde{\beta}_j,1)=1=g(\tilde{\beta}_j)$,
	
	$\phi(\tilde{\gamma}_k,-)=\phi(\tilde{\gamma}_k,0)\cup \phi(\tilde{\gamma}_k,1)=-=g(\tilde{\gamma}_k)$,
	
	$\phi(\bar{\tilde{\alpha}}_i,-)=\phi(\bar{\tilde{\alpha}}_i,0)\cap \phi(\bar{\tilde{\alpha}}_i,1)=1=g(\bar{\tilde{\alpha}}_i)$,
	
	$\phi(\bar{\tilde{\beta}}_j,-)=\phi(\bar{\tilde{\beta}}_j,0)\cap \phi(\bar{\tilde{\beta}}_j,1)=0=g(\bar{\tilde{\beta}}_j)$,
	
	$\phi(\bar{\tilde{\gamma}}_k,-)=\phi(\bar{\tilde{\gamma}}_k,0)\cup \phi(\bar{\tilde{\gamma}}_k,1)=-=g(\bar{\tilde{\gamma}}_k)$,
	
	где  $i\in\{1,\dots,s\}$,  $j\in\{1,\dots,l\}$,  $k\in\{1,\dots,t\}$.
	
Следовательно,  $S^-\subseteq [S\cup \{f\}]$.
\end{proof}

\begin{corollary} Верно, что
$S^- = [\{d_3,\bar{x},f^-\}]$.
\end{corollary}
\begin{proof} Следует из $S=[\{d_3,\bar{x}\}]$  (см., например, \cite{Marchenkov}).
\end{proof}


\begin{lemma}
Из 11 максимальных ультраклонов ранга 2 только $O_2$ и $L^-$ содержат $L$.
\end{lemma}
\begin{proof} Заметим, что $L$ в точности совпадает с множеством булевых функций, сохраняющих предикат
$\begin{pmatrix} 0&0&0&0&1&1&1&1\\0&0&1&1&1&1&0&0\\0&1&0&1&1&0&1&0\\0&1&1&0&1&0&0&1 \end{pmatrix}$ (см., например, \cite{Marchenkov}).
Методом от противного покажем, что $L\subset L^-$. Пусть найдутся функция $f(x_1,\dots,x_n)$ и наборы $\tilde{\alpha}=(\alpha_1,\dots,\alpha_n)$ и $\tilde{\beta}=(\beta_1,\dots,\beta_n)$ такие, что $f\in L$, $f\begin{pmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ - \end{pmatrix}, \begin{pmatrix}  - \\ 0 \end{pmatrix}, \begin{pmatrix}  - \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ - \end{pmatrix}\end{Bmatrix}$  и $\begin{pmatrix} \alpha_i \\ \beta_i \end{pmatrix}\in R_M$  для всех $i\in\{1,\dots,n\}$. Если $f\begin{pmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{pmatrix}=\begin{pmatrix}  - \\ c \end{pmatrix}$, где $c\in\{0,1\}$, то для набора $\tilde{\alpha}$  возьмем уточнения $\tilde{\delta}^1$ и $\tilde{\delta}^2$, которые обязательно найдутся, поскольку $f\in O_2$  и  $f(\tilde{\beta})=-$, такие, что  $f(\tilde{\delta}^1)=\bar{c}$, $f(\tilde{\delta}^2)=c$, а для набора $\tilde{\beta}$  выберем уточнения $\tilde{\tau}^1$ и $\tilde{\tau}^2$  так, чтобы  $\begin{pmatrix} \delta^1_{i} \\ \delta^2_{i} \\ \tau^1_{i} \\ \tau^2_{i} \end{pmatrix} \in\begin{Bmatrix}\begin{pmatrix}  0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix}  0 \\ 0 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \\ 0 \\ 1 \end{pmatrix}\end{Bmatrix}$  для всех  $i\in\{1,\dots,n\}$. Нетрудно заметить, что булева функция $f$  на любом уточнении набора $\tilde{\beta}$  принимает значение $c$. Тогда  $f\begin{pmatrix} \tilde{\delta}^1 \\ \tilde{\delta}^2 \\ \tilde{\tau}^1 \\ \tilde{\tau}^2 \end{pmatrix}=\begin{pmatrix}  \bar{c} \\ c \\ c \\ c \end{pmatrix}$, что противоречит  $f\in L$. Случай $f\begin{pmatrix} \tilde{\alpha} \\ \bar{\tilde{\alpha}} \end{pmatrix}=\begin{pmatrix}  c \\ - \end{pmatrix}$, где $c\in \{0,1\}$, аналогичен предыдущему.

Очевидно, что $L \subset O_2$. Далее справедливость леммы следует из того, что $S^-$  не содержит константу $0$,  $T_0^{-}$, $T_1^{-}$, $M^-$, $K_1$, $K_2$, $K_3$, $K_4$ -- отрицание,  $K_5$  -- эквивалентность.
\end{proof}

\begin{lemma} Верно, что
$O_2\cap L^- = L$.
\end{lemma}

\begin{proof} Включение $L \subseteq O_2\cap L^-$ верно в силу леммы 5. Докажем включение $O_2\cap L^- \subseteq L$.
От противного. Пусть найдется булева функция $f\in L^-$ такая, что $f\notin L$, т. е. $f\begin{pmatrix} \tilde{\alpha}^1 \\ \tilde{\alpha}^2 \\ \tilde{\alpha}^3 \\ \tilde{\alpha}^4 \end{pmatrix}\notin\begin{pmatrix} 0&0&0&0&1&1&1&1\\0&0&1&1&1&1&0&0\\0&1&0&1&1&0&1&0\\0&1&1&0&1&0&0&1 \end{pmatrix}$, где \\ $\begin{pmatrix} \alpha^1_i \\ \alpha^2_i \\ \alpha^3_i \\ \alpha^4_i \end{pmatrix}\in\begin{Bmatrix}\begin{pmatrix}  0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix}  0 \\ 0 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \\ 0 \\ 1 \end{pmatrix}\end{Bmatrix}$, $i\in\{1,\dots,n\}$. Тогда суперпозицией $f$ с проекциями, константами $0$, $1$, отрицанием, сложением, эквивалентностью, которые по лемме 5 лежат в $L^-$, получим одну из функций $(0001)$, $(0010)$, $(0100)$, $(1000)$, $(0111)$, $(1011)$, $(1101)$, $(1110)$, причем, перестановкой переменных в $f$ мы можем получить именно конъюнкцию или дизъюнкцию. Из конъюнкции и дизъюнкции с помощью $f^-\in L^-$ легко получить функции, не принадлежащие $L^-$: $e^2_1 \wedge f^- = (00--)$, $e^2_1 \vee f^- = (--11)$. Последнее противоречит тому, что $L^-$ является замкнутым множеством.
\end{proof}

\begin{lemma} Верно, что
$L^-\setminus L = \{f^-\}$.
\end{lemma}

\begin{proof}
С учетом леммы 6 достаточно рассмотреть случай, когда для $f\in L^-\setminus L$ также выполняется $f\in H_2 \setminus O_2$. Предположим, что $f$ отлична от $f^-$, т. е. существует набор $\tilde{\alpha}$ такой, что $f(\tilde{\alpha})=c\in\{0,1\}$. Тогда $f\begin{pmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{pmatrix}=\begin{pmatrix}  c \\ - \end{pmatrix}\notin R_L$ и $\begin{pmatrix} \alpha_i \\ \beta_i \end{pmatrix}\in \begin{Bmatrix}\begin{pmatrix}  0 \\ 0 \end{pmatrix}, \begin{pmatrix}  0 \\ 1 \end{pmatrix}, \begin{pmatrix}  1 \\ 0 \end{pmatrix}, \begin{pmatrix}  1 \\ 1 \end{pmatrix}\end{Bmatrix}$ для всех $i\in\{1,\dots,n\}$, где $\tilde{\beta}$ -- набор, на котором значение функции $f$ равно $-$. Противоречие. 	
\end{proof}	


\begin{corollary} Верно, что
	$L^- = [\{1,\oplus,f^-\}]$.
\end{corollary}
\begin{proof} Следует из $L=[\{1,\oplus\}]$  (см., например, \cite{Marchenkov}).
\end{proof}

\begin{theorem}
	Интервал $\Im(A,H_2)$ содержит ровно $4$ ультраклона, где $$A \in \{M, S, L\},$$ а именно,
	
	\begin{center}
		\begin{tikzpicture}
			[scale=.65,auto=left,every node/.style={circle,draw}]
			\node (n1) at (15,10) {$H_2$};
			\node (n2) at (13,9)  {$O_2$};
			\node (n3) at (17,9)  {$A^-$};
			\node (n4) at (15,8) {$A$};
			
			\foreach \from/\to in {n1/n2,n1/n3,n2/n4,n3/n4}
			\draw (\from) -- (\to);
			
		\end{tikzpicture}
	\end{center}
\end{theorem}

\begin{proof} 1) Если $A=M$, то справедливость утверждения следует из лемм 1, 2 и из того, что $M$  является максимальным клоном в $O_2$, а $O_2$  и $M^-$  являются максимальными ультраклонами ранга 2.

2) Если $A=S$, то справедливость утверждения следует из лемм 3, 4 и из того, что $S$  является максимальным клоном в $O_2$, а $O_2$  и $S^-$  являются максимальными ультраклонами ранга 2.

3) Если $A=L$, то справедливость утверждения следует из лемм 5, 7 и из того, что $L$  является максимальным клоном в $O_2$, а $O_2$  и $L^-$  являются максимальными ультраклонами ранга 2.
\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{PanteleyevHaltanova} S.Yu. Haltanova, V.I. Panteleyev, {\it About some intervals in the lattic of clones of partial ultrafunctions}, The Bulletin of Irkutsk State University. Series Mathematics, \textbf{4} (2010), 80--87.

\bibitem{Haltanova} S.Yu. Haltanova, {\it On Two Isomorphic Intervals in the Lattice of Ultraclones on Two-Elements Set}, The Bulletin of Irkutsk State University. Series Mathematics, \textbf{7} (2014), 133--140.

\bibitem{Panteleyev2009} V.I. Panteleyev, {\it Completeness Criterion for Predefined Boolean Functions (in Russian)},  Vestnik Samar.
Gos. Univ. Est.-Naush. Ser., \textbf{2}:68 (2009), 60--79.

\bibitem{Marchenkov} S.S. Marchenkov, {\it Closed Classes of Boolean Functions}, M: Fizmatlit, 2000, 128 p.



\end{thebibliography}
\end{document}
