| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) О глубине мультиплексорной функции от “небольшого” числа адресных переменных С. А. Ложкин Московский государственный университет им. М. В. Ломоносова
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 5, Pages DOI: https://doi.org/10.1134/S0001434624050092 
Реферативные базы данных:
  1. ВведениеВ работе рассматривается задача, относящаяся к классу задач индивидуального синтеза, т.е. задач нахождения по заданной системе функций алгебры логики (ФАЛ) $F=(f_{1},\dots,f_{m})$ схемы $\Sigma_{F}$, $\Sigma_{F} \in \mathcal{U}$ ($\mathcal{U}$ – заданный класс схем), реализующей $F$, и такой, что $\Psi(\Sigma_{F})=\min \Psi(\Sigma)$, где $\Psi$ – заданный функционал сложности, а минимум берется по всем схемам $\Sigma$, $\Sigma \in \mathcal{U}$, реализующим систему $F$ (см., например, [1]). В данной работе эта задача решается для мультиплексорной ФАЛ (мультиплексора) $\mu_{n}$ порядка $n$, т.е. ФАЛ от $n+2^n$ булевых переменных (БП), где первые $n$ переменных называются “адресными”, оставшиеся $2^n$ – “информационными”, а значение функции равно значению той ее информационной БП, номер которой поступил на адресные БП. Сложность мультиплексорной ФАЛ изучалась в ряде работ. Известно (см., например, [2]), что сложность реализации ФАЛ $\mu_{n}$, $n=1,2,\dots$, как схемами из функциональных элементов (СФЭ), так и формулами в стандартном базисе асимптотически равна $2^{n+1}$. В работе [3] получена нижняя оценка вида $2^{n+1}+c_{1} \cdot 2^{n / 2}-O(2^{n / 4})$ и верхняя оценка вида $2^{n+1}+c_{2} \cdot 2^{n / 2}+O(2^{n / 4})$, где $c_1, c_2$ – некоторые положительные константы, для сложности реализации мультиплексора порядка $n$ в классе СФЭ над базисом $\textit{Б}_{0}$. Кроме того, в [2] была установлена асимптотика сложности ФАЛ $\mu_{n}$ в классе СФЭ в базисе $\{x \& y,\, x \oplus y,\, \overline x\}$, а в [4] были получены асимптотические оценки высокой степени точности вида
