Construction of a Reversible Full-cycle Transformation in a Threshold Basis

Abstract

The article describes a class of full-cycle transformations in the threshold basis, defined by matrices of coefficients of linear forms, and proves that the definition of the inverse transformation is carried out using a system of threshold functions, the coefficients of which form the transposed matrix with respect to the original one.

Full Text

В данной работе будет доказана обратимость полноцикловой подстановки, построенной авторами в работе [1]. Напомним определения и обозначения.

Пусть G_n – таблица размером 2ⁿ × n, строки которой суть – векторы размером n над полем GF(2), записанные в следующем порядке:

$G_1=\left(\begin{array}{c}0\\ 1\end{array}\right); G_2=\left(\begin{array}{cc}\begin{array}{c}0\\ 1\end{array}& \begin{array}{c}0\\ 1\end{array}\\ \begin{array}{c}1\\ 1\end{array}& \begin{array}{c}1\\ 0\end{array}\end{array}\right),\dots ; G_n=\left(\begin{array}{cc}0& G_{n-1}\\ 1& {\overline{G}}_{n-1}\end{array}\right),$ (1)

где G̅_{n – 1} – таблица, полученная из таблицы G_{n – 1} инвертированием всех элементов.

Определим с помощью таблицы G_n = (ε_ij)_{2n × n} отображение g : GF(2)ⁿ → GF(2)ⁿ по правилу:

g(ε_i1, … , ε_in) = (ε_{(i + 1)1}, … , ε_{(i + 1)n}).

Пример 1. В качестве примера рассмотрим G₂:

g(0, 0) = (0, 1); g(0, 1) = (1, 1);

g(1, 1) = (1, 0); g(1, 0) = (0, 0).

Утверждение 1. Для любых векторов x = (x₁, … , x_n), y = (y₁, … , y_n) из G_n верно, что если g(x) = y, то g(x̄) = ȳ, где x̄ – вектор, полученный из вектора x инвертированием координат.

Доказательство. Докажем это утверждение методом математической индукции по n.

База индукции, очевидно, следует из задания (1).

Предположим, что утверждение верно для любого n < k. Докажем его для n = k.

По предположению индукции если в G_{k – 1} существуют строки вида

$\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{c}\cdots \\ x_2\end{array}& \begin{array}{c}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}\cdots \\ x_k\end{array}\\ \begin{array}{cc}\begin{array}{c}{y}_2\\ \cdots \end{array}& \begin{array}{c}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}{y}_k\\ \cdots \end{array}\end{array}\right),$

то существуют строки вида

$\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{c}\cdots \\ {\overline{x}}_2\end{array}& \begin{array}{c}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}\cdots \\ {\overline{x}}_k\end{array}\\ \begin{array}{cc}\begin{array}{c}{\overline{y}}_2\\ \cdots \end{array}& \begin{array}{c}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}{\overline{y}}_k\\ \cdots \end{array}\end{array}\right).$

Тогда G_k принимает следующий вид:

$G_k=\left\{\begin{array}{cccc}& \cdots & \cdots & \cdots \\ & x_2& \cdots & x_k\\ 0& y_2& \cdots & y_k\\ & \cdots & \cdots & \cdots \\ & \cdots & \cdots & \cdots \\ & {\overline{x}}_2& \cdots & {\overline{x}}_k\\ 0& {\overline{y}}_2& \cdots & {\overline{y}}_k\\ & \cdots & \cdots & \cdots \\ & \cdots & \cdots & \cdots \\ 1& {\overline{x}}_2& \cdots & {\overline{x}}_k\\ & {\overline{y}}_2& & {\overline{y}}_k\\ & \cdots & \cdots & \cdots \\ & x_2& \cdots & y_k\\ 1& y_2& \cdots & y_k\\ & \cdots & \cdots & \cdots \end{array}\right\},$ (2)

Далее утверждение следует из построения G_k (см. (2)):

