К. А. Попков, “О реализации линейных булевых функций самокорректирующимися схемами из ненадежных функциональных элементов”, Матем. заметки, 115:1 (2024), 91–107; Math. Notes, 115:1 (2024), 77

В работе рассматривается задача построения самокорректирующихся схем [1], реализующих заданные булевы функции. Произвольная схема из функциональных элементов называется самокорректирующейся относительно некоторого перечня неисправностей, если при наличии в ней каких угодно неисправностей из этого перечня она реализует ту же булеву функцию, что и при отсутствии в ней неисправностей. Вопросы самокорректирования схем из функциональных элементов исследовались в работах [2]–[10]; при этом всюду предполагалось, что некоторые функциональные элементы являются надежными, т.е. всегда исправными. Это требование возникало из-за того, что во всех указанных работах допускались, в частности, константные неисправности на выходах элементов, а при наличии константной неисправности на выходе выходного элемента любой схемы, реализующей неконстантную булеву функцию, схема начинает реализовывать некоторую булеву константу и тем самым не является самокорректирующейся; таким образом, для возможности реализации хотя бы какой-нибудь неконстантной булевой функции самокорректирующейся схемой из функциональных элементов необходимо, чтобы как минимум выходной элемент этой схемы был надежным.

В работах автора [11], [12], в отличие от работ [2]–[10], изучались возможности построения самокорректирующихся схем, состоящих только из ненадежных функциональных элементов. В [11] были установлены, в частности, следующие факты: 1) любую булеву функцию можно реализовать схемой из ненадежных функциональных элементов, каждый из которых имеет не более трех входов, самокорректирующейся относительно некоторых неисправностей произвольного числа элементов [11; теорема 1]; 2) для любого натурального $k$ любую булеву функцию можно реализовать схемой из ненадежных функциональных элементов, каждый из которых имеет не более двух входов, самокорректирующейся относительно некоторых неисправностей не более $k$ элементов [11; теоремы 2 и 3]. Данные эффекты достигались за счет рассмотрения неисправностей функциональных элементов, отличных от константных неисправностей на их выходах. В [12] было показано, что никакую нелинейную булеву функцию нельзя реализовать схемой из ненадежных функциональных элементов, каждый из которых имеет не более двух входов, самокорректирующейся относительно хотя бы каких-нибудь неисправностей произвольного числа элементов. Открытым оставался вопрос о том, можно ли последнее утверждение распространить на линейные булевы функции. В настоящей статье на этот вопрос получен положительный ответ для функций, существенно зависящих хотя бы от двух переменных (теорема 1), и отрицательный ответ для функций, существенно зависящих не более чем от одной переменной (замечание 1).

Отметим, что любая схема, самокорректирующаяся относительно некоторых неисправностей содержащихся в ней функциональных элементов, не имеет ни одной функции неисправности, отличной от исходной функции, реализуемой схемой, и, как следствие, допускает проверяющий и диагностический тест длины $0$ относительно указанных неисправностей; соответствующие определения можно найти, например, в [1]. Поэтому задачи построения самокорректирующихся схем тесно связаны с проблемами синтеза легкотестируемых схем, активно исследуемыми в настоящее время – см., например, [13]–[24].

Любое множество булевых функций, каждая из которых существенно зависит от всех своих переменных, будем называть базисом. Введем обозначение $\widetilde x^m=(x_1,\dots,x_m)$, где $m\in\mathbb N\cup\{0\}$; в случае $m=0$ полагаем, что $x_1,\dots,x_m$ – пустая строка.

Опишем формальную постановку задачи, как это сделано в [12]. Пусть зафиксирован базис $B$. Будем предполагать, что для каждой функции $\varphi(\widetilde x^m)$ из $B$ имеется сколь угодно много функциональных элементов, каждый из которых реализует в исправном состоянии эту функцию от своих входов; указанные элементы назовем $\varphi$-элементами. Для каждой функции $\varphi(\widetilde x^m)\in B$ введем допустимое множество $M_\varphi=\{M_{\varphi,1},\dots,M_{\varphi,r}\}$, где $r\in\mathbb N$ и $M_{\varphi,i}$ для каждого $i\in\{1,\dots,r\}$ – непустое множество (некоторых) отличных от $\varphi(\widetilde x^m)$ булевых функций от $m$ переменных $x_1,\dots,x_m$. Предполагается, что всевозможные $\varphi$-элементы разделены на $r$ типов и каждый такой элемент $i$-го типа, $i=1,\dots,r$, может перейти в одно из $|M_{\varphi,i}|$ неисправных состояний независимо от неисправностей других функциональных элементов и начать реализовывать вместо “правильной” функции $\varphi(\widetilde x^m)$ некоторую функцию $\psi(\widetilde x^m)$ (от своих входов) из множества $M_{\varphi,i}$; такую неисправность будем называть неисправностью типа $\psi$ рассматриваемого элемента. Условие $M_{\varphi,i}\ne\varnothing$ для любого $i\in\{1,\dots,r\}$ означает, что для каждого $\varphi$-элемента $i$-го типа допустима хотя бы одна неисправность (нет “абсолютно надежных” элементов).

