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


\def\udcs{519.71} %Здесь автор определяет УДК своей работы
\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[О бесповторных булевых функциях]{О бесповторных булевых функциях \\ в элементарном базисе с медианой}
\author{{И.К. Шаранхаев}}%
\address{Ivan Konstantinovich Sharankhaev  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Dorzhi Banzarov Buryat State University,
\newline\hphantom{iii} st. Smolina, 24a,
\newline\hphantom{iii} 670000, Ulan-Ude, Russia}%
\email{goran5@mail.ru}%

\thanks{\sc Sharankhaev, I.K.,
On read-once Boolean functions in elementary base extended by median}
\thanks{\copyright \ 2019 Шаранхаев И.К}
\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. } Boolean functions that can be realized by read-once terms (formulas) in elementary base extended by median are studied. An algorithm for finding read-once represen\-ta\-ti\-ons of  Boolean functions in this base is obtained.
\medskip

\noindent{\bf Keywords:} Boolean function, superposition, base, decom\-po\-si\-tion, read-once term.
 \end{quote}
}

\vspace{1cm}

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

Бесповторные булевы функции, т. е. функции, которые можно реализовать термом (формулой) в некотором базисе, содержащим каждую переменную не более одного раза, исследовались еще в 50-х годах прошлого века \cite{kuz}. Однако алгоритмы нахождения бесповторных представлений булевых функций рассматривались до сих пор только в бинарных базисах \cite{vin-per}.
В статье исследуются булевы функции, которые можно представить бесповторными термами в элементарном базисе, расширенном функцией медианой (трехместной функцией голосования). На основе необходимого и достаточного условия бесповторности булевых функций в данном базисе, полученного автором в работе \cite{per-shar}, предложен алгоритм нахождения бесповторных представлений булевых функций.

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

Изложению основных результатов предпошлем необходимые обозначения и определения. Все неопределяемые понятия можно найти, например, в [4]. Будем использовать следующие обозначения: переменные обозначаются
символами $x, y, z, u, v$, возможно с индексами; константы
обозначаются символами $\alpha, \sigma, \tau$, возможно с
индексами; символом $\tilde{x}$ обозначается набор
$(x_1,\dots,x_n)$; $| \tilde{x} |$~--- длина набора $\tilde{x}$;
rank $f$~--- ранг функции $f$; $\chi(f)$~--- множество всех
переменных функции $f$; $\rho(f)$~--- множество всех
существенных переменных функции $f$; $\delta(f)$~--- множество
всех фиктивных переменных функции $f$;

