| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Короткие полные диагностические тесты для схем, реализующих линейные булевы функции К. А. Попков Институт прикладной математики им. М.В. Келдыша Российской академии наук, г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 1, Pages DOI: https://doi.org/10.1134/S0001434623010091 
Реферативные базы данных:
  1. ВведениеВ работе рассматривается задача синтеза легкотестируемых схем из функциональных элементов (СФЭ), реализующих заданные булевы функции (см. [1]–[3]). Пусть имеется СФЭ S с одним выходом, реализующая булеву функцию f(˜xn), где n∈N и ˜xn=(x1,…,xn). Предположим, что в схеме S могут происходить константные неисправности на выходах элементов, при которых значение на выходе любого неисправного элемента становится равно некоторой булевой константе; число неисправных элементов в схеме предполагается произвольным. В результате схема S вместо исходной функции f(˜xn) будет реализовывать какие-то, вообще говоря, отличные от нее булевы функции, называемые функциями неисправности данной схемы. Через M(S) будем обозначать множество, состоящее из функции f(˜xn) и всех функций неисправности схемы S. Константные неисправности на выходах элементов называются однотипными константными, если на выходе каждого неисправного элемента реализуется одна и та же заранее заданная булева константа (определяющая тип этих неисправностей), и произвольными константными, если на выходе каждого неисправного элемента реализуется одна из булевых констант 0 или 1 независимо от неисправностей других элементов. Полным диагностическим тестом (ПДТ) для схемы S называется такое множество T наборов значений переменных x1,…,xn, что для любой отличной от f(˜xn) функции неисправности g(˜xn) схемы S в T найдется набор ˜σ, на котором f(˜σ)≠g(˜σ), а для любых двух различных функций неисправности g1(˜xn) и g2(˜xn) схемы S в T найдется набор ˜π, на котором g1(˜π)≠g2(˜π). Число наборов в T называется длиной теста. В качестве тривиального ПДТ длины 2n для схемы S всегда можно взять множество, состоящее из всех 2n двоичных наборов длины n. Пусть зафиксированы базис B, в котором строятся схемы, и вид допустимых неисправностей элементов в схемах. Введем следующие обозначения:
Если базис B является функционально полным, то введем также обозначение DB(n)=maxDB(f), где максимум берется по всем булевым функциям f от n переменных. Функция DB(n) называется функцией Шеннона длины ПДТ. Для удобства под буквой D будем ставить символы “01”, “0” или “1” в случаях, когда в схемах допускаются произвольные константные неисправности, однотипные константные неисправности типа 0 или типа 1 на выходах элементов соответственно. Всюду далее в данном разделе будем считать, что n – произвольное натуральное число. Положим ln(˜xn)=x1⊕⋯⊕xn, ¯ln(˜xn)=x1⊕⋯⊕xn⊕1. Очевидно, что ln и ¯ln – единственные линейные булевы функции, существенно зависящие в точности от переменных x1,…,xn. Редькин в [4] для любой булевой функции f(˜xn), существенно зависящей от всех своих переменных, доказал неравенства
\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,
\begin{equation*}
\widetilde\sigma_0=(11111111111),\quad \widetilde\sigma_1=(10101010101),\quad \widetilde\sigma_2=(10001000100), \widetilde\sigma_3=(10000000100).
\end{equation*}
\notag
Обозначим через \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. Тогда поэтому 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, поэтому
\begin{equation*}
g_{0,i}\oplus g_{0,i'}=(g_{1,i}\oplus 1)\oplus(g_{1,i'}\oplus 1)= g_{1,i}\oplus g_{1,i'},
\end{equation*}
\notag
откуда следует, что функции 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. Пусть
\begin{equation*}
\begin{aligned} \, g^{n-1}_{p,0}(\widetilde x^{\,n-1})&= \overline l_{n-1}(\widetilde x^{\,n-1})= x_1\oplus\dots\oplus x_{n-1}\oplus 1, \\ g^{n-1}_{p,i}(\widetilde x^{\,n-1})&=x_{i+1}\oplus\dots\oplus x_{n-1}\oplus p,\qquad i=1,\dots,n-2, \\ g^{n-1}_{p,n-1}(\widetilde x^{\,n-1})&\equiv p. \end{aligned}
\end{equation*}
\notag
Тогда в силу леммы 1, применяемой с заменой n на n-1, для множества M^{n-1}_p=\{g^{n-1}_{p,0},g^{n-1}_{p,1}, \dots,g^{n-1}_{p,n-1}\} существует ДТ T^{n-1}_p мощности не более \lceil\log_2 n\rceil. Все наборы из множества T^{n-1}_p являются (n-1)-разрядными. Добавим к каждому из них слева еще один разряд, равный 1. Полученное множество \widehat T^n_p состоит из n-разрядных наборов и также имеет мощность не более \lceil\log_2 n\rceil. Докажем, что \widehat T^n_p – ДТ для множества \widehat M^n_p=\{l_n,g_{p,2},\dots,g_{p,n}\}. Достаточно доказать, что для любых двух различных функций f_1,f_2\in\widehat M^n_p в \widehat T^n_p найдется набор, на котором значения функций f_1(\widetilde x^{\,n}) и f_2(\widetilde x^{\,n}) различаются. Имеем
\begin{equation*}
\begin{gathered} \, l_n(1,x_2,\dots,x_n)=x_2\oplus\dots\oplus x_n\oplus 1=g^{n-1}_{p,0}(x_2,\dots,x_n), \\ g_{p,i}(1,x_2,\dots,x_n)=x_{i+1}\oplus\dots\oplus x_n\oplus p=g^{n-1}_{p,i-1}(x_2,\dots,x_n),\qquad i=2,\dots,n-1, \\ g_{p,n}(1,x_2,\dots,x_n)\equiv p\equiv g^{n-1}_{p,n-1}(x_2,\dots,x_n). \end{gathered}
\end{equation*}
\notag
Таким образом,
\begin{equation*}
f_1(1,x_2,\dots,x_n)=g^{n-1}_{p,i}(x_2,\dots,x_n),\qquad f_2(1,x_2,\dots,x_n)=g^{n-1}_{p,i'}(x_2,\dots,x_n)
\end{equation*}
\notag
для некоторых различных i,i'\in\{0,1,\dots,n-1\}. Существует набор (\sigma_1,\dots,\sigma_{n-1})\in T^{n-1}_p такой, что g^{n-1}_{p,i}(\sigma_1,\dots,\sigma_{n-1})\ne g^{n-1}_{p,i'}(\sigma_1,\dots,\sigma_{n-1}), так как T^{n-1}_p – ДТ для множества M^{n-1}_p и g^{n-1}_{p,i},g^{n-1}_{p,i'}\in M^{n-1}_p. Тогда
\begin{equation*}
f_1(1,\sigma_1,\dots,\sigma_{n-1})= g^{n-1}_{p,i}(\sigma_1,\dots,\sigma_{n-1})\ne g^{n-1}_{p,i'}(\sigma_1,\dots,\sigma_{n-1})= f_2(1,\sigma_1,\dots,\sigma_{n-1}),
\end{equation*}
\notag
т.е. f_1(1,\sigma_1,\dots,\sigma_{n-1})\ne f_2(1,\sigma_1,\dots,\sigma_{n-1}). Заметим, что (1,\sigma_1,\dots,\sigma_{n-1})\in\widehat T^n_p в силу построения множества \widehat T^n_p. В итоге получаем, что \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, поэтому
\begin{equation*}
g_{1,i}\oplus g_{1,i'}=(g_{0,i}\oplus 1)\oplus(g_{0,i'}\oplus 1)= g_{0,i}\oplus g_{0,i'},
\end{equation*}
\notag
откуда следует, что функции 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. Справедливы неравенства
\begin{equation*}
\begin{alignedat}{2} D^{B_\oplus}_0(l_n)&\leqslant\lceil\log_2 n\rceil,&\qquad D^{B_\oplus}_1(l_n)&\leqslant\lceil\log_2 n\rceil, \\ D^{B_\oplus}_{01}(l_n)&\leqslant\lceil\log_2 n\rceil+1,&\qquad 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,&\qquad D^{B_\oplus}_{01}(\overline l_n)&\leqslant\lceil\log_2(n+1)\rceil+1. \end{alignedat}
\end{equation*}
\notag
Доказательство. Рассмотрим вначале случай n=1. Функцию l_1(x_1)=x_1 можно реализовать СФЭ, не содержащей функциональных элементов. У такой схемы нет ни одной функции неисправности, поэтому пустое множество является для нее ПДТ и
\begin{equation*}
D^{B_\oplus}_0(l_1)=D^{B_\oplus}_1(l_1)= D^{B_\oplus}_{01}(l_1)=0=\lceil\log_2 1\rceil.
\end{equation*}
\notag
Функцию \overline l_1(x_1)=x_1\oplus 1 можно реализовать СФЭ, состоящей из одного сумматора, на входы которого подаются переменная x_1 и константа 1. Очевидно, что при неисправностях типа 0 (типа 1) на выходах элементов данная схема имеет единственную функцию неисправности – константу 0 (соответственно константу 1), которую можно отличить от функции x_1\oplus 1 на наборе (0) (соответственно на наборе (1)). Поэтому
\begin{equation*}
\begin{aligned} \, D^{B_\oplus}_0(\overline l_1)\leqslant 1&=\lceil\log_2(1+1)\rceil, \\ D^{B_\oplus}_1(\overline l_1)\leqslant 1&=\lceil\log_2(1+1)\rceil. \end{aligned}
\end{equation*}
\notag
При произвольных константных неисправностях на выходах элементов указанная схема имеет две функции неисправности – константы 0 и 1, которые можно отличить от функции x_1\oplus 1 и друг от друга на наборах (0), (1), поэтому
\begin{equation*}
D^{B_\oplus}_{01}(\overline l_1)\leqslant 2= \lceil\log_2(1+1)\rceil+1.
\end{equation*}
\notag
Далее будем считать, что n\geqslant 2. Построим схему 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}
Эта публикация цитируется в следующих 1 статьяx:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь:math-net2025_04@mi-ras.ru |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|