Вход функционального элемента $E$, соответствующий переменной $x_i$, для краткости будем называть входом $x_i$ элемента $E$. Будем говорить, что элемент $E$ расположен в схеме из функциональных элементов выше (ниже) элемента $E'$, если в этой схеме существует ориентированный путь от $E$ к $E'$ (соответственно от $E'$ к $E$).

Булева функция $f(\widetilde x^n)$ называется линейной, если она представима в виде

2. Формулировка и доказательство основного результата

Основным результатом данной работы является следующая

Доказательство. В силу основной теоремы работы [12] достаточно доказать утверждение, получающееся из формулировки теоремы 1 добавлением перед словом “булеву” слова “линейную”. Предположим противное: существует линейная булева функция $f(\widetilde x^n)$, существенно зависящая по крайней мере от двух переменных, которую можно реализовать схемой из функциональных элементов $S$ в базисе $B=\{\varphi_1(\widetilde x^{m_1}),\dots,\varphi_l(\widetilde x^{m_l})\}$, где $l\in\mathbb N$ и $m_1,\dots,m_l\in\{0,1,2\}$, самокорректирующейся относительно неисправностей, задаваемых некоторыми допустимыми множествами $M_{\varphi_1},\dots,M_{\varphi_l}$, произвольного числа элементов. Рассмотрим произвольный двухвходовой функциональный элемент $E$, содержащийся в схеме $S$. Пусть он реализует в исправном состоянии функцию $\varphi_E(x_1,x_2)$ от своих входов. У элемента $E$ возможна хотя бы одна неисправность в силу определения допустимых множеств. Пусть при некоторой неисправности он реализует булеву функцию $\psi_E(x_1,x_2)$ от своих входов, где $\psi_E\ne\varphi_E$. Тогда существуют такие $\alpha_E,\beta_E\in\{0,1\}$, что

$$ \begin{equation} \psi_E(\alpha_E,\beta_E)\ne\varphi_E(\alpha_E,\beta_E). \end{equation} \tag{2.1} $$

Пусть $\psi'_E(x_1,x_2)$ – булева функция, отличающаяся от функции $\varphi_E(x_1,x_2)$ только на наборе $(\alpha_E,\beta_E)$. Рассмотрим следующие неисправности элементов в схеме $S$ (вообще говоря, отличные от неисправностей, задаваемых множествами $M_{\varphi_1},\dots,M_{\varphi_l}$): предположим, что каждый двухвходовой элемент $E$ схемы $S$ имеет только одно неисправное состояние и реализует в этом состоянии функцию $\psi'_E(x_1,x_2)$ от своих входов, а все остальные элементы схемы $S$ (имеющие не более одного входа) надежны, т.е. всегда исправны. Указанные неисправности назовем $\psi'$-неисправностями элементов схемы $S$.

Доказательство. При отсутствии неисправностей схема $S$ реализует функцию $f(\widetilde x^n)$, существенно зависящую по крайней мере от двух переменных, поэтому в данной схеме содержится выходной элемент. Зафиксируем некоторое состояние $\mathrm A_1$ схемы $S$ при $\psi'$-неисправностях ее элементов: пусть каждый двухвходовой элемент $E$ этой схемы либо исправен и реализует функцию $\varphi_E(x_1,x_2)$ от своих входов, либо находится в (единственном) неисправном состоянии и реализует функцию $\psi'_E(x_1,x_2)$ от своих входов, а все остальные элементы схемы $S$ исправны. Докажем, что на выходе схемы $S$ реализуется функция $f(\widetilde x^n)$. Достаточно доказать, что при подаче на входы схемы произвольного двоичного $n$-разрядного набора $\widetilde\sigma$ на ее выходе возникает значение $f(\widetilde\sigma)$. Определим состояние $\mathrm A_2$ схемы $S$ при неисправностях, задаваемых множествами $M_{\varphi_1},\dots,M_{\varphi_l}$, произвольного числа ее элементов. Пусть при подаче на входы схемы $S$, находящейся в состоянии $\mathrm A_1$, набора $\widetilde\sigma$ на входы некоторого ее двухвходового элемента $E$ подается набор $(\alpha'_E,\beta'_E)$. Тогда будем считать, что если $(\alpha'_E,\beta'_E)\ne(\alpha_E,\beta_E)$ или при нахождении схемы $S$ в состоянии $\mathrm A_1$ элемент $E$ исправен, то при нахождении схемы $S$ в состоянии $\mathrm A_2$ элемент $E$ исправен, а в противном случае при нахождении схемы $S$ в состоянии $\mathrm A_2$ элемент $E$ неисправен и реализует функцию $\psi_E(x_1,x_2)$ от своих входов. Будем также считать, что при нахождении схемы $S$ в состоянии $\mathrm A_2$ все ее элементы, имеющие не более одного входа, исправны.

Схема $S$ является самокорректирующейся относительно неисправностей, задаваемых множествами $M_{\varphi_1},\dots,M_{\varphi_l}$, произвольного числа элементов, поэтому при ее нахождении в состоянии $\mathrm A_2$ и подаче на ее входы набора $\widetilde\sigma$ на выходе схемы возникает значение $f(\widetilde\sigma)$. В схеме $S$ можно ввести монотонную нумерацию вершин (см., например, [26; с. 66]), при которой каждое ребро ориентировано от вершины с меньшим номером к вершине с бо́льшим номером. Обозначим все функциональные элементы схемы $S$ в порядке возрастания их номеров через $E_1,\dots,E_d$. Докажем индукцией по $i\in\{1,\dots,d\}$, что при подаче на входы схемы $S$ набора $\widetilde\sigma$ на выходе элемента $E_i$ в этой схеме возникают одинаковые значения при нахождении ее в состояниях $\mathrm A_1$ и $\mathrm A_2$. Отсюда будет следовать, что на выходе выходного элемента схемы $S$, т.е. на выходе схемы, при нахождении ее в состоянии $\mathrm A_1$ возникает то же значение $f(\widetilde\sigma)$, что и при нахождении схемы в состоянии $\mathrm A_2$.

База индукции. Пусть $i=1$. Входы элемента $E_1$, очевидно, могут соединяться только со входами схемы. Если элемент $E_1$ имеет не более одного входа, то он исправен при нахождении схемы $S$ в любом из состояний $\mathrm A_1,\mathrm A_2$, и требуемое утверждение доказано. Пусть элемент $E_1$ имеет ровно два входа и при подаче на входы схемы набора $\widetilde\sigma$ на эти два входа поступает набор $(\alpha'_{E_1},\beta'_{E_1})$. Если данный элемент исправен при нахождении схемы в состоянии $\mathrm A_1$, то он исправен и при нахождении схемы в состоянии $\mathrm A_2$, поэтому на его выходе в схеме $S$ в обоих случаях возникает значение $\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1})$. Пусть теперь элемент $E_1$ неисправен при нахождении схемы в состоянии $\mathrm A_1$. Тогда он реализует функцию $\psi'_{E_1}(x_1,x_2)$ от своих входов, поэтому на его выходе в схеме возникает значение $\psi'_{E_1}(\alpha'_{E_1},\beta'_{E_1})$. Если

$$ \begin{equation} (\alpha'_{E_1},\beta'_{E_1})\ne(\alpha_{E_1},\beta_{E_1}), \end{equation} \tag{2.2} $$

то $\psi'_{E_1}(\alpha'_{E_1},\beta'_{E_1})=\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1})$, так как $(\alpha_{E_1},\beta_{E_1})$ – единственный двоичный двухразрядный набор, на котором значения функций $\psi'_{E_1}$ и $\varphi_{E_1}$ различаются. Тогда на выходе элемента $E_1$ в схеме $S$ при ее нахождении в состоянии $\mathrm A_1$ возникает значение $\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1})$. С другой стороны, при выполнении условия (2.2) элемент $E_1$ схемы $S$ при ее нахождении в состоянии $\mathrm A_2$, согласно определению этого состояния, исправен, т.е. реализует функцию $\varphi_{E_1}(x_1,x_2)$ от своих входов, и значение на выходе данного элемента в схеме также равно $\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1})$.