• если g(0, x₂, … , x_k) = (0, y₂, … , y_k), то g(1, x̄₂, … , x̄_k) = = (1, ȳ₂, … , ȳ_k);
• если g(1, x₂, … , x_k) = (1, y₂, … , y_k), то g(0, x̄₂, … , x̄_k) = = (0, ȳ₂, … , ȳ_k).

Определение 1. Пусть A = (a_ij)_{n × n} матрица размером n × n над полем ℝ. Тогда нейропреобразованием, порожденным матрицей A, назовем вектор-функцию f : GF(2)ⁿ → GF(2)ⁿ, f = (f₁, … , f_n), где f_i : GF(2)ⁿ → GF(2)ⁿ координатные функции, задаваемые каждой координатой i-й строки

матрицы A, для любого $i\in \overline{\mathrm{1,}n}$, такие что:

$f_i\left(x_1,\dots ,x_n\right)=\left\{\begin{array}{c}\mathrm{1,} если a_{i1}\left(x_1-\frac{1}{2}\right)+\dots +a_{in}\left(x_n-\frac{1}{2}\right)>0;\\ \mathrm{0,} в противном случае.\end{array} \right.$

Утверждение 2. Пусть (x₂, … , x_n) ∈ GF(2)^{n – 1}.

Неравенство

$\frac{n}{2}+\left(x_2-\frac{1}{2}\right)-\left(x_3-\frac{1}{2}\right)+\dots + {\left(-1\right)}^n\left(x_n-\frac{1}{2}\right) >0$

выполняется тогда и только тогда, когда (x₂, … , x_n) = = (1, 0, 1, 0, 1, …).

Доказательство. Пусть n = 2k, тогда левая часть неравенства принимает вид:

$-k+\frac{1}{2}+x_2-x_3+\dots -x_{2k-1}+x_{2k},$

и если перегруппировать слагаемые:

$\left(-k+\frac{1}{2}\right)+\underset{к штук}{\underbrace{\left(x_2+x_4+\dots +x_{2k}\right)}}-\left(x_3+x_5+\dots + x_{2k-1}\right),$

то утверждение становится очевидным.

Для n = 2k + 1 доказательство проводится аналогично.

Утверждение 3. Пусть A = (a_ij)_{n × n} матрица размера n × n над полем GF(2) и π_A : GF(2)ⁿ → GF(2)ⁿ – нейропреобразование, порожденное матрицей A. Тогда если π_A(x) = y, то π_A(x̄) = ȳ, где x̄ – вектор, полученный из вектора x инвертированием координат.

Доказательство. Рассмотрим

π_A(x) = f(x) = (f₁(x), … , f_n(x)).

Тогда достаточно показать, что если f_i(x) = y_i то f_i(x̄) = ȳ, для любого $i\in \overline{\mathrm{1,}n}$.

Последнее следует из того, что если

$a_{i1}\left(x_1-\frac{1}{2}\right)+\dots +a_{in}\left(x_n-\frac{1}{2}\right)>\mathrm{0,}$

то

$\begin{array}{c}{a}_{i1}\left( {\overline{x}}_1-\frac{1}{2}\right)+\dots +a_{in}\left({\overline{x}}_n-\frac{1}{2}\right)=\\ =a_{i1}\left(1-x_1-\frac{1}{2}\right)+\dots +a_{in}\left(1-x_n-\frac{1}{2}\right)=\\ = -\left(a_{i1}\left(x_1-\frac{1}{2}\right)+\dots +a_{in}\left(x_n-\frac{1}{2}\right)\right)\le 0.\end{array}$

Теорема 1. Таблица G_n задает полный цикл, который может быть задан нейропреобразованием, порожденным матрицей A_n, где A_n строится по индукции:

$\begin{array}{c}{A}_1=\left(-1\right);A_2=\left(\begin{array}{cc}0& 1\\ -1& 0\end{array}\right);\\ A_n=\left(\begin{array}{lll}n& 1& -1\dots {\left(-1\right)}^n\\ -1& n& 1\dots {\left(-1\right)}^{n+1}\\ -1& -1& \\ -1& -1& A_n+A_{n+1}\left(\begin{array}{c}\mathrm{2,}\dots ,n+1\\ \mathrm{2,}\dots ,n+1\end{array}\right)\\ \cdots & \cdots & \end{array}\right),\end{array}$

где $A_{n+1}\left(\begin{array}{c}\mathrm{2,}\dots ,n+1\\ \mathrm{2,}\dots ,n+1\end{array}\right)$ – подматрица матрицы A_{n + 1}, полученная из A_{n + 1} удалением всех строк, кроме строк с номерами 2, … , n + 1, и всех столбцов, кроме столбцов с номерами 2, … , n + 1.

Доказательство. Обозначим g_n : GF(2)ⁿ → GF(2)ⁿ – отображение, полученное с помощью цикла G_n, отображение π_An : GF(2)ⁿ → GF(2)ⁿ – нейропреобразование, порожденное матрицей A_n.

Через

$L_m^n\left(x_1,\dots ,x_n\right)=a_{m,1}\left(x_1-\frac{1}{2}\right)+\dots +a_{m,n}\left(x_n-\frac{1}{2}\right)$

будем обозначать линейную форму, порожденную m-й строкой матрицы A_n.

Индукцией по n покажем, что отображения π_An и g_n совпадают при n = 1. Из формулы (1) следует, что  и $G_1=\left(\begin{array}{c}0\\ 1\end{array}\right)$, g₁(1) = 0. Так как A₁ = (–1), то L₁¹(x₁) = –x₁ + 1/2 и получаем, что π_A1 = (0, 1). База индукции доказана.

Предположим, что утверждение верно для любого k ≤ n + 1. Докажем его при k = n + 2.

Рассмотрим сначала первые две координаты отображений g_{n + 2} и π_{An + 2}. По предложению 2 линейная форма

$\begin{array}{c}{L}_1^{n+2}\left(\mathrm{0,}{x}_2,\dots ,x_{n+2}\right)=\\ =n\left(0-\frac{1}{2}\right)+1\left(x_2-\frac{1}{2}\right)+\dots +{\left(-1\right)}^{n+2}\left(x_{n+2}-\frac{1}{2}\right) > \mathrm{0,}\end{array}$

тогда и только тогда, когда (x₁, … , x_{n + 2}) = (0, 1, 0, 1, …), и L₁^{n + 2} (1, x₂, … , x_{n + 2}) ≤ 0 и тогда и только тогда, когда (x₁, … , x_{n + 2}) = (1, 0, 1, 0, …). То же самое наблюдается и для отображения g_{n + 2} по построению G_{n + 2}.

Рассуждая аналогично, можно получить, что π_{An + 2} совпадает с g_{n + 2} и по второй координате. Таким образом получили, что

$\begin{array}{c}\begin{array}{c}{\pi }_{A_{n+2}}\left(\mathrm{0,}\mathrm{0,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{0,}\mathrm{1,}\mathrm{1,}\dots ,1\right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{0,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right);\\ \left(\mathrm{0,}\mathrm{0,}*,\dots ,*\right),& иначе;\end{array}\right.\end{array}\\ \begin{array}{c}{\pi }_{A_{n+2}}\left(\mathrm{0,}\mathrm{1,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{1,}\mathrm{1,}\mathrm{1,}\dots ,1\right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right);\\ \left(\mathrm{0,}\mathrm{0,}*,\dots ,*\right),& иначе;\end{array}\right.\end{array}\\ \begin{array}{c}{\pi }_{A_{n+2}}\left(\mathrm{1,}\mathrm{1,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{1,}\mathrm{0,}\mathrm{0,}\dots ,0\right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{1,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right);\\ \left(\mathrm{1,}\mathrm{1,}*,\dots ,*\right),& иначе;\end{array}\right.\end{array}\\ \begin{array}{c}{\pi }_{A_{n+2}}\left(\mathrm{1,}\mathrm{0,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{0,}\mathrm{0,}\mathrm{0,}\dots ,0\right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right);\\ \left(\mathrm{1,}\mathrm{0,}*,\dots ,*\right),& иначе.\end{array}\right.\end{array}\end{array}$

Для дальнейшего доказательства воспользуемся следующей леммой.

Лемма 1. Для линейных форм $L_{i+1}^{n+1}$ (x₁, … , x_{n + 1}) и L_iⁿ(x₂, … , x_{n + 1}) верно, что

$\mathrm{sgn}\left(L_{i+1}^{n+1}\left(x_1,\dots ,x_{n+1}\right)\right)=\mathrm{sgn}\left(L_i^n\left(x_2,\dots ,x_{n+1}\right)\right)$

тогда и только тогда, когда (x₁, … , x_{n + 1}) ∉ {(0, 1, 0, 1, …), (1, 0, 1, 0, …)}.

Доказательство леммы. Доказательство проведем индукцией по n.

При n = 1 линейные формы равны L²₂(x₁, x₂) = = –x₁ + 1/2, L₁¹(x₂) = –x₂ + 1/2 и утверждение леммы верно (табл. 1).

Таблица 1. Значение линейных форм L₂²(x₁, x₂)L₁¹(x₂) [Meaning of linear forms L₂²(x₁, x₂)L₁¹(x₂)]

x1	x2	L22(x1, x2)	L11(x2)
0	0	1/2	1/2
0	1	1/2	–1/2
1	0	–1/2	1/2
1	1	–1/2	–1/2

Пусть утверждение верно для любого k ≤ n + 1. Докажем при k = n + 2.

По построению матрицы $A_{n+2}={\left(a_{i,j}^{\left(n+2\right)}\right)}_{\left(n+2\right)\left(n+2\right)}$ можно сказать, что

$a_{i+\mathrm{2,2}}^{\left(n+2\right)}= a_{i+\mathrm{1,1}}^{\left(n+1\right)};a_{i+\mathrm{2,}j}^{\left(n+2\right)}=a_{i+\mathrm{1,}j-1}^{\left(n+1\right)}+a_{i,j-2}^{\left(n\right)},j\in \overline{\mathrm{3,}n+2},$

а значит

$\begin{array}{c}{L}_{i+2}^{n+2}\left(x_1,\dots ,x_{n+2}\right)=\\ =\left(-1\right)\left(x_1-\frac{1}{2}\right)+ L_{i+1}^{n+1}\left(x_2,\dots ,x_{n+2}\right) + L_i^n\left(x_3,\dots ,x_{n+2}\right).\end{array}$

По предположению индукции

$\mathrm{sgn}\left(L_{i+1}^{n+1}\left(x_2,\dots ,x_{n+2}\right)\right)=\mathrm{sgn}\left(L_i^n\left(x_3,\dots ,x_{n+2}\right)\right)$

тогда и только тогда, когда (x₂, … , x_{n + 1}) ∉ {(0, 1, 0, 1, …), (1, 0, 1, 0, …)} и учитывая, что

$\begin{array}{c}\begin{array}{c}\mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{0,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right)\right)=\\ =\mathrm{sgn}\left(\frac{1}{2}+\frac{1}{2}-\frac{1}{2}\right)= \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right)\right);\end{array}\\ \begin{array}{c}\mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right)\right)=\\ =\mathrm{sgn}\left(-\frac{1}{2}\right)\ne \mathrm{sgn}\left(\frac{1}{2}\right)= \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right)\right);\end{array}\\ \begin{array}{c}\mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right)\right)=\\ =\mathrm{sgn}\left(\frac{1}{2}\right)\ne \mathrm{sgn}\left(-\frac{1}{2}\right)= \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right)\right);\end{array}\\ \begin{array}{c}\mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{1,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right)\right)=\\ =\mathrm{sgn}\left(-\frac{1}{2}\right)= \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right)\right),\end{array}\end{array}$