$$x^{\sigma}=\left \{
\begin{array}{l}
x,$ если $\sigma =1; \\
\bar{x},$ если $\sigma =0.
\end{array}
\right .$$

Функция, получаемая из $f(x_1,\dots,x_n)$ подстановкой вместо
некоторой переменной $x_i$ константы $\sigma$, называется {\it
остаточной по переменной} $x_i$ и обозначается $f^{\sigma}_{x_i}$.
Индуктивно это определение распространяется на подмножество
переменных.

Переменная $x_i$ функции $f$ называется {\it фиктивной}, если
$f^0_{x_i}=f^1_{x_i}$, и {\it существенной} в противном случае.

{\it Рангом} функции $f$ называется число ее существенных
переменных.

Терм $\Phi$ над базисом $B$ называется {\it бесповторным}, если
каждая переменная входит в него не более одного раза. Функция $f$ называется {\it бесповторной} в базисе $B$, если
существует бесповторный терм $\Phi$ над $B$, представляющий
функцию $f$. В противном случае $f$ называется {\it повторной} в
$B$.

Функция $d_3=(00010111)$ называется {\it медианой}.

Базис $$B_{0}=\{\vee,~\cdot,~-,~0,~1\}$$ называется {\it
элементарным}.
 Базис $B_{0}\cup$\{$d_3$\} обозначим через $D$.

Будем говорить, что функции $f$ и $g$ {\it связаны отношением
$\preceq$}, и писать $f \preceq g$, если для любого набора
$\tilde{\sigma}$ выполняется неравенство $f(\tilde{\sigma}) \leq
g(\tilde{\sigma})$.

Функция $f$ называется {\it обобщенно монотонной по переменной
$x$}, если выполняется либо $f^0_x \preceq f^1_x$, либо $f^0_x
\succeq f^1_x$. Если $f$ является обобщенно монотонной по
переменной $x$, то для краткости будем писать $f \in M_x$.

Функции $f$ и $g$ называются {\it обобщенно однотипными}, если
$$f(x_1,\dots,x_n)=g^{\sigma}(x_{i_1}^{\sigma_1},\dots,x_{i_n}^{
\sigma_n}),$$ \noindent
 где $(i_1,\dots ,i_n)$~--- некоторая перестановка
чисел от 1 до $n$. Очевидно, что на множестве всех булевых функций
отношение обобщенной однотипности является отношением
эквивалентности.

Множество всех функций, обобщенно однотипных с функцией $d_3$, обозначим через $K$.
Нетрудно проверить, что множество $K$ содержит всего 8 функций: $$d_3(x_1, x_2, x_3)=(0001\;0111), d_3(\bar{x}_1, x_2, x_3)=(0111\;0001),$$
$$d_3(x_1, \bar{x}_2, x_3)=(0100\;1101), d_3(x_1, x_2, \bar{x}_3)=(0010\;1011),$$
$$d_3(\bar{x}_1, \bar{x}_2, x_3)=(1101\;0100), d_3(\bar{x}_1, x_2, \bar{x}_3)=(1011\;0010),$$ $$d_3(x_1, \bar{x}_2, \bar{x}_3)=(1000\;1110), d_3(\bar{x}_1, \bar{x}_2, \bar{x}_3)=(1110\;1000).$$

{\it Производной} функции $f(x_1,\dots,x_n)$ по переменной $x_i$
называется функция $$f^{\prime}_{x_i}=f^0_{x_i} \oplus
f^1_{x_i}.$$

Функцию $f$ будем называть {\it 2-нежесткой}, если
либо  rank $f$ < 2, либо для любого $x \in \rho(f)$ справедливо
включение $f \in M_x$ и выполняется одно из условий:

(1) $\delta(f)=\delta(f^0_{x})$ и $\delta(f) \subsetneq
\delta(f^1_{x})$;

(2) $\delta(f)=\delta(f^1_{x})$ и $\delta(f) \subsetneq
\delta(f^0_{x})$;

(3) существуют $y \in \rho(f^{\prime}_{x})$ такая,
что справедливо строгое включение $$\delta(f^{\prime}_{x})
\subsetneq \delta((f^{\prime}_{x})^{\prime}_{y}).$$

Функцию $f$ будем называть {\it наследственно 2-нежесткой}, если
сама $f$ и все ее остаточные функции являются 2-нежесткими.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Вспомогательные результаты}

\medskip

В \cite{per-shar} получено необходимое и достаточное условие бесповторности булевых функций в базисе $D$ (теорема 1), основанное на анализе остаточных функций и производных.

\begin{theorem} Функция $f$ бесповторна в базисе $D$
тогда и только тогда, когда она является наследственно 2-нежесткой.
\end{theorem}

Далее с помощью теоремы 1 получен алгоритм нахождения
бесповторных представлений булевых функций в базисе
$D$. Отметим, что
алгоритм нахождения бесповторных представлений булевых функций в
$B_0=D \setminus \{d_3\}$ построен в
\cite{vin-per}.

Ниже нам понадобится метод разделительной декомпозиции.

Функция $f$ при разбиении множества переменных на $\tilde{u}$ и $\tilde{v}$ допускает разделительную декомпозицию, если существуют функции $h$ и $g$ такие, что выполняется $$f(\tilde{u}, \tilde{v})=h(\tilde{v}, g(\tilde{u})).$$

\begin{theorem} Для любой функции $f$ равносильны следующие условия:

1) $f$ допускает разделительную декомпозицию при разбиении множества переменных на $\tilde{u}$ и $\tilde{v}$;

2) среди всех остаточных функций от $f$ по переменным $\tilde{v}$ не более двух различных;

3) существует функция $t$ такая, что любая остаточная функция от $f$ по переменным $\tilde{u}$ является либо константной, либо функцией $t$, либо функцией $\bar{t}$.
\end{theorem}

Доказательство теоремы 2 смотрите в \cite{vin-per}.


\section{Алгоритм нахождения бесповторных представлений \\
 булевых функций в базисе $D$}

\indent