$$
\begin{equation*}
2^{n+1} \biggl(1+\frac{1}{2n} \pm O\biggl(\frac1n \log n\biggr)\biggr)
\end{equation*}
\notag
$$
для сложности ее реализации в классе $\pi$-схем. Что касается глубины, то в работе [5] было доказано, что глубина ФАЛ $\mu_{n}$ в базисе $\textit{Б}_{0}$ не превосходит величины $(n+4)$ для случая единичной глубины всех его функциональных элементов (ФЭ) и не превосходит $(n+3)$ в случае, если ФЭ “ $\&$” и “$\vee$” имеют единичную глубину, а ФЭ “$\neg$” – нулевую. Заметим также, что для последнего случая верхняя оценка $(n+3)$ указанной глубины следует из работ [6], [7]. В работе [8] было доказано, что значение глубины мультиплексорной ФАЛ порядка $n$ в стандартном базисе в случае, если ФЭ “$\&$” и “ $\vee$” имеют единичную глубину, а ФЭ “ $\neg$” – нулевую, равно 2, если $n=1$ и равно $n+2$, если $1 < n \leqslant 5$ или $n \geqslant 20$. При этом для случая $5 < n < 20$ были установлены нижняя оценка $n+2$ и верхняя оценка $n+3$ глубины ФАЛ $\mu_{n}$. В настоящей работе доказывается, что значение указанной глубины ФАЛ $\mu_{n}$ при $10 \leqslant n \leqslant 19$ равно $(n+2)$. Из полученных результатов вытекают аналогичные оценки для базиса, состоящего из всех элементарных конъюнкций и элементарных дизъюнкций от двух переменных. 2. Основные понятия и некоторые оценки глубины мультиплексорной функцииНапомним некоторые определения и факты, а также введем обозначения, связанные с реализацией ФАЛ в классах формул и СФЭ в базисе $\textit{Б}_{0}$, где ФЭ “ $\&$” и “$\vee$” имеют вес и глубину 1, а ФЭ “ $\neg$” – нулевые вес и глубину. Те понятия, которые в данной работе не определяются, могут быть найдены, например, в [9]. Будем использовать, в частности, описанное в [9] представление формул деревьями и вложение класса формул в класс СФЭ. Положим $B=\{0, 1\}$ и будем считать, как обычно, что множество
$$
\begin{equation*}
B^n=\underbrace{B \times \dots \times B}_{n \text{ раз}}=B^n(X(n)),
\end{equation*}
\notag
$$
где $n=1, 2, \dots$, представляет собой т.н. единичный $n$-мерный куб, т.е. множество наборов вида $\alpha=(\alpha_1, \dots, \alpha_n)$, являющихся наборами значений булевых переменных (БП) из множества $X(n)=\{x_1, \dots, x_n \}$. Определим, далее, множество $P_2(n)$ как множество всех ФАЛ от БП из $X(n)$, полагая, что каждая такая ФАЛ задается отображением вида $B^n \overset{f}{\longrightarrow} B$. Легко убедиться в том, что для ФАЛ $\mu_{n}$ справедливо представление
$$
\begin{equation}
\mu_{n}(x, y)=\bigvee_{\sigma \in B^n} K_\sigma(x)y_{\nu(\sigma)},
\end{equation}
\tag{1}
$$
где $x=(x_1, \dots, x_n)$ – набор ее адресных БП из $X(n)$, $y=(y_0, \dots, y_{2^n-1})$ – набор ее информационных БП, и для набора $\sigma$, $\sigma=(\sigma_1, \dots, \sigma_n) \in B^n$, формула $K_\sigma(x)$ – элементарная конъюнкция (ЭК) вида1 $x_1^{\sigma_1}x_2^{\sigma_2} \dotsb x_n^{\sigma_n}$ от БП $x$, обращающаяся в 1 только на наборе $\sigma$, а число $\nu(\sigma)= \sum_{i=1}^n\sigma_i 2^{n-i}$ – номер набора $\sigma$ при лексикографическом упорядочении наборов куба $B^n$. Через $L(\Sigma)$ будем обозначать сложность формулы или СФЭ $\Sigma$, т.е. число ФЭ “$\&$” и “$\vee$” в ней. Будем обозначать через $D(\Sigma)$ глубину формулы или СФЭ $\Sigma$, т.е. максимальное число ФЭ “ $\&$” и “$\vee$” этой схемы, лежащих на одной цепи. Под рангом $R(F)$ формулы $F$ будем понимать, как обычно, число вхождений в нее символов БП. Формула, в которой все ФЭ “$\neg$” присоединены к ее входам, называется формулой с поднятыми отрицаниями. Напомним, что глубиной ФАЛ $f$ называется величина $D(f)$, равная минимальной глубине формул или СФЭ, реализующих эту ФАЛ. Легко видеть, что $D(f)$ является также глубиной ФАЛ $f$ в базисе из всех элементарных конъюнкций и дизъюнкций ранга 2. Заметим (см., например, [9]), что для СФЭ $\Sigma$ без “ висячих” ФЭ и с одним выходом справедливо следующее неравенство:
$$
\begin{equation}
D(\Sigma) \geqslant \lceil \log_2 (L(\Sigma)+1)\rceil ,
\end{equation}
\tag{2}
$$
а если $\Sigma$ реализует ФАЛ, существенно зависящую от $N$ БП, то Следуя [10], будем говорить, что непустое подмножество $U$ БП ФАЛ $f$ забивает ее БП $x$, $x \notin U$, если подстановкой некоторых констант вместо БП множества $U$ из ФАЛ $f$ можно получить ФАЛ, не зависящую существенно от $x$. Множество $X$, состоящее из БП ФАЛ $f$, будем называть незабиваемым, если $|X| \geqslant 2$ и любая БП $x$, $x \in X$, не забивается множеством $X \setminus\{x\}$ или если $|X|=1$ и БП $x$, $x \in X$, является существенной БП ФАЛ $f$ (в этом случае будем называть множество $X$ тривиальным незабиваемым множеством). Переменная, принадлежащая некоторому нетривиальному незабиваемому множеству БП ФАЛ $f$, считается незабиваемой БП этой ФАЛ. Заметим, что информационные БП образуют незабиваемое множество переменных ФАЛ $\mu_{n}$. Заметим также, что согласно доказательству теоремы 7.4 [10; ч. 2, § 7] в результате подстановки “подходящих” констант вместо любых $(|U|-1)$ БП, принадлежащих нетривиальному незабиваемому множеству $U$ БП ФАЛ $f$, из произвольной СФЭ $\Sigma$, реализующей $f$, можно “устранить” не менее, чем $(2|U|-2)$, двухвходовых ФЭ. С помощью этого факта, учитывая (2), (3), незабиваемость множества информационных БП ФАЛ $\mu_{n}$, а также то, что при любой подстановке констант вместо части ее информационных БП получается ФАЛ, существенно зависящая от всех оставшихся БП, в [8] было доказано, что если $n \geqslant 2$, и что $D(\mu_{1}) \geqslant 2$.Используя при $n=1$ представление (1), а при $n=2, \dots, 5$, кроме того, – разложение ФАЛ $\mu_{n}$ по первым $(n-1)$ адресным БП, в [8] было установлено, что $D(\mu_{1})=2$ и $D(\mu_{n})=n+2$, если $2 \leqslant n \leqslant 5$. Там же на базе специальных представлений ФАЛ $\mu_{n}$, где $n \geqslant 20$, было доказано, что в этом случае $D(\mu_{n}) \leqslant n+2$. Кроме того, было приведено новое доказательство того, что $D(\mu_{n}) \leqslant n+3$ при любом натуральном $n$. Таким образом, к настоящему моменту известно, что если $2 \leqslant n \leqslant 5$ или $n \geqslant 20$, а также то, что при всех остальных значениях $n$.Основным результатом данной работы является следующее утверждение. Теорема 1. При любом натуральном $n$, где $10 \leqslant n \leqslant 20$, имеет место неравенство $D(\mu_{n}) \leqslant n+2$. 3. Формульные представления мультиплексорных и некоторых других функций, верхние оценки их глубиныНапомним ряд понятий, обозначений, утверждений и конструкций из работ [8], [9], связанных с реализацией мультиплексорных ФАЛ. Для набора $\alpha$, $\alpha \in B^n$, через $S_\alpha$ и $H_\alpha$ будем обозначать т.н. (единичную) сферу и (единичный) шар с центром $\alpha$ в кубе $B^n$ соответственно, если $S_\alpha$ состоит из всех тех наборов $\beta$ куба $B^n$, которые отличаются от набора $\alpha$ ровно в 1 разряде, а $H_\alpha=S_\alpha \cup \{\alpha \}$. Для множества $A$, $A \subseteq B^n$, через $\chi_A$ будем, как правило, обозначать его характеристическую ФАЛ из $P_2(n)$. Известно (см., например, [11], [12]), что единичный куб $B^n$ при $n=2^k-1$, где $k$ – любое натуральное число, может быть разбит на (непересекающиеся) единичные шары, а при $n=2^k$ – на (непересекающиеся) единичные сферы. Рассмотрим указанное разбиение куба $B^7$ от БП $(x', u)$, где $x'=(x_1, \dots, x_6)$, на непересекающиеся единичные шары $\widehat H_1, \dots, \widehat H_{16}$ с центрами $\widehat \alpha^{(1)}, \dots, \widehat \alpha^{(16)}$ соответственно, где $\widehat \alpha^{(i)}= (\alpha^{(i)}, \beta_i)$ и $\alpha^{(i)} \in B^6(x')$, $\beta_i \in B$ для всех $i$, $i \in [1, 16]$. Будем считать, что в соответствии с [11], [12] центры $\widehat \alpha^{(i)}$, $i \in [1, 16]$, являются всевозможными линейными комбинациями над полем $GF(2)$ строк матрицы $\mathcal M$ вида
$$
\begin{equation}
\mathcal M= \begin{array}{|c|c|c|c|c|c|c|c|} \hline x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & u \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ \hline \end{array},
\end{equation}
\tag{5}
$$
рассматриваемых как элементы куба $B^7(x', u)$. Будем считать также, что при этом $\beta_i= 0$, если $i \in [1, 8]$, и $\beta_i=1$ в остальных случаях, а набор $\gamma^{(i)}= \alpha^{(i+8)}$ получается из набора $\alpha^{(i)}$, $i \in [1, 8]$, инвертированием разрядов с номерами 1, 2. Заметим, что единичные шары $H_1, \dots, H_8$ куба $B^6(x')$ с центрами $\alpha^{(1)}, \dots, \alpha^{(8)}$ соответственно попарно не пересекаются и покрывают весь этот куб за исключением множества наборов $G=\{\gamma^{(i)}\}^8_{i=1}$. Следовательно, единичные сферы $S_1, \dots, S_8$ указанных шаров покрывают множество наборов $B^6(x') \setminus (A \cup G)$, где $A=\{\alpha^{(i)} \}^8_{i=1}$. Заметим также, что если $\chi_{S}(x_1, \dots, x_l)$ – характеристическая ФАЛ единичной сферы $S$ с центром $\beta=(\beta_1, \dots, \beta_l)$ в кубе $B^l$, то
$$
\begin{equation}
\chi_{S}(x_1, \dots, x_l)x_i^{\overline \beta_i}=x_1^{\beta_1} \dotsb x_{i-1}^{\beta_{i-1}} x_i^{\overline \beta_i} x_{i+1}^{\beta_{i+1}} \dotsb x_l^{\beta_l}, \qquad 1 \leqslant i \leqslant l.
\end{equation}
\tag{6}
$$
Данное соотношение показывает, что любую ЭК, соответствующую $i$-й точке $(\beta_1, \dots, \beta_{i-1}, \overline \beta_i, \beta_{i+1}, \dots, \beta_l)$, где $i=1, \dots, l$, сферы $S$, можно “выщепить” умножением ФАЛ $\chi_{S}(x_1, \dots, x_l)$ на “букву” $x_i^{\overline \beta_i}$. Из (6) следует, что
$$
\begin{equation}
\chi_{H}(x_1, \dots, x_l) \cdot (x_1^{\overline \beta_1} \cdot y^{(1)} \vee \dots \vee x_l^{\overline \beta_l} \cdot y^{(l)})=\chi_{S}(x_1, \dots, x_l) \cdot \mu_l(x_1, \dots, x_l, y_0, \dots, y_{2^l-1}),
\end{equation}
\tag{7}
$$
где $\chi_{H}(x_1, \dots, x_l)$ – характеристическая ФАЛ шара $H$ с центром $\beta$, а БП $y^{(i)}$, где $i=1, \dots, l$, – информационная БП ФАЛ $\mu_l$, связанная с $i$-й точкой сферы $S$. Будем называть матрицу $M$, состоящую из элементов множества $\{0, 1, 2\}$, отделимой, если любые два ее столбца хотя бы в одной строке имеют различные булевские значения. Легко видеть, что для отделимой матрицы $M$ с $t$ строками и $l$ столбцами выполняется неравенство $t \geqslant \lceil \log l \rceil$. Кроме того, согласно [8], [13] для нее имеет место равенство
$$
\begin{equation}
\chi_{H}(x_1, \dots, x_l) =\operatorname*{\&}_{1 \leqslant i \leqslant t}\biggl(\operatorname*{\&}_{\substack{1 \leqslant j \leqslant l\\ M \langle i, j\rangle= 0}} \overline x_j \vee \operatorname*{\&}_{\substack{1 \leqslant j \leqslant l\\ M \langle i, j\rangle= 1}} \overline x_j\biggr),
\end{equation}
\tag{8}
$$
где $\chi_{H}$ – характеристическая ФАЛ единичного шара $H$ куба $B^l$ с центром в его нулевом наборе, а $M \langle i, j\rangle$ – элемент матрицы $M$, расположенный в ее строке с номером $i$ и столбце с номером $j$. С помощью (8) при $l=6$ для соответствующей характеристической ФАЛ $\chi_{H}=\psi(x_1, \dots, x_6)$ на основе матрицы $M$ вида
$$
\begin{equation*}
\begin{array}{|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 & 0 & 1 \\ \hline 2 & 0 & 1 & 0 & 1 & 2 \\ \hline \end{array}
\end{equation*}
\notag
$$
можно построить следующую формулу:
$$
\begin{equation}
\psi(x_1, \dots, x_6)=\mathcal F_\psi=(\overline x_1 \overline x_2 \overline x_3 \vee \overline x_4 \overline x_5 \overline x_6) \cdot (\overline x_1 \overline x_4 \overline x_5 \vee \overline x_2 \overline x_3 \overline x_6) \cdot (\overline x_2 \overline x_4 \vee \overline x_3 \overline x_5).
\end{equation}
\tag{9}
$$
Заметим, что (при подходящей расстановке скобок) глубина как самой формулы $\mathcal F_\psi$, так и любой формулы вида $\mathcal F_\psi \cdot \mathcal F^{(1)} \cdot \mathcal F^{(2)} \cdot \mathcal F^{(3)} \cdot \mathcal F^{(4)}$, где $R(\mathcal F^{(1)})= R(\mathcal F^{(2)})=1$, $D(\mathcal F^{(3)}) \leqslant 2$, $ D(\mathcal F^{(4)}) \leqslant 3$ будет не больше 5.
4. Доказательство теоремыРассмотрим сначала случай $n=10$. Пусть $x=(x_1, \dots, x_{10})$ и $y=(y_0, \dots, y_{2^{10}-1})$ – наборы адресных и информационных БП ФАЛ $\mu_{10}$ соответственно, а также пусть $x'=(x_1, \dots, x_6)$ и $x''=(x_7, x_8, x_9, x_{10})$. Воспользуемся построенным выше на основе матрицы $\mathcal M$ вида (5) разбиением куба $B^6(x')$ на подмножества $H_1, \dots, H_{8}, A, G$. Обозначим через $y_{i, j, \sigma''}$, где $i \in [1, 8]$, $j \in [1, 8]$ и $\sigma'' \in B^4(x'')$, информационную БП $y_{\nu(\sigma', \sigma'')}$ ФАЛ $\mu_{10}(x, y)$, где $\sigma'$ – набор из $B^6$, который равен $\alpha^{(i)}$, если $j=7$, равен $\gamma^{(i)}$, если $j= 8$ и отличается от набора $\alpha^{(i)}$ в $j$-м разряде, если $j \in [1, 6]$. Положим $M=\{(1110),(1111) \} \subset B^4(x'')$ и заметим, что2
$$
\begin{equation}
\chi_M(x'')=x_7x_8x_9=K_{(111)}(\widehat x''), \qquad \overline \chi_M(x'')=\overline x_7 \vee \overline x_8 \vee \overline x_9=J_{(111)}(\widehat x''),
\end{equation}
\tag{10}
$$
где $\widehat x''=(x_7, x_8, x_9)$. Рассмотрим формулы
$$
\begin{equation}
\mathcal F_1(x, y)=\bigvee_{i=1}^8 \chi_{H_i}(x') \cdot \overline \chi_M(x'') \operatorname*{\ }_{\sigma'' \in B^4 \setminus M} \bigl(J_{\sigma''}(x'') \vee x_1^{\overline \alpha_1^{(i)}} \cdot y_{i, 1, \sigma''} \vee \dots \vee x_6^{\overline \alpha_6^{(i)}} \cdot y_{i, 6, \sigma''}\bigr),
\end{equation}
\tag{11}
$$
$$
\begin{equation}
\mathcal F_2(x, y)=\bigvee_{i=1}^8 \chi_{H_i}(x') \cdot \chi_M(x'') \operatorname*{\ }_{\sigma''=(111\sigma_{10}) \in M} \bigl(x_{10}^{\overline \sigma_{10}} \vee x_1^{\overline \alpha_1^{(i)}} \cdot y_{i, 1, \sigma''} \vee \dots \vee x_6^{\overline \alpha_6^{(i)}} \cdot y_{i, 6, \sigma''}\bigr),
\end{equation}
\tag{12}
$$
в которых для реализации ФАЛ $\chi_{H_i}(x')$ использована формула вида $\mathcal F_\psi$ из равенства (9), а для реализации ФАЛ $\chi_M(x'')$ и $\overline \chi_M(x'')$ – их представления (10). Заметим, что в силу (7), (11), (12) ФАЛ $f_1(x, y)$ и $f_2(x, y)$, реализуемые формулами $\mathcal F_1$ и $\mathcal F_2$, совпадают с ФАЛ $\mu_{10}(x, y)$ на множестве тех наборов значений БП $x$, которые принадлежат множествам
$$
\begin{equation*}
\bigl(B^6 \setminus (A \cup G)\bigr) \times (B^4 \setminus M) \qquad\text{и}\qquad \bigl(B^6 \setminus (A \cup G)\bigr) \times M
\end{equation*}
\notag
$$
соответственно, а вне каждого из этих множеств связанная с ним ФАЛ $f_i$, $i \in [1, 2]$, равна 0. При этом из равенств (11), (12) и последующих уточнений к ним, а также из замечаний к равенству (9) следует, что
$$
\begin{equation}
D(\mathcal F_1) \leqslant 11, \qquad D(\mathcal F_2) \leqslant 9.
\end{equation}
\tag{13}
$$
Кроме того, из указанных выше замечаний к равенству (9) вытекает, что в формулы $\mathcal F_1$ и $\mathcal F_2$ без увеличения их глубины (при подходящем выборе подформул $\mathcal F^{(1)}-\mathcal F^{(4)}$) можно “ вставить” ЭК ранга 10 и 11 соответственно. Перейдем к реализации ФАЛ $\mu_n(x, y)$ на множестве остальных наборов значений ее адресных БП, т.е. на множестве Напомним, что $A=\{\alpha^{(i)} \}^8_{i=1}$ и $G=\{\gamma^{(i)}\}^8_{i=1}$, где для любого $i$, $i \in [1, 6]$, наборы $\alpha^{(i)}=(\alpha_1^{(i)}, \dots, \alpha_6^{(i)})$ и $\gamma^{(i)}=(\gamma_1^{(i)}, \dots, \gamma_6^{(i)})$ куба $B^6(x')$ отличаются друг от друга в разрядах 1, 2, т.е. по БП $x_1, x_2$. Отсюда следует, что
$$
\begin{equation}
K_{\alpha^{(i)}}(x') \vee K_{\gamma^{(i)}}(x')=(x_1^{\alpha_1^{(i)}} \cdot x_2^{\alpha_2^{(i)}} \vee x_1^{\overline \alpha_1^{(i)}} \cdot x_2^{\overline \alpha_2^{(i)}}) \ x_3^{\alpha_3^{(i)}} \dotsb x_6^{\alpha_6^{(i)}}=Q_i(x'),
\end{equation}
\tag{14}
$$
где глубина формулы $Q_i(x')$ равна 3. Введем множество наборов $\widetilde M$ куба $B^4(x'')$, где для которого, очевидно, $\chi_{\widetilde M}(x'')=x_7x_8$, и рассмотрим формулы
$$
\begin{equation}
\mathcal F_3(x, y)=\bigvee_{i=1}^8 Q_i(x') \overline \chi_{\widetilde M}(x'') \operatorname*{\ }_{\sigma'' \in B^4 \setminus \widetilde M} \bigl(J_{\sigma''}(x'') \vee x_1^{\alpha_1^{(i)}} \cdot y_{i, \sigma'', 7} \vee x_1^{\overline \alpha_1^{(i)}} \cdot y_{i, \sigma'', 8}\bigr),
\end{equation}
\tag{15}
$$
$$
\begin{equation}
\mathcal F_4(x, y)=\bigvee_{i=1}^8 Q_i(x') \chi_{\widetilde M}(x'') \operatorname*{\ }_{\sigma'' \in \widetilde M} \bigl(J_{\sigma''}(x'') \vee x_1^{\alpha_1^{(i)}} \cdot y_{i, \sigma'', 7} \vee x_1^{\overline \alpha_1^{(i)}} \cdot y_{i, \sigma'', 8}\bigr),
\end{equation}
\tag{16}
$$
реализующие ФАЛ $f_3(x, y)$ и $f_4(x, y)$ соответственно. Заметим, что ФАЛ $f_3$ и $f_4$ совпадают с ФАЛ $\mu_{10}(x, y)$ на множествах наборов
$$
\begin{equation*}
(A \cup G) \times \bigl(B^4(x'') \setminus \widetilde M\bigr) \qquad\text{и}\qquad (A \cup G) \times \widetilde M
\end{equation*}
\notag
$$
соответственно, а вне указанных множеств равны 0. При этом из (14)–(16) следует, что и что каждую из формул $\mathcal F_3$, $\mathcal F_4$ можно без увеличения их глубины домножить на ЭК ранга 22. Таким образом, формула
$$
\begin{equation}
\mathcal F(x, y)=\mathcal F_1(x, y) \vee \mathcal F_2(x, y) \vee \mathcal F_3(x, y) \vee \mathcal F_4(x, y)
\end{equation}
\tag{18}
$$
является искомой формулой, которая реализует ФАЛ $\mu_{10}(x, y)$ и имеет в силу (13), (17) глубину 12. Для завершения доказательства при любом $k$, $ k \in [11, 20]$, положим
$$
\begin{equation*}
\widetilde x=(x_1, \dots, x_k)=(x, \check x), \qquad \widetilde y=(y_0, \dots, y_{2^k- 1})=(\widetilde y^{(0)}, \dots, \widetilde y^{(2^{k-10}-1)}),
\end{equation*}
\notag
$$
где $x=(x_1, \dots, x_{10})$, $\check x=(x_{11}, \dots, x_k)$ и для любого $i$, $i= 0, 1, \dots, (2^{k-10}-1)$, набор $\widetilde y^{(i)}$ представляет собой поднабор из $2^{10}$ подряд идущих БП набора $\widetilde y$. При этом для ФАЛ $\mu_k(\widetilde x, \widetilde y)$ будет справедливо представление
$$
\begin{equation*}
\mu_k(\widetilde x, \widetilde y)=\bigvee_{\check \sigma=(\sigma_1, \dots, \sigma_k) \in B^{k-10}} K_{\check \sigma}(\check x) \cdot \mu_{10}(x, \widetilde y^{(\nu(\check \sigma))}),
\end{equation*}
\notag
$$
из которого с учетом (18) вытекает, что формула
$$
\begin{equation}
\widetilde{\mathcal F}(\widetilde x, \widetilde y)=\bigvee_{\check \sigma \in B^{k- 10}} \bigvee^{4}_{s=1} K_{\check \sigma}(\check x) \cdot \mathcal F_s(x, \widetilde y^{(\nu(\check \sigma))})
\end{equation}
\tag{19}
$$
реализует ФАЛ $\mu_k(\widetilde x, \widetilde y)$. В первой части доказательства отмечалось, что для любой формулы $\mathcal F_s$, $s \in [1, 4]$, при условии $(k-10) \leqslant 10$ выполняется неравенство
$$
\begin{equation*}
D(K_{\check \sigma}(\check x) \cdot \mathcal F_s(x, y)) \leqslant D(\mathcal F_s).
\end{equation*}
\notag
$$
Следовательно, формула $\widetilde{\mathcal F}(\widetilde x, \widetilde y)$ является искомой, так как согласно (13), (17), (19) удовлетворяет соотношению
$$
\begin{equation*}
D(\widetilde{\mathcal F}(\widetilde x, \widetilde y)) \leqslant 12+(k-10)=k+2.
\end{equation*}
\notag
$$
Теорема доказана. 
Цитирование в формате AMSBIB
\RBibitem{Loz24} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|