Пусть теперь условие (2.2) не выполнено, т.е. $(\alpha'_{E_1},\beta'_{E_1})=(\alpha_{E_1},\beta_{E_1})$. Тогда

$$ \begin{equation*} \psi_{E_1}(\alpha'_{E_1},\beta'_{E_1})=\psi_{E_1}(\alpha_{E_1},\beta_{E_1}) \ne\varphi_{E_1}(\alpha_{E_1},\beta_{E_1})=\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1}) \end{equation*} \notag $$

в силу (2.1), т.е.

$$ \begin{equation*} \psi_{E_1}(\alpha'_{E_1},\beta'_{E_1})=\overline{\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1})}. \end{equation*} \notag $$

Кроме того, $\psi'_{E_1}(\alpha_{E_1},\beta_{E_1})\ne\varphi_{E_1}(\alpha_{E_1},\beta_{E_1})$, откуда следует, что

$$ \begin{equation*} \psi'_{E_1}(\alpha'_{E_1},\beta'_{E_1})=\psi'_{E_1}(\alpha_{E_1},\beta_{E_1}) \ne\varphi_{E_1}(\alpha_{E_1},\beta_{E_1})=\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1}), \end{equation*} \notag $$

т.е.

$$ \begin{equation*} \psi'_{E_1}(\alpha'_{E_1},\beta'_{E_1})=\overline{\varphi_{E_1}(\alpha'_{E_1},\beta'_{E_1})} =\psi_{E_1}(\alpha'_{E_1},\beta'_{E_1}). \end{equation*} \notag $$

Таким образом, значение на выходе элемента $E_1$ в схеме $S$ при ее нахождении в состоянии $\mathrm A_1$, равное $\psi'_{E_1}(\alpha'_{E_1},\beta'_{E_1})$, совпадает со значением на выходе элемента $E_1$ в этой схеме при ее нахождении в состоянии $\mathrm A_2$, равным $\psi_{E_1}(\alpha'_{E_1},\beta'_{E_1})$. База индукции доказана.

Предположение и шаг индукции. Пусть $d\geqslant 2$ и утверждение доказано для $i=1,\dots,j-1$, где $j\leqslant d$; докажем его для $i=j$. Входы элемента $E_j$ в силу монотонности нумерации могут соединяться только со входами схемы $S$ и с выходами элементов $E_1,\dots,E_{j-1}$. Тогда с учетом предположения индукции при подаче на входы схемы $S$ набора $\widetilde\sigma$ на входы элемента $E_j$ в этой схеме поступают одинаковые наборы при нахождении ее в состояниях $\mathrm A_1$ и $\mathrm A_2$. Далее дословно повторяем доказательство базы индукции, начиная с фразы “Если элемент $E_1$ имеет не более одного входа…” с заменой всюду $E_1$ на $E_j$. Шаг индукции, а вместе с ним требуемое утверждение доказаны.

Тем самым установлено, что при подаче на входы схемы $S$ произвольного двоичного $n$-разрядного набора $\widetilde\sigma$ на ее выходе при нахождении схемы в состоянии $\mathrm A_1$ возникает значение $f(\widetilde\sigma)$. Отсюда следует, что схема $S$ в состоянии $\mathrm A_1$ реализует функцию $f(\widetilde x^n)$. В силу произвольности выбора состояния $\mathrm A_1$ схемы при $\psi'$-неисправностях ее элементов получаем, что она является самокорректирующейся относительно $\psi'$-неисправностей произвольного числа элементов. Лемма доказана.

Вернемся к доказательству основной теоремы. Всюду далее будем предполагать, что на входы схем из функциональных элементов, помимо переменных, может подаваться константа $0$. Функция $f(\widetilde x^n)$ линейна и существенно зависит по крайней мере от двух переменных, поэтому она имеет вид $x_{i_1}\oplus x_{i_2}\oplus\dots\oplus x_{i_t}\oplus c$, где $2\leqslant t\leqslant n$; $i_1,i_2,\dots,i_t$ – попарно различные индексы от $1$ до $n$ и $c\in\{0,1\}$. Подадим на входы схемы $S$ вместо всех переменных, кроме $x_{i_1}$ и $x_{i_2}$, нули. Полученную схему из функциональных элементов обозначим через $S_0$; очевидно, что на ее выходе реализуется булева функция, получающаяся из функции $x_{i_1}\oplus x_{i_2}\oplus\dots\oplus x_{i_t}\oplus c$ подстановкой вместо каждой переменной, кроме $x_{i_1}$ и $x_{i_2}$, константы $0$, т.е. функция $x_{i_1}\oplus x_{i_2}\oplus c$, причем это свойство сохраняется и при наличии $\psi'$-неисправностей произвольного числа элементов в схеме $S$ в силу леммы 1. Отсюда следует, что схема $S_0$ также является самокорректирующейся относительно $\psi'$-неисправностей произвольного числа элементов. Для удобства переменные $x_{i_1}$ и $x_{i_2}$ обозначим через $x$ и $y$ соответственно. Схема $S_0$ реализует функцию $x\oplus y\oplus c$, существенно зависящую по крайней мере от двух переменных, поэтому в данной схеме содержится выходной элемент, который мы обозначим через $E_{\mathrm{out}}$.

Множество всех булевых функций от переменных $x_1,x_2$ разобьем на два непересекающихся подмножества

Будем далее считать, что в схеме $S_0$ возможны только $\psi'$-неисправности элементов. Предположим, что все двухвходовые элементы схемы $S_0$, каждый из которых в исправном состоянии реализует функцию из множества $M_2$ от своих входов, неисправны, а все остальные элементы этой схемы исправны; данную ситуацию назовем $L$-состоянием схемы $S_0$. Тогда на выходе схемы по-прежнему реализуется функция $x\oplus y\oplus c$, так как схема $S_0$ является самокорректирующейся. Рассмотрим произвольный двухвходовой элемент $E$, содержащийся в данной схеме. Если $\varphi_E(x_1,x_2)\in M_2$, то элемент $E$ неисправен и реализует функцию $\psi'_E(x_1,x_2)$ от своих входов, которая отличается от функции $\varphi_E(x_1,x_2)$ ровно на одном наборе. Заметим, что каждая функция из множества $M_2$, в том числе $\varphi_E(x_1,x_2)$, принимает значение $1$ ровно на одном или трех наборах, а каждая функция из множества $L_2$ – на нуле, двух или четырех наборах, поэтому $\psi'_E(x_1,x_2)\in L_2$. Если же $\varphi_E(x_1,x_2)\notin M_2$, то элемент $E$ исправен и реализует функцию $\varphi_E(x_1,x_2)\in L_2$ от своих входов. Таким образом, все двухвходовые элементы схемы $S_0$ при ее нахождении в $L$-состоянии реализуют функции из множества $L_2$ от своих входов. То же можно сказать и обо всех остальных элементах этой схемы (имеющих не более одного входа), так как все функции $0,1,x_1,\overline x_1$ принадлежат $L_2$.