Алгоритм является рекурсивным, на вход подается существенная  булева функция $f(\tilde{x})$
размерности не менее, чем 1, заданная в векторном виде. На выходе
алгоритм находит бесповторный терм $\Phi(\tilde{x})$,
представляющий $f(\tilde{x})$, или сообщает, что $f(\tilde{x})$ не является бесповторной
в базисе $D$.

A. Проверяем, является ли функция $f(\tilde{x})$ наследственно 2-нежесткой. Если $f(\tilde{x})$ не является 2-нежесткой, то по теореме 1 она является  повторной в $D$ и алгоритм завершает работу, иначе переходим к шагу B.

B. Если функция $f(\tilde{x})$ является одноместной, т. е. $\tilde{x}=x_1$, то $$\Phi(x_1)=x_1\:\mbox{или}\:\Phi(x_1)=\bar{x}_1.$$

C. К этому шагу переходим, если функция $f(\tilde{x})$ не является одноместной.

С.0. Произвольным образом выбираем одну переменную $y$ и находим множества $\tilde{x}_0=\delta(f_y^0)$, $\tilde{x}_1=\delta(f_y^1)$. Если ровно одно из этих множеств пустое, то переходим к С.1. Если для любой переменной множества $\tilde{x}_0$ и $\tilde{x}_1$ являются пустыми, то переходим к С.2.

С.1. К этому шагу переходим, если нашлась переменная $y$ такая, что только одна из остаточных функций от функции $f(\tilde{x})$ по $y$ несущественна.

C.1.а. К этому шагу переходим, если $\tilde{x}_0\cup\{y\}=\tilde{x}$, т. е. $f_y^0$ -- константная. Применив алгоритм к $f_y^1(\tilde{x}_0)$, найдем бесповторный терм $\Psi(\tilde{x}_0)$, представляющий функцию $f_y^1(\tilde{x}_0)$. Тогда искомый терм $\Phi(\tilde{x})$ будет определяться следующим образом: $$\Phi(\tilde{x})=(y\cdot(\Psi(\tilde{x}_0))^{\bar{\sigma}})^{\bar{\sigma}},$$ где $\sigma=f_y^0$.

C.1.b. К этому шагу переходим, если $\tilde{x}_1\cup\{y\}=\tilde{x}$, т. е. функция $f_y^1$ -- константная. Применив алгоритм к $f_y^0(\tilde{x}_1)$, найдем бесповторный терм $\Psi(\tilde{x}_1)$, представляющий функцию $f_y^0(\tilde{x}_1)$. Тогда искомый терм $\Phi(\tilde{x})$, будет определяться следующим образом$\colon$\\
$$\Phi(\tilde{x})=(y\vee(\Psi(\tilde{x}_1))^{\sigma})^{\sigma},$$ где $\sigma=f_y^1$.

C.1.с. Обозначим $\tilde{u}=\{y\}\cup\tilde{x}_0\cup\tilde{x}_1$ и $\tilde{v}=\tilde{x}\setminus\tilde{u}$. Этот шаг выполняется, если $\tilde{u}$ и $\tilde{v}$ оба непусты. Среди остаточных функций $f_{\tilde{u}}^{\tilde{\tau}}$ найдем две различных. Обозначим их через $f_1(\tilde{v})$ и $f_2(\tilde{v})$.