получаем, что утверждение леммы верно.

Перейдем к заключительному этапу доказательства теоремы. По лемме и предложению 3 имеем:

1) π_{An + 2}(x₁, … , x_{n + 2}) = (y₁, … , y_{n + 2}) ⇒ ⇒ π_{An + 2}(x̄₁, … , x̄_{n + 2}) = (ȳ₁, … , ȳ_{n + 2});

2) π_{An + 2}(0, x₂, … , x_{n + 2}) = π_{An + 1}(x₂, … , x_{n + 2}), за исключением (x₁, … , x_{n + 2}) = (0, 1, 0, 1, …), а π_{An + 2}(0, 1, 0, 1, …) = 1.

Из выше сказанного следует, что преобразование π_{An + 2} совпадает с g_{n + 2}.

Пример 2. Приведем примеры матриц A_n:

$\begin{array}{c}{A}_1=\left(-1\right);A_2=\left(\begin{array}{cc}0& 1\\ -1& 0\end{array}\right);\\ A_3=\left(\begin{array}{ccc}1& 1& -1\\ -1& 1& 1\\ -1& -1& -1\end{array}\right);A_4= \left(\begin{array}{cc}\begin{array}{cc}2& 1\\ -1& 2\end{array}& \begin{array}{cc}-1& 1\\ 1& -1\end{array}\\ \begin{array}{cc}-1& -1\\ -1& -1\end{array}& \begin{array}{cc}1& 2\\ -2& -1\end{array}\end{array}\right);\\ A_7=\left(\begin{array}{ccc}\begin{array}{ccc}5& 1& -1\\ -1& 5& 1\\ -1& -1& 7\end{array}& \begin{array}{ccc}1& -1& 1\\ -1& 1& -1\\ 2& -2& 2\end{array}& \begin{array}{c}-1\\ 1\\ -2\end{array}\\ \begin{array}{ccc}-1& -1& -2\\ -1& -1& -2\\ -1& -1& -2\end{array}& \begin{array}{ccc}8& 3& -3\\ -3& 8& 5\\ -3& -5& 5\end{array}& \begin{array}{c}3\\ -5\\ 8\end{array}\\ \begin{array}{ccc}-1& -1& -2\end{array}& \begin{array}{ccc}-3& -5& -8\end{array}& -5\end{array}\right).\end{array}$