Пусть $\widehat S$ – произвольная схема из функциональных элементов, каждый элемент которой имеет не более двух входов и реализует функцию из множества $L_2$ от своих входов. Определим понятие существенного входа элемента схемы $\widehat S$. Каждый вход каждого ее двухвходового элемента, реализующего функцию $x_1\oplus x_2$ или $x_1\oplus x_2\oplus 1$ от своих входов, будем считать существенным. Вход каждого ее одновходового элемента, реализующего функцию $x_1$ или $\overline x_1$ от своего входа, также будем считать существенным. Наконец, для каждого $i\in\{1,2\}$ и каждого двухвходового элемента схемы $\widehat S$, реализующего функцию $x_i$ или $\overline x_i$ от своих входов, вход $x_i$ элемента будем считать существенным. Все остальные входы элементов схемы $\widehat S$ будут предполагаться несущественными. Ориентированный путь в этой схеме будем считать существенным, если он не проходит через несущественные входы элементов. Степенью произвольного элемента схемы $\widehat S$ назовем общее число несовпадающих существенных путей, соединяющих данный элемент с выходом схемы. Например, если в схеме, изображенной на рис. 1, элементы $E_1,E_2,E_3,E_4,E_5,E_6$ реализуют функции соответственно $x_1\oplus x_2$, $x_1\oplus x_2$, $\overline x_1$, $0$, $x_1\oplus x_2\oplus 1=x_1\sim x_2$, $x_1\oplus x_2$, где $x_1$ – левый, а $x_2$ – правый вход каждого двухвходового элемента, то степени элементов $E_1,E_2,E_3,E_4,E_5,E_6$ равны $2,1,1,1,1,1$ соответственно (скажем, существенными путями, соединяющими элемент $E_1$ с выходом схемы, являются пути $E_1-E_3-E_5-E_6$ и $E_1-E_2-E_6$).

Пусть схема $S_0$ находится в $L$-состоянии. Предположим, что в ней есть хотя бы один двухвходовой элемент $E$, имеющий нечетную степень, на входы которого в этой схеме подаются функции двух из трех видов $x\oplus a_1$, $y\oplus a_2$, $x\oplus y\oplus a_3$, где $a_1,a_2,a_3\in\{0,1\}$. Функции, подаваемые в схеме $S_0$ на входы $x_1$ и $x_2$ элемента $E$, обозначим через $h_1(x,y)$ и $h_2(x,y)$ соответственно. Пусть данный элемент поменял свое состояние и вместо функции из множества $L_2$ стал реализовывать функцию из множества $M_2$ от своих входов. Более конкретно, если $\varphi_E\in M_2$, то пусть элемент $E$ исправен, а если $\varphi_E\in L_2$, то пусть он неисправен и реализует функцию $\psi'_E(x_1,x_2)$ от своих входов, которая отличается от функции $\varphi_E(x_1,x_2)$ ровно на одном наборе и, следовательно, принимает значение $1$ ровно на одном или трех наборах, т.е. принадлежит $M_2$. Будем считать, что состояние всех остальных элементов схемы $S_0$ не изменилось. Тогда, в частности, не изменились булевы функции, подаваемые в схеме на входы элемента $E$. Набор $(\alpha_E,\beta_E)$, на котором значения функций $\varphi_E(x_1,x_2)$ и $\psi'_E(x_1,x_2)$ различаются, для краткости обозначим через $(\alpha,\beta)$. Докажем, что на входы схемы $S_0$ вместо переменных $x$ и $y$ можно подать такие значения, чтобы на входы элемента $E$ поступил набор $(\alpha,\beta)$. Возможны шесть случаев.

1. Выполняются равенства $h_1=x\oplus a_1$ и $h_2=y\oplus a_2$. Тогда при подаче на входы схемы $S_0$ вместо переменной $x$ значения $a_1\oplus\alpha$, а вместо переменной $y$ значения $a_2\oplus\beta$ на входы элемента $E$ с учетом равенств $(a_1\oplus\alpha)\oplus a_1=\alpha$, $(a_2\oplus\beta)\oplus a_2=\beta$ поступит набор $(\alpha,\beta)$.

2. Выполняются равенства $h_1=y\oplus a_2$ и $h_2=x\oplus a_1$. Тогда при подаче на входы схемы $S_0$ вместо переменной $x$ значения $a_1\oplus\beta$, а вместо переменной $y$ значения $a_2\oplus\alpha$ на входы элемента $E$ с учетом равенств $(a_2\oplus\alpha)\oplus a_2=\alpha$, $(a_1\oplus\beta)\oplus a_1=\beta$ поступит набор $(\alpha,\beta)$.

3. Выполняются равенства $h_1=x\oplus a_1$ и $h_2=x\oplus y\oplus a_3$. Тогда при подаче на входы схемы $S_0$ вместо переменной $x$ значения $a_1\oplus\alpha$, а вместо переменной $y$ значения $a_1\oplus\alpha\oplus a_3\oplus\beta$ на входы элемента $E$ с учетом равенств $(a_1\oplus\alpha)\oplus a_1=\alpha$,

4. Выполняются равенства $h_1=x\oplus y\oplus a_3$ и $h_2=x\oplus a_1$. Тогда при подаче на входы схемы $S_0$ вместо переменной $x$ значения $a_1\oplus\beta$, а вместо переменной $y$ значения $a_1\oplus\alpha\oplus a_3\oplus\beta$ на входы элемента $E$ с учетом равенств $(a_1\oplus\beta)\oplus a_1=\beta$,

5. Выполняются равенства $h_1=y\oplus a_2$ и $h_2=x\oplus y\oplus a_3$. Тогда при подаче на входы схемы $S_0$ вместо переменной $y$ значения $a_2\oplus\alpha$, а вместо переменной $x$ значения $a_2\oplus\alpha\oplus a_3\oplus\beta$ на входы элемента $E$ с учетом равенств $(a_2\oplus\alpha)\oplus a_2=\alpha$,

6. Выполняются равенства $h_1=x\oplus y\oplus a_3$ и $h_2=y\oplus a_2$. Тогда при подаче на входы схемы $S_0$ вместо переменной $y$ значения $a_2\oplus\beta$, а вместо переменной $x$ значения $a_2\oplus\alpha\oplus a_3\oplus\beta$ на входы элемента $E$ с учетом равенств $(a_2\oplus\beta)\oplus a_2=\beta$,