Определим функции $h({\tilde{v},z})$ и $g(\tilde{u})$ следующим образом: $$h({\tilde{v},z})=\bar{z}f_1(\tilde{v})\vee z f_2(\tilde{v}),$$
$$g(\tilde{\tau})=\left \{
\begin{array}{l}
0,$ если $f_{\tilde{u}}^{\tilde{\tau}}=f_1; \\
1,$ если $f_{\tilde{u}}^{\tilde{\tau}}=f_2.
\end{array}
\right .$$

Дважды применяем алгоритм для нахождения бесповторных термов $\Psi_h({\tilde{v},z})$ и $\Psi_g(\tilde{u})$, представляющих $h({\tilde{v},z})$ и $g(\tilde{u})$. Тогда искомый терм $\Phi(\tilde{x})$ будет определяться следующим образом:\\ $$\Phi({\tilde{u},\tilde{v}})=\Psi_h({\tilde{v},\Psi_g({\tilde{u}})}).$$

C.2. К этому шагу переходим, если обе остаточные функции от функции $f$ по каждой переменной существенны. Если функция $f$ является трехместной, то она принадлежит $K$, т. е. представляющий ее терм известен. Иначе выберем произвольным образом набор из трех переменных $\tilde{u}=(x_{i_1}, x_{i_2}, x_{i_3})$. Среди остаточных функций $f_{\tilde{u}}^{\tilde{\tau}}$ найдем две различных. Обозначим их через $f_1(\tilde{v})$ и $f_2(\tilde{v})$.

Определим функции $h({\tilde{v},z})$ и $g(\tilde{u})$, где $\tilde{v}=\tilde{x}\setminus\tilde{u}$,  следующим образом: $$h({\tilde{v},z})=\bar{z}f_1(\tilde{v})\vee z f_2(\tilde{v}),$$
$$g(\tilde{\tau})=\left \{
\begin{array}{l}
0,$ если $f_{\tilde{u}}^{\tilde{\tau}}=f_1; \\
1,$ если $f_{\tilde{u}}^{\tilde{\tau}}=f_2.
\end{array}
\right .$$

Если функция $g(\tilde{u}) \not \in K$, то выберем другой набор $\tilde{u}$ и повторим процедуру построения $h({\tilde{v},z})$ и $g(\tilde{u})$.

 Если выполняется $g(\tilde{u}) \in K$, дважды применяем алгоритм для нахождения бесповторных термов $\Psi_h({\tilde{v},z})$ и $\Psi_g(\tilde{u})$, представляющих $h({\tilde{v},z})$ и $g(\tilde{u})$. Тогда искомый терм $\Phi(\tilde{x})$ будет определяться следующим образом: $$\Phi({\tilde{u},\tilde{v}})=\Psi_h({\tilde{v},\Psi_g({\tilde{u}})}).$$

\begin{theorem}  Алгоритм нахождения бесповторных представлений
 булевых функций в базисе  $D$ является
корректным.
\end{theorem}

\begin{proof} Корректность шага А достигается в силу теоремы 1. Далее доказательство теоремы проведем индукцией по числу $n$ переменных функции $f$.

Базис индукции. Если $n=1$, то функция $f$ является одноместной и выполняется шаг В, который, очевидно, является корректным.

Шаг индукции. Пусть для всех функций размерности меньше, чем $n$ алгоритм является корректным. Рассмотрим выполнение шага С. Оценив функции из базиса $D$, нетрудно заметить, что если функция $f$ является существенной бесповторной в базисе $D$, а она является таковой в силу выполнения шага А, то для любой переменной $y$ либо ровно одна из остаточных функций $f_y^0$, $f_y^1$ существенна, либо обе они существенны. Таким образом, выполняется либо условие пункта С.1, либо условие пункта С.2, т. е. пункт С.0 является корректным.

Пусть выполняется пункт С.1.a. Остаточная функция $f_y^1$ существенна, поэтому рекурсивный вызов алгоритма является корректным. В силу индуктивного предположения бесповторный терм $\Psi(\tilde{x}_0)$ представляет функцию $f_y^1(\tilde{x}_0)$. Теперь тот факт, что $\Phi(\tilde{x})=(y\cdot(\Psi(\tilde{x}_0))^{\bar{\sigma}})^{\bar{\sigma}},$ где $\sigma=f_y^0$, представляет функцию $f$, легко проверяется разбором случаев $y=0$ и $y=1$. По построению терм $\Phi(\tilde{x})$ является бесповторным над $D$, т. е. алгоритм для $f$ является корректным.

Корректность пункта С.1.b доказывается аналогично пункту С.1.a.

Пусть выполняется пункт С.1.c. Ровно одно из множеств $\tilde{x}_0$, $\tilde{x}_1$ непусто, будем для определенности считать, что $\tilde{x}_0$, тогда имеем $\tilde{u}=\{y\}\cup\tilde{x}_0$ и $\tilde{v}=\tilde{x}\setminus\tilde{u}$. В силу шага А функция $f$ является
бесповторной в $D$, тогда представляющий ее бесповторный терм $\Phi(\tilde{x})$ будет иметь подтерм $\Psi(\tilde{u})$ вида $y \cdot \Gamma(\tilde{x}_0)$ или $\bar{y} \vee \Gamma(\tilde{x}_0)$. Таким образом, выполняются условия разделительной декомпозиции теоремы 2, следовательно, $f(\tilde{u}, \tilde{v})=h(\tilde{v}, g(\tilde{u}))$. Остается применить предположение индукции к $h(\tilde{v}, z)$ и $g(\tilde{u}))$.

Пусть выполняется пункт С.2. Функция $f$ является
бесповторной в $D$ и обе остаточные функции от функции $f$ по каждой переменной существенны. Это возможно только в случае, если либо $f \in K$, что сразу влечет корректность алгоритма, либо $f$ допускает разделительную декомпозицию при разбиении множества переменных на $\tilde{u}$ и $\tilde{v}$, т. е. $f(\tilde{u}, \tilde{v})=h(\tilde{v}, g(\tilde{u})),$ где $g(\tilde{u})$ обобщенно однотипна функции $d_3$. Очевидно, что $g(\tilde{u})$ представима термом, бесповторным над $D$. По предположению индукции для $h(\tilde{v}, z)$ алгоритм является корректным. Следовательно, для $f$ алгоритм также является корректным.
\end{proof}

Проверим работу алгоритма на примере функции $$f(x_1, x_2, x_3, x_4, x_5)=(1111\; 1111\; 1111\; 1111\; 0100\; 0100\; 0100\; 1101).$$

Вызов алгоритма 1.

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

1) $f=(1111\; 1111\; 1111\; 1111\; 0100\; 0100\; 0100\; 1101)$,