Естественный вопрос, возникающий при изучении подстановок – это вопрос обратимости. Дать на него ответ может дать следующая теорема.

Теорема 2. Если A_n – матрица из теоремы 1, то цикл, обратный к π_An, задается нейропреобразованием, порожденным матрицей A^T_n.

Доказательство. Рассмотрим таблицу H_n, строящуюся по индукции

$H_1=\left(\begin{array}{c}1\\ 0\end{array}\right);H_2=\left(\begin{array}{cc}\begin{array}{c}1\\ 1\end{array}& \begin{array}{c}0\\ 1\end{array}\\ \begin{array}{c}0\\ 0\end{array}& \begin{array}{c}1\\ 0\end{array}\end{array}\right), \dots ;H_n=\left(\begin{array}{cc}1& {\overline{H}}_{n-1}\\ 0& H_{n-1}\end{array}\right),$ (3)

где H̅_{n – 1} – таблица, полученная из таблицы H_{n – 1} инвертированием всех элементов.

Таблица H_n = (ε_ij)_{2n × n} задает отображение h_n : GF(2)ⁿ → GF(2)ⁿ по правилу:

h_n(ε_i1, … , ε_in) = (ε_{(i + 1)1}, … , ε_{(i + 1)n}).

По построению H_n, очевидно, что h = g^–1, где g – отображение, задаваемое формулой (1).