Тем самым доказано, что на входы схемы $S_0$ вместо переменных $x$ и $y$ можно подать такие значения, чтобы на входы элемента $E$ поступил набор $(\alpha,\beta)$, что мы и сделаем. В силу соотношения $\varphi_E(\alpha,\beta)\ne\psi'_E(\alpha,\beta)$ изменение состояния элемента $E$ с исправного на неисправное или наоборот приведет к изменению значения на его выходе. Все остальные элементы схемы $S_0$ реализуют линейные булевы функции от своих входов. С учетом этого нетрудно заметить, что изменение значения на выходе элемента $E$ приведет к прибавлению такого числа единиц по модулю $2$ к значению, возникающему на выходе элемента $E_{\mathrm{out}}$, т.е. на выходе схемы $S_0$, сколько в ней есть существенных путей, соединяющих элемент $E$ с выходом элемента $E_{\mathrm{out}}$ (формально это можно доказать индукцией по длине самого длинного существенного пути, соединяющего элемент $E$ с выходом какого-либо элемента схемы $S_0$, где под длиной пути понимается число содержащихся в нем функциональных элементов). Указанное число существенных путей по определению равно степени элемента $E$ и нечетно в силу выбора данного элемента, поэтому изменение состояния элемента $E$ с исправного на неисправное или наоборот приведет к прибавлению нечетного числа единиц по модулю $2$ к значению, возникающему на выходе схемы $S_0$, откуда следует, что это значение изменится на противоположное. В итоге получаем, что при подаче на входы схемы $S_0$ некоторых значений изменение состояния элемента $E$ с исправного на неисправное или наоборот приводит к изменению значения на выходе схемы, что невозможно, так как схема $S_0$ является самокорректирующейся. Полученное противоречие означает, что исходное предположение было неверно и каждый двухвходовой элемент схемы $S_0$, на входы которого в этой схеме подаются функции двух из трех видов $x\oplus a_1$, $y\oplus a_2$, $x\oplus y\oplus a_3$, где $a_1,a_2,a_3\in\{0,1\}$, при нахождении схемы в $L$-состоянии имеет четную степень.

Преобразуем схему $S_0$, находящуюся в $L$-состоянии, следующим образом: каждый элемент схемы, реализующий функцию $x_1\oplus x_2\oplus 1$, $\overline x_1$, $\overline x_2$ или $1$ от своих входов, заменим на функциональный элемент с тем же числом и наименованием входов, реализующий функцию соответственно $x_1\oplus x_2$, $x_1$, $x_2$ или $0$ от своих входов, и поставим в соответствие заменяющий элемент заменяемому; все остальные элементы поставим в соответствие сами себе. Полученную схему из функциональных элементов обозначим через $S'_0$. Очевидно, что множество существенных путей в схеме при этом не изменится, следовательно, степень каждого элемента схемы $S'_0$ совпадает со степенью соответствующего элемента схемы $S_0$. Ясно также, что каждый элемент схемы $S'_0$ реализует функцию из множества $\{0,x_1,x_2,x_1\oplus x_2\}$. Кроме того, легко видеть, что при преобразовании схемы $S_0$ в схему $S'_0$ для каждого элемента схемы $S_0$ к функции, реализуемой этим элементом от своих входов, прибавляется по модулю $2$ одна из констант $0$ или $1$. Тогда, последовательно двигаясь от входов схемы к ее выходу, нетрудно получить, что для каждого элемента схемы $S'_0$ функция, реализуемая на выходе этого элемента в данной схеме, получается из функции, реализуемой на выходе соответствующего ему элемента в схеме $S_0$, прибавлением по модулю $2$ нуля или единицы (формально это утверждение можно доказать индукцией по номеру элемента схемы $S'_0$ при некоторой монотонной нумерации ее элементов последовательными натуральными числами). В частности, на выходе выходного элемента схемы $S'_0$, т.е. на выходе этой схемы, реализуется функция, получающаяся из функции, реализуемой на выходе элемента $E_{\mathrm{out}}$ в схеме $S_0$ и равной $x\oplus y\oplus c$, прибавлением по модулю $2$ нуля или единицы. Таким образом, схема $S'_0$ реализует одну из функций $x\oplus y$, $x\oplus y\oplus 1$. Более конкретно, это функция $x\oplus y$, так как при подаче на входы схемы $S'_0$ вместо переменных $x$ и $y$ нулей на выходе каждого элемента этой схемы, в том числе выходного, возникает значение $0$. Из последнего рассуждения с учетом линейности всех функций из множества $\{0,x_1,x_2,x_1\oplus x_2\}$ вытекает также, что в схеме $S'_0$ на выходе каждого элемента реализуется одна из функций $0,x,y,x\oplus y$.

Как было показано выше, степень каждого элемента схемы $S'_0$ совпадает со степенью соответствующего элемента схемы $S_0$. Тогда схема $S'_0$ обладает следующим свойством $(*)$: каждый ее двухвходовой элемент, на входы которого в этой схеме подаются две из трех функций $x$, $y$ и $x\oplus y$, имеет четную степень.

Удалим теперь все несущественные входы элементов из схемы $S'_0$. А именно, преобразуем ее следующим образом:

1) удалим из схемы каждый элемент, имеющий один или два входа и реализующий константу $0$ от своих входов, а на каждый вход каждого элемента, соединявшийся с выходом удаляемого элемента, подадим константу $0$ со входа схемы;

2) заменим в схеме каждый двухвходовой элемент, реализующий функцию $x_1$ или $x_2$ от своих входов, на одновходовой элемент, реализующий функцию $x_1$ от своего входа; соединим этот вход с тем узлом схемы (ее входом или выходом ее элемента), который соединялся со входом соответственно $x_1$ или $x_2$ заменяемого элемента, и поставим в соответствие заменяющий элемент заменяемому;

3) все остальные элементы поставим в соответствие сами себе.

Полученную схему из функциональных элементов обозначим через $S_1$. Легко видеть, что

Опишем алгоритм преобразования схемы $S_1$ в схему $S'$. Перед началом алгоритма считаем, что $k=1$, а перед началом шага $k$ алгоритма – что определена схема из функциональных элементов $S_k$, каждый элемент которой имеет не более двух входов и реализует функцию из множества $L_2$ от своих входов.

Шаг $k$ алгоритма. Рассмотрим семь случаев.

1. Пусть в схеме $S_k$ содержится хотя бы один двухвходовой элемент четной степени, на выходе которого в этой схеме реализуется функция $x$ или $y$. Произвольный такой элемент обозначим через $E_k$. Удалим из схемы элемент $E_k$ (вместе со входящими в него ребрами), а на каждый вход каждого элемента, соединявшийся с выходом элемента $E_k$, подадим переменную соответственно $x$ или $y$ со входа схемы.