2) $f_1= (1111\; 1111\; 0100\; 1101)$,

3) $f_2= (1111\; 1111\; 0101\; 0111)$,

4) $f_3= (1111\; 1111\; 0000\; 0001)$,

5) $f_4= (1111\; 0100)$,

6) $f_5= (0100\; 1101)$,

7) $f_6= (0000\; 0001)$,

8) $f_7= (0100)$.

1) Найдем остаточные функции от функции $f$ по каждой переменной:

$f_{x_1}^0=(1111\; 1111\; 1111\; 1111)$, $\delta(f_{x_1}^0)=\{x_2,x_3,x_4,x_5\}$;

$f_{x_1}^1=(0100\; 0100\; 0100\; 1101)$, $\delta(f_{x_1}^1)=\varnothing$;

$f_{x_2}^0=(1111\; 1111\; 0100\; 0100)$, $\delta(f_{x_2}^0)=\{x_3\}$;

$f_{x_2}^1=(1111\; 1111\; 0100\; 1101)$, $\delta(f_{x_2}^1)=\varnothing$;

$f_{x_3}^0=(1111\; 1111\; 0100\; 0100)$, $\delta(f_{x_3}^0)=\{x_2\}$;

$f_{x_3}^1=(1111\; 1111\; 0100\; 1101)$, $\delta(f_{x_3}^1)=\varnothing$;

$f_{x_4}^0=(1111\; 1111\; 0101\; 0111)$, $\delta(f_{x_4}^0)=\varnothing$;

$f_{x_4}^1=(1111\; 1111\; 0000\; 0001)$, $\delta(f_{x_4}^1)=\varnothing$;

$f_{x_5}^0=(1111\; 1111\; 0000\; 0010)$, $\delta(f_{x_5}^0)=\varnothing$;

$f_{x_5}^1=(1111\; 1111\; 1010\; 1011)$, $\delta(f_{x_5}^1)=\varnothing$.

Как видно, $f$ является обобщенно монотонной по каждой переменной. Очевидно, что любая остаточная функция от функции $f$ по любому множеству переменных также является обобщенно монотонной по каждой переменной, поэтому проверку на это свойство в дальнейшем будем пропускать.
Для переменных $x_1$, $x_2$, $x_3$ выполняется второе условие определения 2-неже\-ст\-кой функции, убедимся, что для $x_4$ и $x_5$ выполняется третье условие. Действительно, это верно в силу того, что $\delta(f_{x_4}^{\prime})=\varnothing$, $\delta(f_{x_5}^{\prime})=\varnothing$, $\delta((f_{x_4}^{\prime})_{x_2}^{\prime})=\{x_5\}$, $\delta((f_{x_5}^{\prime})_{x_2}^{\prime})=\{x_4\}$. Итак, функция $f$ является 2-нежесткой.

