| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Короткие полные диагностические тесты для схем, реализующих линейные булевы функции К. А. Попков Институт прикладной математики им. М.В. Келдыша Российской академии наук, г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 1, Pages DOI: https://doi.org/10.1134/S0001434623010091 
Реферативные базы данных:
  1. ВведениеВ работе рассматривается задача синтеза легкотестируемых схем из функциональных элементов (СФЭ), реализующих заданные булевы функции (см. [1]–[3]). Пусть имеется СФЭ $S$ с одним выходом, реализующая булеву функцию $f(\widetilde x^{\,n})$, где $n\in\mathbb N$ и $\widetilde x^{\,n}=(x_1,\dots,x_n)$. Предположим, что в схеме $S$ могут происходить константные неисправности на выходах элементов, при которых значение на выходе любого неисправного элемента становится равно некоторой булевой константе; число неисправных элементов в схеме предполагается произвольным. В результате схема $S$ вместо исходной функции $f(\widetilde x^{\,n})$ будет реализовывать какие-то, вообще говоря, отличные от нее булевы функции, называемые функциями неисправности данной схемы. Через $M(S)$ будем обозначать множество, состоящее из функции $f(\widetilde x^{\,n})$ и всех функций неисправности схемы $S$. Константные неисправности на выходах элементов называются однотипными константными, если на выходе каждого неисправного элемента реализуется одна и та же заранее заданная булева константа (определяющая тип этих неисправностей), и произвольными константными, если на выходе каждого неисправного элемента реализуется одна из булевых констант $0$ или $1$ независимо от неисправностей других элементов. Полным диагностическим тестом (ПДТ) для схемы $S$ называется такое множество $T$ наборов значений переменных $x_1,\dots,x_n$, что для любой отличной от $f(\widetilde x^{\,n})$ функции неисправности $g(\widetilde x^{\,n})$ схемы $S$ в $T$ найдется набор $\widetilde\sigma$, на котором $f(\widetilde\sigma)\ne g(\widetilde\sigma)$, а для любых двух различных функций неисправности $g_1(\widetilde x^{\,n})$ и $g_2(\widetilde x^{\,n})$ схемы $S$ в $T$ найдется набор $\widetilde\pi$, на котором $g_1(\widetilde\pi)\ne g_2(\widetilde\pi)$. Число наборов в $T$ называется длиной теста. В качестве тривиального ПДТ длины $2^n$ для схемы $S$ всегда можно взять множество, состоящее из всех $2^n$ двоичных наборов длины $n$. Пусть зафиксированы базис $B$, в котором строятся схемы, и вид допустимых неисправностей элементов в схемах. Введем следующие обозначения:
Если базис $B$ является функционально полным, то введем также обозначение $D^B(n)=\max D^B(f)$, где максимум берется по всем булевым функциям $f$ от $n$ переменных. Функция $D^B(n)$ называется функцией Шеннона длины ПДТ. Для удобства под буквой $D$ будем ставить символы “$01$”, “$0$” или “$1$” в случаях, когда в схемах допускаются произвольные константные неисправности, однотипные константные неисправности типа 0 или типа 1 на выходах элементов соответственно. Всюду далее в данном разделе будем считать, что $n$ – произвольное натуральное число. Положим $l_n(\widetilde x^{\,n})=x_1\oplus\dots\oplus x_n$, $\overline l_n(\widetilde x^{\,n})=x_1\oplus\dots\oplus x_n\oplus 1$. Очевидно, что $l_n$ и $\overline l_n$ – единственные линейные булевы функции, существенно зависящие в точности от переменных $x_1,\dots,x_n$. Редькин в [4] для любой булевой функции $f(\widetilde x^{\,n})$, существенно зависящей от всех своих переменных, доказал неравенства
$$
\begin{equation*}
D^{B_0}_0(f)\leqslant\min(N_1(f),1+N_0(f)),\qquad D^{B_0}_1(f)\leqslant\min(N_0(f),1+N_1(f)),
\end{equation*}
\notag
$$
где $B_0=\{\&,\vee,\neg\}$ – стандартный (классический) базис, а $N_\alpha(f)$ – число наборов, на которых функция $f(\widetilde x_n)$ принимает значение $\alpha$ ($\alpha=0,1$). Нетрудно заметить, что в случаях $f=l_n$ и $f=\overline l_n$ каждое из выражений $\min(N_1(f),1+N_0(f))$, $\min(N_0(f),1+N_1(f))$ принимает максимально возможное значение, равное $2^{n-1}$. Тем самым в указанных случаях верхние оценки величин $D^{B_0}_0(f)$ и $D^{B_0}_1(f)$, найденные в [4], лишь в два раза меньше тривиальной верхней оценки $2^n$. В теореме 3 настоящей работы эти оценки понижены до $n$. В работе автора [5] установлены неравенства
$$
\begin{equation*}
D^{\mathtt B_1}_1(n)>\frac{2^{n/2}\cdot\sqrt[4]{n}} {2\sqrt{n+(1/2)\log n+2}}\,,\quad D^{\mathtt B_2}_{01}(n)>\frac{2^{n/2}\cdot\sqrt[4]{n}} {2\sqrt{n+(1/2)\log n+2}}\,,
\end{equation*}
\notag
$$
где $\mathtt B_1=\{\overline{x\&y}\}$ и $\mathtt B_2=\{x\&y,\overline x\}$. Х. Фудзивара доказал [6; теорема 7], что минимально возможная длина ПДТ для СФЭ в базисе $\{x\oplus y\}$, реализующих функцию $l_n$, при произвольных константных неисправностях на выходах элементов и на входах схем равна $n+1$. В теореме 1 настоящей работы, в частности, установлено, что при рассмотрении произвольных константных неисправностей только на выходах элементов верхнюю оценку $n+1$ можно понизить до $\lceil\log_2 n\rceil+1$. В [7], [8] для любой булевой функции $f(\widetilde x^{\,n})$ получены верхние оценки $1$ и $2$ минимально возможных длин ПДТ для реализующих ее СФЭ в базисах соответственно $\{x_1\&\dots\&x_t,x\oplus y,1\mid t=2,3,4,\dots\}$ и $\{x\&y\&z,x\oplus y,1\}$ при инверсных неисправностях на выходах элементов, при которых значение на выходе любого неисправного элемента становится противоположным значению на этом выходе в случае, когда элемент исправен. Г. В. Антюфеев и Д. С. Романов доказали [9; теорема 3] существование такой булевой функции $f(\widetilde x^{\,n})$, что длина любого ПДТ для любой реализующей ее СФЭ при произвольных константных неисправностях на входах схем асимптотически не меньше $2^{\lfloor n/2\rfloor+1}$. В работах автора [10], [11] рассматривались ПДТ для СФЭ, моделирующих булевы функции с одним или двумя дополнительными входами, при однотипных константных неисправностях на выходах элементов. Тесты (но не ПДТ) для схем, реализующих линейные булевы функции, в различных базисах при различных неисправностях элементов исследовались в работах [3; с. 128–130], [12], [13]. ПДТ для контактных схем при константных неисправностях (обрывах и/или замыканиях) контактов рассматривались в статьях [14], [15]; упомянем также работу автора [16]. 2. Диагностические тесты для некоторых множеств линейных функцийДиагностическим тестом (ДТ) для множества булевых функций, зависящих от переменных $x_1,\dots,x_n$, назовем такое множество $T$ двоичных $n$-разрядных наборов, что для любых двух различных функций $f_1(\widetilde x^{\,n})$ и $f_2(\widetilde x^{\,n})$ из этого множества в $T$ найдется набор $\widetilde\sigma$, на котором $f_1(\widetilde\sigma)\ne f_2(\widetilde\sigma)$. Пусть зафиксированы допустимые неисправности функциональных элементов в схемах. Из определений вытекает, что множество $T$ является ПДТ для схемы $S$ тогда и только тогда, когда $T$ – ДТ для множества $M(S)$. Для каждого содержащегося в формулировке одной из нижеследующих лемм 1–4 множества $M$ булевых функций в доказательстве теоремы 1 и/или теоремы 2, представленном в разделе “Формулировки и доказательства основных результатов”, будет рассмотрена такая СФЭ $S$, что $M(S)=M$. Поэтому из верхней оценки мощности ДТ для множества $M$ будет следовать такая же верхняя оценка длины ПДТ для схемы $S$. Лемма 1. Пусть $p\in\{0,1\}$, $n\geqslant 2$, $g_{p,i}(\widetilde x^{\,n})= x_{i+1}\oplus\dots\oplus x_n\oplus p$ для каждого $i=1,\dots,n-1$ и $g_{p,n}(\widetilde x^{\,n})\equiv p$. Тогда для множества $\{\overline l_n,g_{p,1},\dots,g_{p,n}\}$ существует ДТ мощности не более $\lceil\log_2(n+1)\rceil$. Доказательство. Введем для удобства обозначение $g_{p,0}=\overline l_n$. Занумеруем разряды произвольного двоичного $n$-разрядного набора слева направо числами $0,1,\dots, n- 1$. Пусть $m=\lceil\log_2(n+1)\rceil$ и $\widetilde\sigma_j$ – такой двоичный $n$-разрядный набор, у которого единицы стоят в точности во всех разрядах с номерами, делящимися на $2^j$, $j=0,\dots,m-1$. Например, если $n=11$, то $m=4$, Обозначим через $\widetilde\sigma_{p,j}$ набор, получающийся из набора $\widetilde\sigma_j$ заменой числа, стоящего в крайнем левом разряде, с $1$ на $p$. Докажем, что $M^n_p=\{g_{p,0},g_{p,1},\dots,g_{p,n}\}$ допускает ДТ $T^n_p=\{\widetilde\sigma_{p,0},\widetilde\sigma_{p,1},\dots, \widetilde\sigma_{p,m-1}\}$. Достаточно доказать, что для любых $i$ и $i'$ из множества $\{0,1,\dots,n\}$, удовлетворяющих условию $i<i'$, функции $g_{p,i}$ и $g_{p,i'}$ можно отличить друг от друга хотя бы на одном из наборов $\widetilde\sigma_{p,0}, \widetilde\sigma_{p,1},\dots,\widetilde\sigma_{p,m-1}$. Пусть $k$ – максимальное такое целое неотрицательное число, что $i'-i$ делится на $2^k$. Тогда
$$
\begin{equation*}
2^k\leqslant i'-i\leqslant n<2^{\log_2(n+1)}\leqslant 2^m,
\end{equation*}
\notag
$$
поэтому $k<m$, т.е. $k\in\{0,\dots,m-1\}$. Докажем, что значение функции $g_{p,i}\oplus g_{p,i'}$ на наборе $\widetilde\sigma_{p,k}$ равно $1$; отсюда будет следовать, что $g_{p,i}(\widetilde\sigma_{p,k})\ne g'_{p,i}(\widetilde\sigma_{p,k})$. В силу определения функций $g_{p,0},g_{p,1},\dots,g_{p,n}$ при $i\geqslant 1$, $i'\leqslant n-1$ имеем
$$
\begin{equation*}
g_{p,i}\oplus g_{p,i'}=(x_{i+1}\oplus\dots\oplus x_n\oplus p)\oplus (x_{i'+1}\oplus\dots\oplus x_n\oplus p)= x_{i+1}\oplus\dots\oplus x_{i'};
\end{equation*}
\notag
$$
при $i\geqslant 1$, $i'=n$ имеем
$$
\begin{equation*}
g_{p,i}\oplus g_{p,i'}=(x_{i+1}\oplus\dots\oplus x_n\oplus p)\oplus p=x_{i+1}\oplus\dots\oplus x_n=x_{i+1}\oplus\dots\oplus x_{i'};
\end{equation*}
\notag
$$
при $i=0$, $i'\leqslant n-1$ имеем
$$
\begin{equation*}
g_{p,i}\oplus g_{p,i'}=(x_1\oplus\dots\oplus x_n\oplus 1)\oplus (x_{i'+1}\oplus\dots\oplus x_n\oplus p)=x_1\oplus\dots\oplus x_{i'}\oplus p\oplus 1;
\end{equation*}
\notag
$$
наконец, при $i=0$, $i'=n$ имеем
$$
\begin{equation*}
g_{p,i}\oplus g_{p,i'}=(x_1\oplus\dots\oplus x_n\oplus 1)\oplus p=x_1\oplus\dots\oplus x_{i'}\oplus p\oplus 1.
\end{equation*}
\notag
$$
Таким образом, функция $g_{p,i}\oplus g_{p,i'}$ равна $x_{i+1}\oplus\dots\oplus x_{i'}$ при $i\geqslant 1$ и равна $x_1\oplus\dots\oplus x_{i'}\oplus p\oplus 1$ при $i=0$. Число $i'-i$ делится на $2^k$, но не делится на $2^{k+1}$, поэтому число $(i'-i)/2^k$ нечетно и представимо в виде $2a+1$, где $a\in\mathbb N\cup\{0\}$. В силу определения наборов $\widetilde\sigma_0,\widetilde\sigma_1,\dots,\widetilde\sigma_{m-1}$ набор $\widetilde\sigma_k$ обладает следующим свойством: среди любых $2^k$ его последовательных разрядов имеется ровно один единичный, значит, сумма по модулю $2$ любых $2^k$ последовательных разрядов набора $\widetilde\sigma_k$ равна $1$. В случае $i\geqslant 1$ значение функции $x_{i+1}\oplus\dots\oplus x_{i'}$ на наборе $\widetilde\sigma_{p,k}$ равно сумме по модулю $2$ некоторых $i'-i=2^k(2a+1)$ его последовательных разрядов, среди которых нет крайнего левого, так как $i+1\geqslant 2$. Следовательно, указанное значение равно сумме по модулю $2$ некоторых $2^k(2a+1)$ последовательных разрядов набора $\widetilde\sigma_k$, т.е. равно сумме $2a+1$ единиц по модулю $2$ и равно $1$. В случае $i=0$ значение функции $x_1\oplus\dots\oplus x_{i'}\oplus p\oplus 1$ на наборе $\widetilde\sigma_{p,k}$ равно сумме по модулю $2$ крайних левых $i'=i'-i=2^k(2a+1)$ его разрядов и числа $p\oplus 1$. Заметим, что сумма по модулю $2$ крайних левых $2^k(2a+1)$ разрядов набора $\widetilde\sigma_k$ равна $1$, а сумма по модулю $2$ крайних левых $2^k(2a+1)$ разрядов набора $\widetilde\sigma_{p,k}$ получается из нее прибавлением $p\oplus 1$ по модулю $2$, так как число, стоящее в крайнем левом разряде, меняется с $1$ на $p$. Тем самым показано, что значение функции $x_1\oplus\dots\oplus x_{i'}\oplus p\oplus 1$ на наборе $\widetilde\sigma_{p,k}$ равно $1\oplus(p\oplus 1)\oplus(p\oplus 1)=1$. В итоге получаем, что значение функции $g_{p,i}\oplus g_{p,i'}$ на наборе $\widetilde\sigma_{p,k}$ равно $1$, что и требовалось доказать. Отсюда вытекает, что $g_{p,i}(\widetilde\sigma_{p,k})\ne g'_{p,i}(\widetilde\sigma_{p,k})$, т.е. функции $g_{p,i}$ и $g_{p,i'}$ можно отличить друг от друга хотя бы на одном из наборов $\widetilde\sigma_{p,0},\widetilde\sigma_{p,1},\dots, \widetilde\sigma_{p,m-1}$ и множество $T^n_p$ является ДТ мощности не более $m=\lceil\log_2(n+1)\rceil$ для множества $M^n_p$. Лемма 1 доказана. Лемма 2. Пусть $n\geqslant 2$, $g_{p,i}(\widetilde x_n)=x_{i+1}\oplus\dots\oplus x_n\oplus p$ для каждых $i=1,\dots,n-1$ и $p=0,1$, $g_{p,n}(\widetilde x^{\,n})\equiv p$ для каждого $p=0,1$. Тогда для множества $\{\overline l_n,g_{0,1},\dots,g_{0,n}, g_{1,1},\dots,g_{1,n}\}$ существует ДТ мощности не более $\lceil\log_2(n+1)\rceil+1$. Доказательство. Введем для удобства обозначение $g_{1,0}=\overline l_n$. В силу леммы 1 для множества $M^n_1=\{g_{1,0},g_{1,1},\dots,g_{1,n}\}$ существует ДТ $T^n_1$ мощности не более $\lceil\log_2(n+1)\rceil$. Докажем, что множество $M^n=\{g_{0,1},\dots,g_{0,n},g_{1,0},g_{1,1},\dots,g_{1,n}\}$ допускает ДТ $T^n=T^n_1\cup\{\widetilde 0^n\}$, где $\widetilde 0^n=(\underbrace{0\dots 0}_n)$. Заметим, что $g_{0,i}(\widetilde 0^n)=0$ для любого $i\in\{1,\dots,n\}$ и $g_{1,i'}(\widetilde 0^n)=1$ для любого $i'\in\{0,1,\dots,n\}$. Следовательно, функции $g_{0,i}$ и $g_{1,i'}$ можно отличить друг от друга на наборе $\widetilde 0^n\in T^n$. Для любых различных $i,i'\in\{0,1,\dots,n\}$ функции $g_{1,i}$ и $g_{1,i'}$ можно отличить друг от друга хотя бы на одном наборе из множества $T^n_1\subseteq T^n$, поскольку $T^n_1$ – ДТ для $M^n_1$. Осталось различить между собой функции $g_{0,i}$ и $g_{0,i'}$, где $i$ и $i'$ – произвольные различные индексы из множества $\{1,\dots,n\}$. Легко видеть, что $g_{0,i}=g_{1,i}\oplus 1$ и $g_{0,i'}=g_{1,i'}\oplus 1$, поэтому откуда следует, что функции $g_{0,i}$ и $g_{0,i'}$ можно различить на том же наборе из множества $T^n_1\subseteq T^n$, что и функции $g_{1,i}$ и $g_{1,i'}$. В итоге получаем, что любые две функции из множества $M^n$ можно различить на наборах из множества $T^n$, поэтому $T^n$ – ДТ для $M^n$. Мощность этого теста не превосходит $|T^n_1|+1\leqslant\lceil\log_2(n+1)\rceil+1$. Лемма 2 доказана. Лемма 3. Пусть $p\in\{0,1\}$, $n\geqslant 2$, $g_{p,i}(\widetilde x^{\,n})=x_{i+1}\oplus\dots\oplus x_n\oplus p$ для каждого $i=2,\dots,n-1$ (в случае $n\geqslant 3$) и $g_{p,n}(\widetilde x^{\,n})\equiv p$. Тогда для множества $\{l_n,g_{p,2},\dots,g_{p,n}\}$ существует ДТ мощности не более $\lceil\log_2 n\rceil$. Доказательство. В случае $n=2$ функции $l_2(x_1,x_2)=x_1\oplus x_2$ и $g_{p,2}(x_1,x_2)\equiv p$ можно отличить друг от друга на наборе $(p1)$, поэтому для множества $\{l_2,g_{p,2}\}$ существует ДТ мощности $1=\lceil\log_2 2\rceil$. Далее будем считать, что $n\geqslant 3$. Пусть В итоге получаем, что $\widehat T^n_p$ – ДТ мощности не более $\lceil\log_2 n\rceil$ для множества $\widehat M^n_p$. Лемма 3 доказана. Лемма 4. Пусть $n\geqslant 2$, $g_{p,i}(\widetilde x^{\,n})=x_{i+1} \oplus\dots\oplus x_n\oplus p$ для каждых $i=2,\dots,n-1$ и $p=0,1$ (в случае $n\geqslant 3$), $g_{p,n}(\widetilde x^{\,n})\equiv p$ для каждого $p=0,1$. Тогда для множества $\{l_n,g_{0,2},\dots,g_{0,n},g_{1,2},\dots,g_{1,n}\}$ существует ДТ мощности не более $\lceil\log_2 n\rceil+1$. Доказательство. Лемма 4 выводится из леммы 3 по аналогии с тем, как лемма 2 выводится из леммы 1. Введем для удобства обозначение $g_{0,1}=l_n$. В силу леммы 3 для множества $\widehat M^n_0=\{g_{0,1},g_{0,2},\dots,g_{0,n}\}$ существует ДТ $\widehat T^n_0$ мощности не более $\lceil\log_2 n\rceil$. Докажем, что множество $\widehat M^n= \{g_{0,1},g_{0,2},\dots,g_{0,n},g_{1,2},\dots,g_{1,n}\}$ допускает ДТ $\widehat T^n=\widehat T^n_0\cup\{\widetilde 0^n\}$, где $\widetilde 0^n=(\underbrace{0\dots 0}_n)$. Заметим, что $g_{0,i}(\widetilde 0^n)=0$ для любого $i\in\{1,\dots,n\}$ и $g_{1,i'}(\widetilde 0^n)=1$ для любого $i'\in\{2,\dots,n\}$. Следовательно, функции $g_{0,i}$ и $g_{1,i'}$ можно отличить друг от друга на наборе $\widetilde 0^n\in\widehat T^n$. Для любых различных $i,i'\in\{1,\dots,n\}$ функции $g_{0,i}$ и $g_{0,i'}$ можно отличить друг от друга хотя бы на одном наборе из множества $\widehat T^n_0\subseteq\widehat T^n$, поскольку $\widehat T^n_0$ – ДТ для $\widehat M^n_0$. Осталось различить между собой функции $g_{1,i}$ и $g_{1,i'}$, где $i$ и $i'$ – произвольные различные индексы из множества $\{2,\dots,n\}$. Легко видеть, что $g_{1,i}=g_{0,i}\oplus 1$ и $g_{1,i'}=g_{0,i'}\oplus 1$, поэтому откуда следует, что функции $g_{1,i}$ и $g_{1,i'}$ можно различить на том же наборе из множества $\widehat T^n_0\subseteq\widehat T^n$, что и функции $g_{0,i}$ и $g_{0,i'}$. В итоге получаем, что любые две функции из множества $\widehat M^n$ можно различить на наборах из множества $\widehat T^n$, поэтому $\widehat T^n$ – ДТ для $\widehat M^n$. Мощность этого теста не превосходит $|\widehat T^n_0|+1\leqslant\lceil\log_2 n\rceil+1$. Лемма 4 доказана. 3. Формулировки и доказательства основных результатовВместо “вход схемы $S$, отвечающий переменной $x_i$” для краткости будем писать “вход $x_i$ схемы $S$”. Рассмотрим базис $B_\oplus=\{x\oplus y,1\}$. Любой функциональный элемент, реализующий функцию вида $x\oplus y$ от своих входов, будем называть сумматором. Предполагается, что константа $1$ подается со входа схемы, не является функциональным элементом и не может быть неисправна. Теорема 1. Справедливы неравенства Доказательство. Рассмотрим вначале случай $n=1$. Функцию $l_1(x_1)=x_1$ можно реализовать СФЭ, не содержащей функциональных элементов. У такой схемы нет ни одной функции неисправности, поэтому пустое множество является для нее ПДТ и Построим схему $S$ в базисе $B_\oplus$, реализующую функцию $\overline l_n(\widetilde x^{\,n})$ (см. рис. 1). Схема $S$ представляет собой цепочку из сумматоров $E_1,\dots,E_n$. На входы сумматора $E_1$ подаются константа $1$ и переменная $x_1$ со входов схемы. Для каждого $i\in\{2,\dots,n\}$ входы сумматора $E_i$ соединяются с выходом элемента $E_{i-1}$ и со входом $x_i$ схемы. Выходом схемы $S$ объявим выход сумматора $E_n$; легко видеть, что на этом выходе реализуется функция $\overline l_n(\widetilde x^{\,n})$. Рассмотрим два случая. 1) Пусть в схеме возможны только неисправности заданного типа $p$, $p\in\{0,1\}$, на выходах элементов. Найдем все возможные функции неисправности схемы $S$. Обозначим через $q$ максимальный такой индекс из множества $\{1,\dots,n\}$, что сумматор $E_q$ неисправен. Тогда на выходе этого сумматора реализуется константа $p$. Если $q=n$, то на выходе схемы $S$ получим функцию неисправности $g_{p,n}(\widetilde x^{\,n})\equiv p$. Если же $q\leqslant n-1$, то все сумматоры $E_{q+1},\dots,E_n$ исправны, поэтому на выходе схемы $S$ реализуется функция неисправности $g_{p,q}(\widetilde x^{\,n})=p\oplus x_{q+1}\oplus\dots\oplus x_n$. Таким образом, множество всех функций неисправности схемы $S$ имеет вид $\{g_{p,1},\dots,g_{p,n}\}$ и $M(S)=\{\overline l_n,g_{p,1},\dots,g_{p,n}\}$. По лемме 1 для множества $M(S)$ существует ДТ мощности не более $\lceil\log_2(n+1)\rceil$, поэтому схема $S$ допускает ПДТ длины не более $\lceil\log_2(n+1)\rceil$, откуда следует, что $D^{B_\oplus}_0(\overline l_n)\leqslant\lceil\log_2(n+1)\rceil$ и $D^{B_\oplus}_1(\overline l_n)\leqslant\lceil\log_2(n+1)\rceil$. Четвертое и пятое неравенства из формулировки теоремы 1 доказаны. 2) Пусть в схеме возможны произвольные константные неисправности на выходах элементов. Найдем все возможные функции неисправности схемы $S$. Обозначим через $q$ максимальный такой индекс из множества $\{1,\dots,n-1\}$, что сумматор $E_q$ неисправен. Тогда на выходе этого сумматора реализуется некоторая булева константа $b$. Если $q=n$, то на выходе схемы $S$ получим функцию неисправности $g_{b,n}(\widetilde x^{\,n})\equiv b$. Если же $q\leqslant n-1$, то все сумматоры $E_{q+1},\dots,E_n$ исправны, поэтому на выходе схемы $S$ реализуется функция неисправности $g_{b,q}(\widetilde x^{\,n})=b\oplus x_{q+1}\oplus\dots\oplus x_n$. Таким образом, множество всех функций неисправности схемы $S$ имеет вид $\{g_{0,1},\dots,g_{0,n},g_{1,1},\dots,g_{1,n}\}$ и $M(S)=\{\overline l_n,g_{0,1},\dots,g_{0,n},g_{1,1},\dots, g_{1,n}\}$. По лемме 2 для множества $M(S)$ существует ДТ мощности не более $\lceil\log_2(n+1)\rceil+1$, поэтому схема $S$ допускает ПДТ длины не более $\lceil\log_2(n+1)\rceil+1$ и $D^{B_\oplus}_{01}(\overline l_n)\leqslant \lceil\log_2(n+1)\rceil+1$. Шестое неравенство из формулировки теоремы 1 доказано. Удалим из схемы $S$ сумматор $E_1$, а соединявшийся с его выходом вход сумматора $E_2$ соединим вместо этого со входом $x_1$ схемы. Полученную схему, выход которой совпадает с выходом элемента $E_n$, обозначим через $S'$ (см. рис. 2); легко видеть, что на выходе схемы $S'$ реализуется функция $l_n(\widetilde x^{\,n})$. Рассмотрим два случая. 1$'$) Пусть в схеме возможны только неисправности заданного типа $p$, $p\in\{0,1\}$, на выходах элементов. Найдем все возможные функции неисправности схемы $S'$. Обозначим через $q$ максимальный такой индекс из множества $\{2,\dots,n\}$, что сумматор $E_q$ неисправен. Тогда на выходе этого сумматора реализуется константа $p$. Если $q=n$, то на выходе схемы $S'$ получим функцию неисправности $g_{p,n}(\widetilde x^{\,n})\equiv p$. Если же $q\leqslant n-1$, то все сумматоры $E_{q+1},\dots,E_n$ исправны, поэтому на выходе схемы $S'$ реализуется функция неисправности $g_{p,q}(\widetilde x^{\,n})=p\oplus x_{q+1}\oplus\dots\oplus x_n$. Таким образом, множество всех функций неисправности схемы $S'$ имеет вид $\{g_{p,2},\dots,g_{p,n}\}$ и $M(S')=\{l_n,g_{p,2},\dots,g_{p,n}\}$. По лемме 3 для множества $M(S')$ существует ДТ мощности не более $\lceil\log_2 n\rceil$, поэтому схема $S'$ допускает ПДТ длины не более $\lceil\log_2 n\rceil$, откуда следует, что $D^{B_\oplus}_0(l_n)\leqslant\lceil\log_2 n\rceil$ и $D^{B_\oplus}_1(l_n)\leqslant\lceil\log_2 n\rceil$. Первое и второе неравенства из формулировки теоремы 1 доказаны. 2$'$) Пусть в схеме возможны произвольные константные неисправности на выходах элементов. Найдем все возможные функции неисправности схемы $S'$. Обозначим через $q$ максимальный такой индекс из множества $\{2,\dots,n\}$, что сумматор $E_q$ неисправен. Тогда на выходе этого сумматора реализуется некоторая булева константа $b$. Если $q=n$, то на выходе схемы $S'$ получим функцию неисправности $g_{b,n}(\widetilde x^{\,n})\equiv b$. Если же $q\leqslant n-1$, то все сумматоры $E_{q+1},\dots,E_n$ исправны, поэтому на выходе схемы $S'$ реализуется функция неисправности $g_{b,q}(\widetilde x^{\,n})=b\oplus x_{q+1}\oplus\dots\oplus x_n$. Таким образом, множество всех функций неисправности схемы $S'$ имеет вид $\{g_{0,2},\dots,g_{0,n},g_{1,2},\dots,g_{1,n}\}$ и $M(S')=\{l_n,g_{0,2},\dots,g_{0,n},g_{1,2},\dots,g_{1,n}\}$. По лемме 4 для множества $M(S')$ существует ДТ мощности не более $\lceil\log_2 n\rceil+1$, поэтому схема $S'$ допускает ПДТ длины не более $\lceil\log_2 n\rceil+1$, откуда следует, что $D^{B_\oplus}_{01}(l_n)\leqslant\lceil\log_2 n\rceil+1$. Третье неравенство из формулировки теоремы, а вместе с ним и вся теорема 1 доказаны. Рассмотрим базис $B_1=\{x\&\overline y,x\vee y,\overline x\}$. Любой функциональный элемент, реализующий функцию вида $x\vee y$ (вида $x\&\overline y$, вида $\overline x$) от своих входов, будем называть дизъюнктором (соответственно косым конъюнктором, инвертором). Вход произвольного косого конъюнктора, отвечающий переменной $x$ (переменной $y$), будем считать положительным (соответственно отрицательным). Доказательство. Рассмотрим вначале случай $n=1$. Функцию $l_1(x_1)=x_1$ можно реализовать СФЭ, не содержащей функциональных элементов. У такой схемы нет ни одной функции неисправности, поэтому пустое множество является для нее ПДТ и $D^{B_1}_1(l_1)=0$. Функцию $\overline l_1(x_1)=\overline x_1$ можно реализовать СФЭ, состоящей из одного инвертора. Очевидно, что данная схема имеет единственную функцию неисправности (при неисправностях типа $1$ на выходах элементов) – константу $1$, которую можно отличить от функции $\overline x_1$ на наборе $(1)$, поэтому $D^{B_1}_1(\overline l_1)\leqslant 1$. Далее будем считать, что $n\geqslant 2$. Построим схему $S_\oplus$ со входами $x$ и $y$ в базисе $B_1$, реализующую функцию $x\oplus y$ (см. рис. 3). Переменная $x$ подается на положительный, а переменная $y$ – на отрицательный вход косого конъюнктора. Кроме того, переменная $x$ подается на отрицательный, а переменная $y$ – на положительный вход другого косого конъюнктора. Выходы указанных двух косых конъюнкторов соединяются со входами дизъюнктора, выход которого объявляется выходом схемы $S_\oplus$. Очевидно, что на этом выходе реализуется функция $(x\&\overline y)\vee(\overline x\&y)=x\oplus y$, а единственной функцией неисправности схемы $S_\oplus$ является тождественная единица. Теперь построим схему $S$ в базисе $B_1$, реализующую функцию $\overline l_n(\widetilde x^{\,n})$ (см. рис. 4). Схема $S$ состоит из подсхем $S_1,\dots,S_n$. Подсхема $S_1$ содержит единственный элемент – инвертор, вход которого соединяется со входом $x_1$ схемы. Для каждого $i\in\{2,\dots,n\}$ подсхема $S_i$ представляет собой копию схемы $S_\oplus$. Входы подсхемы $S_i$ соединяются с выходом подсхемы $S_{i-1}$ и со входом $x_i$ схемы. Выходом схемы $S$ объявим выход подсхемы $S_n$; легко видеть, что на этом выходе реализуется функция $\overline x_1\oplus x_2 \oplus\dots\oplus x_n=\overline l_n(\widetilde x^{\,n})$. Найдем все возможные функции неисправности схемы $S$. Пусть $q$ – максимальный такой индекс из множества $\{1,\dots,n\}$, что в подсхеме $S_q$ хотя бы один элемент неисправен. Тогда на выходе этой подсхемы реализуется константа $1$. Если $q=n$, то на выходе схемы $S$ получим функцию неисправности $g_{1,n}(\widetilde x^{\,n})\equiv 1$. Если же $q\leqslant n-1$, то в подсхемах $S_{q+1},\dots,S_n$ все элементы исправны и каждая из них реализует функцию $x\oplus y$ от своих входов, поэтому на выходе схемы $S$ реализуется функция неисправности $g_{1,q}(\widetilde x^{\,n})=1\oplus x_{q+1}\oplus\dots\oplus x_n$. Таким образом, множество всех функций неисправности схемы $S$ имеет вид $\{g_{1,1},\dots,g_{1,n}\}$ и $M(S)=\{\overline l_n,g_{1,1},\dots,g_{1,n}\}$. По лемме 1 для множества $M(S)$ существует ДТ мощности не более $\lceil\log_2(n+1)\rceil$, поэтому схема $S$ допускает ПДТ длины не более $\lceil\log_2(n+1)\rceil$ и неравенство $D^{B_1}_1(\overline l_n)\leqslant\lceil\log_2(n+1)\rceil$ доказано. Удалим из схемы $S$ подсхему $S_1$, а соединявшийся с ее выходом вход подсхемы $S_2$ соединим вместо этого со входом $x_1$ схемы. Полученную схему, выход которой совпадает с выходом подсхемы $S_n$, обозначим через $S'$ (см. рис. 5); легко видеть, что на выходе схемы $S'$ реализуется функция $l_n(\widetilde x^{\,n})$. Найдем все возможные функции неисправности схемы $S'$. Пусть $q$ – максимальный такой индекс из множества $\{2,\dots,n\}$, что в подсхеме $S_q$ хотя бы один элемент неисправен. Тогда на выходе этой подсхемы реализуется константа $1$. Если $q=n$, то на выходе схемы $S'$ получим функцию неисправности $g_{1,n}(\widetilde x^{\,n})\equiv 1$. Если же $q\leqslant n-1$, то в подсхемах $S_{q+1},\dots,S_n$ все элементы исправны и каждая из них реализует функцию $x\oplus y$ от своих входов, поэтому на выходе схемы $S'$ реализуется функция неисправности $g_{1,q}(\widetilde x^{\,n})=1\oplus x_{q+1}\oplus\dots\oplus x_n$. Таким образом, множество всех функций неисправности схемы $S'$ имеет вид $\{g_{1,2},\dots,g_{1,n}\}$ и $M(S')=\{l_n,g_{1,2},\dots,g_{1,n}\}$. По лемме 3 для множества $M(S')$ существует ДТ мощности не более $\lceil\log_2 n\rceil$, поэтому схема $S'$ допускает ПДТ длины не более $\lceil\log_2 n\rceil$ и неравенство $D^{B_1}_1(l_n)\leqslant\lceil\log_2 n\rceil$, а вместе с ним теорема 2 доказаны. Из теоремы 2 с использованием принципа двойственности (см., например, [17; с. 24]) можно получить неравенства
$$
\begin{equation*}
\begin{aligned} \, D^{B^*_1}_0(l_n)&\leqslant\begin{cases} \lceil\log_2 n\rceil,&\text{если } n \text{ нечетно}, \\ \lceil\log_2(n+1)\rceil,&\text{если } n \text{ четно}, \end{cases} \\ D^{B^*_1}_0(\overline l_n)&\leqslant\begin{cases} \lceil\log_2(n+1)\rceil,&\text{если } n \text{ нечетно}, \\ \lceil\log_2 n\rceil,&\text{если } n \text{ четно}, \end{cases} \end{aligned}
\end{equation*}
\notag
$$
где $B^*_1=\{x\&y,x\to y,\overline x\}$ – базис, двойственный базису $B_1$. Рассмотрим стандартный базис $B_0=\{x\&y,x\vee y,\overline x\}$. Любой функциональный элемент, реализующий функцию вида $x\&y$ от своих входов, будем называть конъюнктором. Теорема 3. Справедливы неравенства $D^{B_0}_0(l_n)\leqslant n$, $D^{B_0}_0(\overline l_n)\leqslant n$, $D^{B_0}_1(l_n)\leqslant n$ и $D^{B_0}_1(\overline l_n)\leqslant n$. Доказательство. Докажем неравенства $D^{B_0}_0(l_n)\leqslant n$ и $D^{B_0}_0(\overline l_n)\leqslant n$; оставшиеся два неравенства будут следовать из них по принципу двойственности. Рассмотрим вначале случай $n=1$. Функцию $l_1(x_1)=x_1$ можно реализовать СФЭ, не содержащей функциональных элементов. У такой схемы нет ни одной функции неисправности, поэтому пустое множество является для нее ПДТ и $D^{B_0}_0(l_1)=0$. Функцию $\overline l_1(x_1)=\overline x_1$ можно реализовать СФЭ, состоящей из одного инвертора. Очевидно, что данная схема имеет единственную функцию неисправности (при неисправностях типа $0$ на выходах элементов) – константу $0$, которую можно отличить от функции $\overline x_1$ на наборе $(0)$, поэтому $D^{B_0}_0(\overline l_1)\leqslant 1$. Далее будем считать, что $n\geqslant 2$. Построим схему $S_\oplus$ со входами $x$ и $y$ в базисе $B_0$, реализующую функцию $x\oplus y$ (см. рис. 6). Переменные $x$ и $y$ подаются на входы конъюнктора $E$ и на входы дизъюнктора. Выход элемента $E$ соединяется со входом инвертора, а выходы инвертора и дизъюнктора соединяются со входами еще одного конъюнктора, выход которого объявляется выходом схемы $S_\oplus$. Легко видеть, что на этом выходе реализуется функция $\overline{x\&y}\&(x\vee y)=x\oplus y$, а схема $S_\oplus$ имеет ровно две функции неисправности: константу $0$ и функцию $x\vee y$ (последняя из них возникает при неисправности конъюнктора $E$). Теперь построим схему $S$ в базисе $B_0$, реализующую функцию $l_n(\widetilde x^{\,n})$. Схема $S$ имеет вид, изображенный на рис. 5. Она состоит из подсхем $S_2,\dots,S_n$ (для удобства выберем именно такую нумерацию), каждая из которых представляет собой копию схемы $S_\oplus$. Входы подсхемы $S_2$ соединяются со входами $x_1$ и $x_2$ схемы $S$. В случае $n\geqslant 3$ для каждого $i\in\{3,\dots,n\}$ входы подсхемы $S_i$ соединяются с выходом подсхемы $S_{i-1}$ и со входом $x_i$ схемы $S$. Выходом схемы $S$ объявим выход подсхемы $S_n$; очевидно, что на этом выходе реализуется функция $l_n(\widetilde x^{\,n})$. Найдем все возможные функции неисправности схемы $S$. Пусть $q$ – максимальный такой индекс из множества $\{2,\dots,n\}$, что подсхема $S_q$, рассматриваемая как схема со входами $x$ и $y$, реализует тождественный нуль (если такого индекса нет, полагаем $q=0$). Тогда в случае $2\leqslant q\leqslant n-1$ каждая из подсхем $S_{q+1},\dots,S_n$, а в случае $q=0$ каждая из подсхем $S_2,\dots,S_n$, как показано выше, реализует либо сумму по модулю $2$, либо дизъюнкцию значений, подаваемых на свои входы. Отсюда с учетом равенств $0\oplus x_{q+1}=x_{q+1}$, $0\vee x_{q+1}=x_{q+1}$ получаем, что каждая функция неисправности схемы $S$ имеет вид
$$
\begin{equation}
g_{q,i}(\widetilde x^{\,n})=\underbrace{(\cdots(}_{n-q-2}x_{q+1} \circ_{i,1}x_{q+2})\circ_{i,2}x_{q+3})\cdots \circ_{i,n-q-2}x_{n-1})\circ_{i,n-q-1}x_n
\end{equation}
\tag{3.1}
$$
(в случаях $q=n$, $q=n-1$ и $q=n-2$ полагаем соответственно $g_{q,i}(\widetilde x^{\,n})\equiv 0$, $g_{q,i}(\widetilde x^{\,n})=x_n$ и $g_{q,i}(\widetilde x^{\,n})=x_{n-1}\circ_{i,1}x_n$), где $q\in\{0,2,3,\dots,n\}$ и каждая из бинарных операций $\circ_{i,1},\dots,\circ_{i,n-q-1}$ – это либо $\oplus$, либо $\vee$. Функция $l_n(\widetilde x^{\,n})$ также имеет вид (3.1) при $q=0$ и $\circ_{i,1}=\cdots=\circ_{i,n-q-1}=\oplus$ (под равенством бинарных операций понимается их совпадение). Докажем, что схема $S$ допускает ПДТ $T=\{\widetilde\sigma_1,\dots,\widetilde\sigma_n\}$, где
$$
\begin{equation*}
\widetilde\sigma_1=(1\underbrace{0\dots 0}_{n-1}),\qquad \widetilde\sigma_k=(\underbrace{0\dots 0}_{k-2}11 \underbrace{0\dots 0}_{n-k}),\quad k=2,\dots,n.
\end{equation*}
\notag
$$
Достаточно доказать, что любые две различные булевы функции вида (3.1) можно отличить друг от друга хотя бы на одном из наборов $\widetilde\sigma_1,\dots,\widetilde\sigma_n$. Итак, пусть $g_{q,i}(\widetilde x^{\,n})$ – функция вида (3.1) и
$$
\begin{equation}
g_{r,j}(\widetilde x^{\,n})=\underbrace{(\cdots(}_{n-r-2}x_{r+1} \circ_{j,1}x_{r+2})\circ_{j,2}x_{r+3})\cdots \circ_{j,n-r-2}x_{n-1})\circ_{j,n-r-1}x_n
\end{equation}
\tag{3.2}
$$
(в случаях $r=n$, $r=n-1$ и $r=n-2$ полагаем соответственно $g_{r,j}(\widetilde x^{\,n})\equiv 0$, $g_{r,j}(\widetilde x^{\,n})=x_n$ и $g_{r,j}(\widetilde x^{\,n})=x_{n-1}\circ_{j,1}x_n$), где $r\in\{0,2,3,\dots,n\}$ и $\circ_{j,1},\dots,\circ_{j,n-r-1}\in\{\oplus,\vee\}$, причем $g_{q,i}\ne g_{r,j}$. Без ограничения общности $q\geqslant r$. Рассмотрим два случая. 1. Пусть $q\geqslant r+1$. Докажем, что $g_{q,i}(\widetilde\sigma_{r+1})=0$ и $g_{r,j}(\widetilde\sigma_{r+1})=1$. Из определения наборов $\widetilde\sigma_1,\dots,\widetilde\sigma_n$ вытекает, что крайние правые $n-r-1$ разрядов набора $\widetilde\sigma_{r+1}$ равны $0$, а его $(n-r)$-й справа разряд равен $1$, поэтому в силу неравенства $n-q\leqslant n-r-1$, соотношения (3.1) и равенств $0\oplus 0=0$, $0\vee 0=0$ имеем
$$
\begin{equation}
g_{q,i}(\widetilde\sigma_{r+1})=\underbrace{(\cdots(}_{n-q-2}0 \circ_{i,1}0)\circ_{i,2}0)\cdots\circ_{i,n-q-2}0)\circ_{i,n-q-1}0=0,
\end{equation}
\tag{3.3}
$$
а в силу соотношения (3.2) и равенств $1\oplus 0=1$, $1\vee 0=1$ имеем
$$
\begin{equation}
g_{r,j}(\widetilde\sigma_{r+1})=\underbrace{(\dots(}_{n-r-2}1 \circ_{j,1}0)\circ_{j,2}0)\dots\circ_{j,n-r-2}0)\circ_{i,n-r-1}0=1,
\end{equation}
\tag{3.4}
$$
что и требовалось доказать. 2. Пусть $q=r$. Из различия функций $g_{q,i}$ и $g_{r,j}$ следует неравенство $q\leqslant n-2$ и существование такого $t\in\{1,\dots,n-q-1\}$, что $\circ_{i,t}\ne\circ_{j,t}$. Без ограничения общности $\circ_{i,t}=\oplus$, $\circ_{j,t}=\vee$. Докажем, что $g_{q,i}(\widetilde\sigma_{t+q+1})=0$ и $g_{r,j}(\widetilde\sigma_{t+q+1})=1$. Из определения наборов $\widetilde\sigma_1,\dots,\widetilde\sigma_n$ вытекает, что в наборе $\widetilde\sigma_{t+q+1}$ единицы стоят только в $(t+q)$-м и $(t+q+1)$-м слева разрядах, поэтому в силу соотношений (3.1), (3.2) и свойств функций $x\oplus y$, $x\vee y$ имеем
$$
\begin{equation*}
\nonumber g_{q,i}(\widetilde\sigma_{t+q+1}) = \underbrace{(\cdots(}_{n-q-2}0\circ_{i,1}0)\cdots\circ_{i,t-2}0) \circ_{i,t-1}1)\circ_{i,t}1)\circ_{i,t+1}0)\cdots\circ_{i,n-q-1}0
\end{equation*}
\notag
$$
$$
\begin{equation*}
\nonumber =\underbrace{(\cdots(}_{n-q-t}0\circ_{i,t-1}1)\oplus 1) \circ_{i,t+1}0)\cdots\circ_{i,n-q-1}0
\end{equation*}
\notag
$$
$$
\begin{equation}
=\underbrace{(\cdots(}_{\substack{n-q-\\-t-2}}0\circ_{i,t+1}0) \cdots\circ_{i,n-q-1}0=0,
\end{equation}
\tag{3.5}
$$
$$
\begin{equation*}
\nonumber g_{r,j}(\widetilde\sigma_{t+q+1}) = \underbrace{(\cdots(}_{n-q-2}0\circ_{j,1}0)\cdots\circ_{j,t-2}0) \circ_{j,t-1}1)\circ_{j,t}1)\circ_{j,t+1}0)\cdots\circ_{j,n-q-1}0
\end{equation*}
\notag
$$
$$
\begin{equation*}
\nonumber =\underbrace{(\cdots(}_{n-q-t}0\circ_{j,t-1}1)\vee 1)\circ_{j,t+1}0) \cdots\circ_{j,n-q-2}0
\end{equation*}
\notag
$$
$$
\begin{equation}
=\underbrace{(\cdots(}_{\substack{n-q-\\-t-2}}1\circ_{j,t+1}0) \cdots\circ_{j,n-q-1}0=1,
\end{equation}
\tag{3.6}
$$
что и требовалось доказать. Тем самым установлено, что любые две различные булевы функции вида (3.1) можно отличить друг от друга хотя бы на одном наборе из множества $T$, поэтому схема $S$ допускает ПДТ $T$ длины $n$ и неравенство $D^{B_0}_0(l_n)\leqslant n$ доказано. Неравенство $D^{B_0}_0(\overline l_n)\leqslant n$ доказывается похожим образом; перечислим основные отличия. Подсхема $S_n$, рассматриваемая как схема со входами $x$ и $y$, теперь не является копией схемы $S_\oplus$, а имеет следующий вид (см. рис. 7). Переменные $x$ и $y$ подаются на входы инверторов $I_1$ и $I_2$ соответственно. Выход элемента $I_1$ и вход $y$ схемы соединяются со входами дизъюнктора, а вход $x$ схемы и выход элемента $I_2$ – со входами другого дизъюнктора. Выходы двух указанных дизъюнкторов соединяются со входами конъюнктора, выход которого объявляется выходом схемы $S_n$. Легко видеть, что на этом выходе реализуется функция
$$
\begin{equation*}
(\overline x\vee y)\&(x\vee\overline y)=x\oplus y\oplus 1=x\sim y,
\end{equation*}
\notag
$$
а схема $S_n$ имеет ровно две функции неисправности: константу $0$ и функцию $x\&y$ (последняя из них возникает при неисправности одного или обоих инверторов схемы). Очевидно, что на выходе схемы $S$ при отсутствии в ней неисправностей реализуется функция $(x_1\oplus\dots\oplus x_{n-1})\oplus x_n\oplus 1= \overline l_n(\widetilde x^{\,n})$. В представлении (3.1) операция $\circ_{i,n-q-1}$ теперь является одной из операций $\sim$, $\&$, а в случае $q=n-1$ полагаем $g_{q,i}(\widetilde x^{\,n})=\overline x_n$. Функция $\overline l_n(\widetilde x^{\,n})$ также имеет вид (3.1) при $q=0$ и $\circ_{i,1}=\cdots=\circ_{i,n-q-2}=\oplus$, $\circ_{i,n-q-1}=\sim$. У каждого из наборов $\widetilde\sigma_1,\dots,\widetilde\sigma_{n-1}$ последний разряд меняется с $0$ на $1$. Набор $\widetilde\sigma_n$ становится равным $(\underbrace{0\dots 0}_n)$. Если выполнен случай 1 (т.е. $q\geqslant r+1$) и при этом $r\leqslant n-2$, или же если выполнен случай 2 (т.е. $q=r$) и при этом $t\leqslant n-q-2$, то в каждом из соотношений (3.3), (3.4) (соответственно в каждом из соотношений (3.5), (3.6)) каждый нуль, стоящий непосредственно перед знаком равенства, заменяется на единицу, поскольку $\widetilde\sigma_{r+1}\in \{\widetilde\sigma_1,\dots,\widetilde\sigma_{n-1}\}$ (соответственно $\widetilde\sigma_{t+q+1}\in\{\widetilde\sigma_1, \dots,\widetilde\sigma_{n-1}\}$); при этом крайняя правая часть каждого из этих соотношений с учетом равенств $0\sim 1=0$, $0\&1=0$, $1\sim 1=1$, $1\&1=1$ остается неизменной. Если выполнен случай 1 и $r=n-1$, то $q=n$, $g_{q,i}(\widetilde x^{\,n})\equiv 0$, $g_{r,j}(\widetilde x^{\,n})=\overline x_n$ и функции $g_{q,i}$ и $g_{r,j}$ можно различить на наборе $\widetilde\sigma_n$. Наконец, пусть выполнен случай 2 и $t=n-q-1$. Тогда $\circ_{i,n-q-1}\ne\circ_{j,n-q-1}$. Без ограничения общности $\circ_{i,n-q-1}=\sim$, $\circ_{j,n-q-1}=\&$. В силу соотношений (3.1), (3.2) и свойств функций $x\oplus y$, $x\vee y$, $x\sim y$, $x\&y$ имеем
$$
\begin{equation*}
\begin{aligned} \, g_{q,i}(\widetilde\sigma_n)&= \underbrace{(\cdots(}_{n-q-2}0\circ_{i,1}0)\cdots\circ_{i,n-q-2}0) \circ_{i,n-q-1}0=0\sim 0=1, \\ g_{r,j}(\widetilde\sigma_n)&= \underbrace{(\cdots(}_{n-q-2}0\circ_{j,1}0)\cdots \circ_{j,n-q-2}0)\circ_{j,n-q-1}0=0\&0=0, \end{aligned}
\end{equation*}
\notag
$$
значит, функции $g_{q,i}$ и $g_{r,j}$ можно различить на наборе $\widetilde\sigma_n$. Тем самым установлено, что любые две различные булевы функции вида (3.1) можно отличить друг от друга хотя бы на одном наборе из $T=\{\widetilde\sigma_1,\dots,\widetilde\sigma_n\}$, поэтому схема $S$ допускает ПДТ $T$ длины $n$ и неравенство $D^{B_0}_0(\overline l_n)\leqslant n$, а вместе с ним теорема 3 доказаны. 4. ЗаключениеЛегко проверить, что число функциональных элементов в каждой из схем $S$, $S'$, построенных в ходе доказательств теорем 1–3, не превосходит $4n-3$. С учетом этого обстоятельства, а также малой длины ПДТ для данных схем, широкой распространенности линейных булевых функций и простоты базисов $\{x\oplus y,1\}$, $\{x\&\overline y,x\vee y,\overline x\}$, $\{x\&y,x\vee y,\overline x\}$ полученные результаты могут иметь практическое применение. 
Цитирование в формате AMSBIB
\RBibitem{Pop23} |
|
||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|