2. Пусть случай 1 не выполнен, но в схеме $S_k$ содержатся хотя бы два двухвходовых элемента четной степени, на выходе каждого из которых в этой схеме реализуется функция $x\oplus y$. Рассмотрим произвольные два таких элемента. Среди них хотя бы один элемент, который мы обозначим через $E'_k$, расположен в схеме не ниже другого элемента, который мы обозначим через $E_k$. Удалим из схемы элемент $E_k$, а каждый вход каждого элемента, соединявшийся с выходом элемента $E_k$, соединим вместо этого с выходом элемента $E'_k$.

3. Пусть случаи 1, 2 не выполнены, но в схеме $S_k$ содержится хотя бы один двухвходовой элемент, оба входа которого соединены с одним и тем же узлом схемы (ее входом или выходом ее элемента). Произвольный такой элемент обозначим через $E_k$. Удалим из схемы элемент $E_k$, а на каждый вход каждого элемента, соединявшийся с выходом элемента $E_k$, подадим константу $0$ со входа схемы.

4. Пусть случаи 1–3 не выполнены, но в схеме $S_k$ содержится хотя бы один элемент без входов, реализующий константу $0$. Произвольный такой элемент обозначим через $E_k$. Удалим из схемы элемент $E_k$, а на каждый вход каждого элемента, соединявшийся с выходом элемента $E_k$, подадим константу $0$ со входа схемы.

5. Пусть случаи 1–4 не выполнены, но в схеме $S_k$ содержится хотя бы один одновходовой элемент, реализующий функцию $x_1$ от своего входа. Произвольный такой элемент обозначим через $E_k$, а его вход – через $v$. Удалим из схемы элемент $E_k$, а каждый вход каждого элемента, соединявшийся с выходом элемента $E_k$, соединим вместо этого с тем узлом схемы, который соединялся со входом элемента $E_k$. Если $E_k$ являлся выходным элементом схемы, а его вход $v$ соединялся с выходом некоторого элемента $E'_k$, то назовем это подслучаем 5.1 и перенесем выход схемы на выход элемента $E'_k$; противоположный подслучай назовем подслучаем 5.2.

6. Пусть случаи 1–5 не выполнены, но в схеме $S_k$ содержится хотя бы один двухвходовой элемент, на один из входов которого подается константа $0$ со входа схемы. Произвольный такой элемент обозначим через $E_k$. Удалим из схемы элемент $E_k$, а каждый вход каждого элемента, соединявшийся с выходом элемента $E_k$, соединим вместо этого с тем узлом схемы, который соединялся с другим входом элемента $E_k$; обозначим указанный вход через $v$. Если $E_k$ являлся выходным элементом схемы, а его вход $v$ соединялся с выходом некоторого элемента $E'_k$, то назовем это подслучаем 6.1 и перенесем выход схемы на выход элемента $E'_k$; противоположный подслучай назовем подслучаем 6.2.

В каждом из случаев 1–6 схему, полученную после удаления элемента $E_k$ и, возможно, переноса выхода схемы с выхода этого элемента на выход элемента $E'_k$, обозначим через $S_{k+1}$ и увеличим $k$ на единицу.

7. Если не выполнен ни один из случаев 1–6, то остановим алгоритм.

Число элементов в схеме $S_1$ конечно, поэтому алгоритм остановится через конечное число $N$ шагов. Будем считать, что схема $S'$ совпадает со схемой $S_N$.

Нетрудно видеть, что при $N\geqslant 2$ для любого $k\in\{1,\dots,N-1\}$ удаление элемента $E_k$ из схемы $S_k$ не изменяет функций, подаваемых в схеме на входы ее оставшихся элементов (формально это можно доказать индукцией по номеру элемента схемы $S_k$, отличного от элемента $E_k$, при некоторой монотонной нумерации ее элементов последовательными натуральными числами). Таким образом, выполнено следующее утверждение $(**)$: на входы каждого элемента схемы $S_1$, кроме элементов $E_1,\dots,E_{N-1}$ (т.е. тех элементов, которые были удалены при преобразовании схемы $S_1$ в схему $S_N$), подаются те же булевы функции, что и на соответствующие входы этого же элемента в схеме $S_N$. Также легко заметить, что если $E_k$ является выходным элементом схемы $S_k$ и выполнен один из подслучаев 5.1, 6.1, то функции, реализуемые в данной схеме на выходах элементов $E'_k$ и $E_k$, совпадают. Из приведенных рассуждений следует, что если не выполнено хотя бы одно из двух условий:

(i) элемент $E_k$ является выходным элементом схемы $S_k$;

(ii) на шаге $k$ алгоритма выполнен один из случаев 1–4, 5.2, 6.2,

то на выходах схем $S_k$ и $S_{k+1}$ реализуются одинаковые булевы функции. Предположим, что для какого-то $k\in\{1,\dots,N-1\}$ условия (i) и (ii) выполняются одновременно. Среди всех таких $k$ выберем наименьшее. Тогда на выходах схем $S_1,\dots,S_k$ реализуются одинаковые булевы функции, равные $x\oplus y$. В силу условия (i) элемент $E_k$ схемы $S_k$ имеет нечетную степень, равную единице, поэтому на шаге $k$ алгоритма случай 2 выполняться не может. Согласно описанию случаев 1, 3, 4, на выходе элемента $E_k$ в схеме $S_k$ в случае 1 реализуется функция $x$ или $y$, а в каждом из случаев 3, 4 – константа $0$; если на шаге $k$ алгоритма выполнен подслучай 5.2 или 6.2, то с учетом выполнения условия (i) получаем, что вход $v$ элемента $E_k$ соединен в схеме $S_k$ с каким-то входом схемы и на выходе данного элемента в ней реализуется одна из функций $x,y,0$. Тогда в силу условия (i) на выходе схемы $S_k$ реализуется одна из функций $x,y,0$, каждая из которых отлична от функции $x\oplus y$. Полученное противоречие означает, что ни для какого $k\in\{1,\dots,N-1\}$ условия (i) и (ii) не могут выполняться одновременно, а тогда на выходах схем $S_1,\dots,S_N$ реализуются одинаковые булевы функции, равные $x\oplus y$. Тем самым доказано, что схема $S_N$ реализует функцию $x\oplus y$.