2) Найдем остаточные функции от функции $f_1$ по каждой переменной:

$(f_1)_{x_1}^0=(1111\; 1111)$, $\delta((f_1)_{x_1}^0)=\{x_2,x_3,x_4\}$;

$(f_1)_{x_1}^1=(0100\; 1101)$, $\delta((f_1)_{x_1}^1)=\varnothing$;

$(f_1)_{x_2}^0=(1111\; 0100)$, $\delta((f_1)_{x_2}^0)=\varnothing$;

$(f_1)_{x_2}^1=(1111\; 1101)$, $\delta((f_1)_{x_2}^1)=\varnothing$;

$(f_1)_{x_3}^0=(1111\; 0111)$, $\delta((f_1)_{x_3}^0)=\varnothing$;

$(f_1)_{x_3}^1=(1111\; 0001)$, $\delta((f_1)_{x_3}^1)=\varnothing$;

$(f_1)_{x_4}^0=(1111\; 0010)$, $\delta((f_1)_{x_4}^0)=\varnothing$;

$(f_1)_{x_4}^1=(1111\; 1011)$, $\delta((f_1)_{x_4}^1)=\varnothing$.

Очевидно, что для $x_1$ выполняется второе условие определения 2-неже\-ст\-кой функции. Для остальных переменных выполняется третье условие 2-неже\-ст\-кой функции, так как $\delta((f_1)_{x_2}^{\prime})=\varnothing$, $\delta(((f_1)_{x_2}^{\prime})_{x_4}^{\prime})=\{x_3\}$, $\delta((f_1)_{x_3}^{\prime})=\varnothing$, $\delta(((f_1)_{x_3}^{\prime})_{x_4}^{\prime})=\{x_2\}$, $\delta((f_1)_{x_4}^{\prime})=\varnothing$, $\delta(((f_1)_{x_4}^{\prime})_{x_3}^{\prime})=\{x_2\}$. Итак, функция $f_1$ является 2-нежесткой.

3) Найдем остаточные функции от функции $f_2$ по каждой переменной:

$(f_2)_{x_1}^0=(1111\; 1111)$, $\delta((f_2)_{x_1}^0)=\{x_2,x_3,x_4\}$;

$(f_2)_{x_1}^1=(0101\; 0111)$, $\delta((f_2)_{x_1}^1)=\varnothing$;

$(f_2)_{x_2}^0=(1111\; 0101)$, $\delta((f_2)_{x_2}^0)=\{x_3\}$;

$(f_2)_{x_2}^1=(1111\; 0111)$, $\delta((f_2)_{x_2}^1)=\varnothing$;

$(f_2)_{x_3}^0=(1111\; 0101)$, $\delta((f_2)_{x_3}^0)=\{x_2\}$;

$(f_2)_{x_3}^1=(1111\; 0111)$, $\delta((f_2)_{x_3}^1)=\varnothing$;

$(f_2)_{x_4}^0=(1111\; 0001)$, $\delta((f_2)_{x_4}^0)=\varnothing$;

$(f_2)_{x_4}^1=(1111\; 1111)$, $\delta((f_2)_{x_4}^1)=\{x_1,x_2,x_3\}$.

Очевидно, что для $x_1$, $x_2$, $x_3$  выполняется второе условие определения 2-неже\-ст\-кой функции, а для $x_4$
выполняется первое условие.  Итак, функция $f_2$ является 2-нежесткой.

4) Найдем остаточные функции от функции $f_3$ по каждой переменной:

$(f_3)_{x_1}^0=(1111\; 1111)$, $\delta((f_3)_{x_1}^0)=\{x_2,x_3,x_4\}$;

$(f_3)_{x_1}^1=(0000\; 0001)$, $\delta((f_3)_{x_1}^1)=\varnothing$;

$(f_3)_{x_2}^0=(1111\; 0000)$, $\delta((f_3)_{x_2}^0)=\{x_3, x_4\}$;

$(f_3)_{x_2}^1=(1111\; 0001)$, $\delta((f_3)_{x_2}^1)=\varnothing$;

$(f_3)_{x_3}^0=(1111\; 0000)$, $\delta((f_3)_{x_3}^0)=\{x_2, x_4\}$;