Индукцией по n покажем, что отображения π^T_An и h_n совпадают.

Через

$L_m^n\left(x_1,\dots ,x_n\right)=a_{m,1}\left(x_1-\frac{1}{2}\right)+\dots +a_{m,n}\left(x_n-\frac{1}{2}\right)$

будем обозначать линейную форму, порожденную m-й строкой матрицы A^T_n.

При n = 1. Из задания (3) следует, что

$H_1=\left(\begin{array}{c}1\\ 0\end{array}\right)$

и h₁(0) = 1, h₁(1) = 0. Так как A^T₁ = (–1), то L¹₁(x₁) = –x₁ + 1/2 и получаем, что π_A1 = (0, 1). База индукции доказана.

Предположим, что утверждение верно для любого k ≤ n + 1. Докажем его при k = n + 2.

Сначала докажем равенство первых двух координатных функций отображений h_{n + 2} и π^T_{An +2}. Для этого рассмотрим линейную форму

$\begin{array}{c}{L}_1^{n+2}\left(x_1,x_2,\dots ,x_{n+2}\right)=\\ =n\left(x_1-\frac{1}{2}\right)+\left(-1\right)\left(x_2-\frac{1}{2}\right)+\dots +\left(-1\right)\left(x_{n+2}-\frac{1}{2}\right)=\\ = n\left(\underset{n+1 штук}{\underbrace{x_1 -x_2+\dots +x_{n+2}}}\right) + \frac{1}{2}.\end{array}$