Пусть $N\geqslant 2$. Рассмотрим произвольное $k\in\{1,\dots,N-1\}$ и произвольный элемент $\widehat E$ схемы $S_k$, отличный от элемента $E_k$. Докажем, что применение шага $k$ алгоритма не изменяет четности степени элемента $\widehat E$. Для любого элемента $E^{(1)}$ схемы $S_k$ через $d_{E^{(1)}}$ обозначим степень этого элемента, а для любых двух элементов $E^{(1)}$ и $E^{(2)}$ схемы $S_k$ через $n_{E^{(1)},E^{(2)}}$ обозначим число различных существенных путей в схеме, соединяющих элементы $E^{(1)}$ и $E^{(2)}$ и ориентированных в сторону элемента $E^{(2)}$. Пусть $P_1$ ($P_2$) – множество всевозможных существенных путей, соединяющих элемент $\widehat E$ с выходом схемы $S_k$ и не проходящих (соответственно проходящих) через элемент $E_k$. Ясно, что $d_{\widehat E}=|P_1|+|P_2|$. Легко также видеть, что любой путь из множества $P_1$ останется существенным путем, соединяющим элемент $\widehat E$ с выходом схемы, и после удаления из нее элемента $E_k$ в результате применения шага $k$ алгоритма (если $E_k$ – выходной элемент схемы $S_k$, то $P_1=\varnothing$).

Пусть на шаге $k$ алгоритма выполнен случай 1. Тогда выполнено условие (ii), значит, условие (i) выполняться не может. Каждый путь из множества $P_2$ можно разбить на два участка: от элемента $\widehat E$ до элемента $E_k$ и от элемента $E_k$ до выхода схемы $S_k$. Поэтому мощность множества $P_2$ равна $n_{\widehat E,E_k}\cdot d_{E_k}$. Число $d_{E_k}$ четно в силу описания случая 1, значит, и число $|P_2|$ четно. Удаление из схемы элемента $E_k$ приведет к удалению из множества всевозможных существенных путей, соединяющих элемент $\widehat E$ с выходом схемы, всех путей из множества $P_2$. Следовательно, степень элемента $\widehat E$ изменится при этом с $|P_1|+|P_2|$ на $|P_1|$, и ее четность сохранится.

Пусть на шаге $k$ алгоритма выполнен случай 2. Тогда выполнено условие (ii), значит, условие (i) выполняться не может. Дословно повторяя рассуждения из предыдущего абзаца с заменой случая 1 на случай 2, получаем, что число $|P_2|$ четно. Множество $P_1$ разобьем на два непересекающихся подмножества $P'_1$ и $P''_1$: к $P'_1$ ($P''_1$) отнесем все пути из множества $P_1$, проходящие (соответственно не проходящие) через элемент $E'_k$. Тогда $d_{\widehat E}=|P'_1|+|P''_1|+|P_2|$. Каждый путь из множества $P'_1$ можно разбить на два участка: от элемента $\widehat E$ до элемента $E'_k$ и от элемента $E'_k$ до выхода схемы $S_k$. Поэтому мощность множества $P'_1$ равна $n_{\widehat E,E'_k}\cdot d_{E'_k}$ и $d_{\widehat E}=n_{\widehat E,E'_k}\cdot d_{E'_k}+|P''_1|+|P_2|$. Удаление из схемы элемента $E_k$ приведет к удалению из множества всевозможных существенных путей, соединяющих элемент $\widehat E$ с выходом схемы, всех путей из множества $P_2$. Отсоединение всех входов элементов, соединявшихся с выходом элемента $E_k$, и последующее соединение этих входов с выходом элемента $E'_k$ приведет к изменению степени элемента $E'_k$ с $d_{E'_k}$ до $d_{E'_k}+d_{E_k}$ (для каждого существенного пути, соединявшего элемент $E_k$ с выходом схемы, возникнет новый, соответствующий данному пути, существенный путь, соединяющий элемент $E'_k$ с выходом полученной схемы). По аналогии с установлением равенства $|P'_1|=n_{\widehat E,E'_k}\cdot d_{E'_k}$ можно показать, что мощность “нового” множества $P'_1$, т.е. число существенных путей в полученной схеме, соединяющих элемент $\widehat E$ с ее выходом и проходящих через элемент $E'_k$, равна $n_{\widehat E,E'_k}\cdot(d_{E'_k}+d_{E_k})$. Нетрудно видеть, что множество $P''_1$ при применении шага $k$ алгоритма в случае 2 не изменится (достаточно для любого пути из $P''_1$ последовательно рассмотреть элементы, через которые проходит этот путь при движении от элемента $\widehat E$ к выходу схемы). С учетом вышесказанного получаем, что степень элемента $\widehat E$ изменится с $n_{\widehat E,E'_k}\cdot d_{E'_k}+|P''_1|+|P_2|$ до $n_{\widehat E,E'_k}\cdot(d_{E'_k}+d_{E_k})+|P''_1|$. Имеем

Пусть на шаге $k$ алгоритма выполнен случай 3. Тогда выполнено условие (ii), значит, условие (i) выполняться не может. Удаление из схемы элемента $E_k$ приведет к удалению из множества всевозможных существенных путей, соединяющих элемент $\widehat E$ с выходом схемы, всех путей из множества $P_2$. Степень элемента $\widehat E$ изменится при этом с $|P_1|+|P_2|$ на $|P_1|$. Достаточно доказать, что число $|P_2|$ четно. В случае $P_2=\varnothing$ утверждение очевидно. Пусть $P_2\ne\varnothing$. Тогда в схеме $S_k$ есть хотя бы один существенный путь, соединяющий элемент $\widehat E$ с элементом $E_k$. В таком случае тот узел схемы $S_k$, с которым соединены оба входа элемента $E_k$, не может быть входом схемы, поэтому он является выходом некоторого элемента $\widehat E'$ (элементы $\widehat E$ и $\widehat E'$ могут совпадать). Каждый путь из множества $P_2$ проходит через какой-то вход элемента $E_k$ и, как следствие, через элемент $\widehat E'$, и этот путь можно разбить на три участка: от элемента $\widehat E$ до элемента $\widehat E'$, от элемента $\widehat E'$ до элемента $E_k$ и от элемента $E_k$ до выхода схемы $S_k$. Поэтому мощность множества $P_2$ равна $n_{\widehat E,\widehat E'}\cdot n_{\widehat E',E_k}\cdot d_{E_k}$. Очевидно, $n_{\widehat E',E_k}=2$, следовательно, число $|P_2|$ четно, что и требовалось доказать.

Пусть на шаге $k$ алгоритма выполнен случай 4. Тогда выполнено условие (ii), значит, условие (i) выполняться не может. Удаление из схемы элемента $E_k$ приведет к удалению из множества всевозможных существенных путей, соединяющих элемент $\widehat E$ с выходом схемы, всех путей из множества $P_2$, которое пусто, так как элемент $E_k$ не имеет входов. Следовательно, степень элемента $\widehat E$ изменится при этом с $|P_1|+|P_2|=|P_1|$ на $|P_1|$, и ее четность сохранится.