$(f_3)_{x_3}^1=(1111\; 0001)$, $\delta((f_3)_{x_3}^1)=\varnothing$;

$(f_3)_{x_4}^0=(1111\; 0000)$, $\delta((f_3)_{x_4}^0)=\{x_2, x_3\}$;

$(f_3)_{x_4}^1=(1111\; 0001)$, $\delta((f_3)_{x_4}^1)=\varnothing$.

Очевидно, что для $x_1$, $x_2$, $x_3$, $x_4$  выполняется второе условие определения 2-неже\-ст\-кой функции. Итак, функция $f_3$ является 2-нежесткой.

5) Найдем остаточные функции от функции $f_4$ по каждой переменной:

$(f_4)_{x_1}^0=(1111)$, $\delta((f_4)_{x_1}^0)=\{x_2,x_3\}$;

$(f_4)_{x_1}^1=(0100)$, $\delta((f_4)_{x_1}^1)=\varnothing$;

$(f_4)_{x_2}^0=(1101)$, $\delta((f_4)_{x_2}^0)=\varnothing$;

$(f_4)_{x_2}^1=(1100)$, $\delta((f_4)_{x_2}^1)=\{x_3\}$;

$(f_4)_{x_3}^0=(1100)$, $\delta((f_4)_{x_3}^0)=\{x_2\}$;

$(f_4)_{x_3}^1=(1110)$, $\delta((f_4)_{x_3}^1)=\varnothing$.

Очевидно, что для $x_1$, $x_3$  выполняется второе условие определения 2-неже\-ст\-кой функции, а для $x_2$
выполняется первое условие. Итак, функция $f_4$ является 2-нежесткой.

6) Найдем остаточные функции от функции $f_5$ по каждой переменной:

$(f_5)_{x_1}^0=(0100)$, $\delta((f_5)_{x_1}^0)=\varnothing$;

$(f_5)_{x_1}^1=(1101)$, $\delta((f_5)_{x_1}^1)=\varnothing$;

$(f_5)_{x_2}^0=(0111)$, $\delta((f_5)_{x_2}^0)=\varnothing$;

$(f_5)_{x_2}^1=(0001)$, $\delta((f_5)_{x_2}^1)=\varnothing$;

$(f_5)_{x_3}^0=(0010)$, $\delta((f_5)_{x_3}^0)=\varnothing$;

$(f_5)_{x_3}^1=(1011)$, $\delta((f_5)_{x_3}^1)=\varnothing$.

Для $x_1$, $x_2$, $x_3$ выполняется третье условие 2-неже\-ст\-кой функции, так как $\delta((f_5)_{x_1}^{\prime})=\varnothing$, $\delta(((f_5)_{x_1}^{\prime})_{x_2}^{\prime})=\{x_3\}$, $\delta((f_5)_{x_2}^{\prime})=\varnothing$, $\delta(((f_5)_{x_2}^{\prime})_{x_1}^{\prime})=\{x_3\}$, $\delta((f_5)_{x_3}^{\prime})=\varnothing$, $\delta(((f_5)_{x_3}^{\prime})_{x_1}^{\prime})=\{x_2\}$. Итак, функция $f_5$ является 2-нежесткой.

Случаи 7) и 8) аналогичны случаю 5).

Таким образом, функция $f$ является наследственно 2-нежесткой, поэтому по теореме 1 бесповторна в $D$.

Вызов алгоритма 2.

С.0. Находим $\tilde{x}_0=\delta(f_{x_1}^0)$, $\tilde{x}_1=\delta(f_{x_1}^1)$:
$$f_{x_1}^0=(1111\; 1111\; 1111\; 1111), f_{x_1}^1=(0100\; 0100\; 0100\; 1101),$$ т. е. $\tilde{x}_0=\delta(f_{x_1}^0)=\{x_2,x_3,x_4,x_5\}$, $\tilde{x}_1=\delta(f_{x_1}^1)=\varnothing$. Очевидно, выполняется условие пункта C.1.a, поэтому переходим к нему.

C.1.a. Применив алгоритм к $f_{x_1}^1(\tilde{x}_0)$ (вызов 3), найдем бесповторный терм $\Psi(\tilde{x}_0)=d_3(x_2 \cdot x_3, \bar{x}_4, x_5)$, представляющий функцию $f_{x_1}^1(\tilde{x}_0)$. Тогда искомый терм $\Phi(\tilde{x})=\overline{x_1 \cdot \bar{d}_3(x_2 \cdot x_3, \bar{x}_4, x_5)}$.