При x₁ = 0, L₁^{n + 2}(0, x₂, … , x_{n + 2}) > 0 тогда и только тогда, когда (x₁, … , x_{n + 2}) = (0, … , 0). При x₁ = 1, L₁^{n + 2}(1, x₂, … , x_{n + 2}) > 0 тогда и только тогда, когда (x₁, … , x_{n + 2}) = (1, … , 1). Тоже самое наблюдается и для отображения g_{n + 2} по построению G_{n + 2}.

Рассуждая аналогично, можно получить, что π^T_{An +2} совпадает с h_{n + 2} и по второй координате. Таким образом получили, что

$\begin{array}{c}\begin{array}{c}{\pi }_{A_{n+2}^T}\left(\mathrm{1,}\mathrm{0,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{1,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{1,}\mathrm{0,}0\dots ,0\right);\\ \left(\mathrm{1,}\mathrm{0,}*,\dots ,*\right),& иначе;\end{array}\right.\end{array}\\ \begin{array}{c}{\pi }_{A_{n+2}^T}\left(\mathrm{1,}\mathrm{1,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\dots \right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{1,}\mathrm{1,}1\dots ,1\right);\\ \left(\mathrm{1,}\mathrm{1,}*,\dots ,*\right),& иначе;\end{array}\right.\end{array}\\ \begin{array}{c}{\pi }_{A_{n+2}^T}\left(\mathrm{0,}\mathrm{1,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{0,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{0,}\mathrm{1,}\mathrm{1,}\mathrm{1,}\dots ,1\right);\\ \left(\mathrm{1,}\mathrm{0,}*,\dots ,*\right),& иначе;\end{array}\right.\end{array}\\ \begin{array}{c}{\pi }_{A_{n+2}^T}\left(\mathrm{0,}\mathrm{0,}*,\dots ,*\right)=\\ =\left\{\begin{array}{ll}\left(\mathrm{1,}\mathrm{0,}\mathrm{1,}\mathrm{0,}\dots \right),& \left(x_1,\dots ,x_{n+2}\right)=\left(\mathrm{0,}\mathrm{0,}0\dots ,0\right);\\ \left(\mathrm{0,}\mathrm{0,}*,\dots ,*\right),& иначе.\end{array}\right.\end{array}\end{array}$

Для дальнейшего доказательства воспользуемся следующей леммой.

Лемма 2. Для линейных форм $L_{i+1}^{n+1}$ (x₁, … , x_{n + 1}) и L_iⁿ(x₂, … , x_{n + 1}) верно, что

$\mathrm{sgn}\left(L_{i+1}^{n+1}\left(x_1,\dots ,x_{n+1}\right)\right)=\mathrm{sgn}\left(L_i^n\left(x_2,\dots ,x_{n+1}\right)\right)$

тогда и только тогда, когда (x₁, … , x_{n + 1}) ∉ {(0, … , 0), (1, … , 1)}.

Доказательство леммы. Доказательство проведем индукцией по n.

При n = 1 линейные формы равны L²₂(x₁, x₂) = x₁ – 1/2, L¹₁(x₂) = –x₂ + 1/2 и утверждение леммы верно (табл. 2).

Таблица 2. Значение линейных форм L₂²(x₁, x₂)L₁¹(x₂) [Meaning of linear forms L₂²(x₁, x₂)L₁¹(x₂)]

x1	x2	L22(x1, x2)	L11(x2)
0	0	–1/2	1/2
0	1	–1/2	–1/2
1	0	1/2	1/2
1	1	1/2	–1/2

Пусть утверждение верно для любого k ≤ n + 1. Докажем при k = n + 2.

По построению матрицы $A_{n+2}^T={\left(a_{i,j}^{T,\left(n+2\right)}\right)}_{\left(n+2\right)\left(n+2\right)}$ можно сказать, что

$\begin{array}{c}{a}_{i+\mathrm{2,2}}^{T,\left(n+2\right)}= a_{i+\mathrm{1,1}}^{T,\left(n+1\right)};\\ a_{i+\mathrm{2,}j}^{T,\left(n+2\right)}=a_{i+\mathrm{1,}j-1}^{T,\left(n+1\right)}+a_{i,j-2}^{T,\left(n\right)},j\in \overline{\mathrm{3,}n+2},\end{array}$

а значит

$\begin{array}{c}{L}_{i+2}^{n+2}\left(x_1,\dots ,x_{n+2}\right)=\\ ={\left(-1\right)}^{n+2}\left(x_1-\frac{1}{2}\right)+ L_{i+1}^{n+1}\left(x_2,\dots ,x_{n+2}\right) + L_i^n\left(x_3,\dots ,x_{n+2}\right).\end{array}$

По предположению индукции

$\mathrm{sgn}\left(L_{i+1}^{n+1}\left(x_2,\dots ,x_{n+2}\right)\right)=\mathrm{sgn}\left(L_i^n\left(x_3,\dots ,x_{n+2}\right)\right)$

тогда и только тогда, когда (x₂, … , x_{n + 1}) ∉ {(0, … , 0), (1, … , 1)} и учитывая, что

$\begin{array}{c}\mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{0,}\dots ,0\right)\right)\ne \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{0,}\dots ,0\right)\right);\\ \mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{0,}\mathrm{1,}\mathrm{1,}\dots ,1\right)\right)= \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{1,}\mathrm{1,}\dots ,1\right)\right);\\ \mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{1,}\mathrm{0,}\mathrm{0,}\dots ,0\right)\right)= \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{0,}\dots ,0\right)\right);\\ \mathrm{sgn}\left(L_{i+2}^{n+2}\left(\mathrm{1,}\mathrm{1,}\dots ,1\right)\right)\ne \mathrm{sgn}\left(L_{i+1}^{n+1}\left(\mathrm{1,}\mathrm{1,}\dots ,1\right)\right),\end{array}$

получаем, что утверждение леммы верно.

Перейдем к заключительному этапу доказательства теоремы. По лемме и предложению 3 имеем:

1) π^T_{An +2}(x₁, … , x_{n + 2}) = (y₁, … , y_{n + 2}) ⇒ ⇒ π^T_{An +2} (x̅₁, … , x̅_{n + 1}) = (y̅₁, … , y̅_{n + 2});

2) π^T_{An +2}(0, x₂, … , x_{n + 2}) = π^T_{An +1}(x₂, … , x_{n + 2}), за исключением (x₁, … , x_{n + 2}) = (0, … , 0), а π^T_{An +2} = (0, … , 0) = 1.

Из вышесказанного следует, что преобразование π^T_{An +2} совпадает с h_{n + 2}.

В данной статье был рассмотрен способ построения обратимого полноциклового преобразование в базисе пороговых функций.