Пусть на шаге $k$ алгоритма выполнен случай 5. Если вход $v$ элемента $E_k$ соединен в схеме $S_k$ с каким-то входом схемы, то очевидно, что в ней не может быть существенных путей, соединяющих элемент $\widehat E$ с элементом $E_k$, и удаление из схемы элемента $E_k$ не изменит множества существенных путей, соединяющих элемент $\widehat E$ с выходом схемы, которое останется равным $P_1$, поэтому четность степени элемента $\widehat E$ сохранится. Пусть вход $v$ элемента $E_k$ соединен в схеме $S_k$ с выходом какого-то элемента $\widehat E'$ (элементы $\widehat E$ и $\widehat E'$ могут совпадать). Каждый путь из множества $P_2$ проходит через вход $v$ элемента $E_k$ и, как следствие, через элемент $\widehat E'$, и этот путь можно разбить на три участка: от элемента $\widehat E$ до элемента $\widehat E'$, от элемента $\widehat E'$ до элемента $E_k$ и от элемента $E_k$ до выхода схемы $S_k$. Поэтому мощность множества $P_2$ равна $n_{\widehat E,\widehat E'}\cdot n_{\widehat E',E_k}\cdot d_{E_k}$. Очевидно, $n_{\widehat E',E_k}=1$, следовательно, $|P_2|=n_{\widehat E,\widehat E'}\cdot d_{E_k}$. Удаление из схемы элемента $E_k$ приведет к удалению из указанного пути участка от элемента $\widehat E'$ до элемента $E_k$. Отсоединение всех входов элементов, соединявшихся с выходом элемента $E_k$, и последующее соединение этих входов с выходом элемента $\widehat E'$ приведет к замене участка указанного пути от элемента $E_k$ до выхода схемы на соответствующий участок от элемента $\widehat E'$ до выхода схемы. Число различных существенных путей, соединяющих элемент $\widehat E$ с выходом схемы, т.е. степень данного элемента, при этом не изменится. Таким образом, четность степени элемента $\widehat E$ сохранится.

Пусть на шаге $k$ алгоритма выполнен случай 6. Дословно повторяя рассуждения из предыдущего абзаца, получаем, что при применении этого шага четность степени элемента $\widehat E$ сохранится.

Тем самым доказано, что применение шага $k$ алгоритма не изменяет четности степени элемента $\widehat E$. В силу произвольности выбора числа $k\in\{1,\dots,N-1\}$ и элемента $\widehat E$ схемы $S_k$ отсюда следует, что четность степени каждого элемента схемы $S_1$, кроме элементов $E_1,\dots,E_{N-1}$ (т.е. тех элементов, которые были удалены при преобразовании схемы $S_1$ в схему $S_N$), совпадает с четностью степени этого же элемента в схеме $S_N$. Как было показано выше, схема $S_1$ обладает свойством $(*)$, а для схем $S_1$ и $S_N$ выполнено утверждение $(**)$, следовательно, схема $S_N$ также обладает свойством $(*)$.

Далее считаем, что на число $N$ не наложено дополнительного условия $N\geqslant 2$. Рассмотрим произвольный верхний элемент $E$ схемы $S_N$, выше которого в данной схеме не содержится ни одного элемента; это можно сделать, так как схема $S_N$ конечна и не содержит ориентированных циклов. Пусть $k=N$. Для схемы $S_k$ выполнен случай 7, т.е. не выполнен ни один из случаев 1–6. Если элемент $E$ не имеет входов, то он обязательно реализует константу $0$ и для схемы $S_k$ выполнен случай 4, что невозможно. Если элемент $E$ имеет ровно один вход, то он обязательно реализует функцию $x_1$ от своего входа и для схемы $S_k$ выполнен случай 5, что невозможно. Значит, элемент $E$ имеет ровно два входа. Тогда он обязательно реализует функцию $x_1\oplus x_2$ от своих входов и оба его входа соединены со входами схемы. В силу невыполнения случаев 3 и 6 из описания шага $k$ алгоритма на один вход элемента $E$ подается переменная $x$, а на другой – переменная $y$ со входов схемы. Тогда по свойству $(*)$ схемы $S_k$ элемент $E$ имеет четную степень. Предположим, что в этой схеме содержится хотя бы один элемент, отличный от $E$. Среди всех таких элементов выберем произвольный верхний элемент $E'$. Так же, как для элемента $E$, доказывается, что элемент $E'$ имеет ровно два входа и реализует функцию $x_1\oplus x_2$ от своих входов. Может выполняться один из трех случаев.

Случай А. Оба входа элемента $E'$ соединены со входами схемы $S_k$. Рассуждая по аналогии с предыдущим абзацем, получаем, что а) на один вход элемента $E'$ подается переменная $x$, а на другой – переменная $y$ со входов схемы; б) элемент $E'$ имеет четную степень. Тогда на выходе каждого из элементов $E,E'$ в схеме $S_k$ реализуется функция $x\oplus y$ и каждый из этих элементов имеет четную степень, т.е. для схемы $S_k$ выполнен случай 2, что невозможно.

Случай Б. Оба входа элемента $E'$ соединены с выходом элемента $E$. Тогда для схемы $S_k$ выполнен случай 3, что невозможно.

Случай В. Один вход элемента $E'$ соединен со входом схемы $S_k$, а другой – с выходом элемента $E$. Обозначим входы элемента $E'$ в указанном порядке через $v_1$ и $v_2$ соответственно. Если на вход $v_1$ подается константа $0$, то для схемы $S_k$ выполнен случай 6, что невозможно. Поэтому на вход $v_1$ подается одна из функций $x,y$, а на вход $v_2$ – функция $x\oplus y$ с выхода элемента $E$. В таком случае по свойству $(*)$ схемы $S_k$ элемент $E'$ имеет четную степень, а на его выходе в этой схеме реализуется либо функция $x\oplus(x\oplus y)=y$, либо функция $y\oplus(x\oplus y)=x$. Следовательно, для схемы $S_k$ выполнен случай 1, что невозможно.

Тем самым показано, что исходное предположение было неверно и единственным элементом, содержащимся в схеме $S_k$, является $E$. На выходе данной схемы реализуется функция $x\oplus y$, поэтому выход схемы $S_k$ обязан совпадать с выходом элемента $E$. Но тогда степень элемента $E$ равна единице, что противоречит четности этой степени. Полученное противоречие доказывает теорему 1.

3. Заключение

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

1. Введение

2. Формулировка и доказательство основного результата

3. Заключение

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