Вызов алгоритма 3.

С.0. $f(x_2, x_3, x_4, x_5)=(0100\; 0100\; 0100\; 1101)$. Находим $\tilde{x}_0=\delta(f_{x_2}^0)$, $\tilde{x}_1=\delta(f_{x_2}^1)$:
$$f_{x_2}^0=(0100\; 0100), f_{x_2}^1=(0100\; 1101),$$ т. е. $\tilde{x}_0=\delta(f_{x_2}^0)=\{x_3\}$, $\tilde{x}_1=\delta(f_{x_2}^1)=\varnothing$. Выполняется условие пункта C.1.c, поэтому переходим к нему.

C.1.c. Находим $\tilde{u}=\{x_2, x_3\}$, $\tilde{v}=\{x_4, x_5\}$. Вычисляем остаточные функции от $f$ по $x_1$, $x_2$:
$$f_1(x_4, x_5)=(0100), f_2(x_4, x_5)=(1101).$$
Находим функции $h(z, x_4, x_5)=(0100\; 1101)$ и $g(x_2, x_3)=(0001)$.

Применив алгоритм к $h(z, x_4, x_5)=(0100\; 1101)$ (вызов 4), найдем бесповторный терм $\Psi_h(z, x_4, x_5)=d_3(z, \bar{x}_4, x_5)$. Применив алгоритм к $g(x_2, x_3)=(0001)$ (вызов 5), найдем бесповторный терм $\Psi_g(x_2, x_3)=x_2 \cdot x_3$.Тогда искомый терм $\Phi(x_2, x_3, x_4, x_5)=d_3(x_2 \cdot x_3, \bar{x}_4, x_5)$.

Вызов алгоритма 4.

C.0. $f(z, x_4, x_5)=(0100\; 1101)$. Для любой переменной множества $\tilde{x}_0$ и $\tilde{x}_1$ являются пустыми, переходим к С.2.

C.2. Поскольку $f \in K$, имеем искомый  терм $\Phi(z, x_4, x_5)=d_3(z, \bar{x}_4, x_5)$.

Вызов алгоритма 5.

С.0. $f(x_2, x_3)=(0001)$. Находим $\tilde{x}_0=\delta(f_{x_2}^0)$, $\tilde{x}_2=\delta(f_{x_1}^1)$:
$$f_{x_2}^0=(00), f_{x_2}^1=(01),$$ т. е. $\tilde{x}_0=\delta(f_{x_2}^0)=\{x_3\}$, $\tilde{x}_1=\delta(f_{x_2}^1)=\varnothing$. Очевидно, выполняется условие пункта C.1.a, поэтому переходим к нему.

C.1.a. Применив алгоритм к $f_{x_2}^1(x_3)$ (вызов 6), найдем бесповторный терм $\Psi(x_3)= x_3$, представляющий функцию $f_{x_2}^1(x_3)$. Тогда искомый терм  $$\Phi(x_2, x_3)=x_2 \cdot x_3.$$

Вызов алгоритма 6.

B. $f(x_3)=(01)$. Функция $f$ одноместная, поэтому искомый терм  $\Phi(x_3)=x_3.$

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

\bibitem{kuz} A.V. Kuznetsov, {\it On Repetition-Free Contact Circuits
and Repetition-Free Superpositions of Logic Functions}, Trudi Mat. Instit. AN USSR, {\bf 51} (1958), 186--225.

\bibitem{vin-per} S.F. Vinokurov, N.A. Peryazev, {\it Selected Questions of Theory of Boolean functions},
Fizmatlit, M., 2001.


\bibitem{per-shar} N.A. Peryazev, I.K. Sharankhaev, {\it Repetition-free Criteria for a Boolean Function in the Pre-elementary Bases of Rank 3}, Discrete Math. Appl., {\bf 15}:3 (2005), 299--311.
    \url{http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=104&option_lang=eng}

\bibitem{per} N.A. Peryazev, {\it Fundamentals of Theory of Boolean Functions},
Fizmatlit, M., 1999.

\end{thebibliography}
\end{document}
