| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Уточнение оценок немонотонной сложности функций В. В. Кочергинabc, А. В. Михайловичbc a Московский государственный университет им. М. В. Ломоносова b Национальный исследовательский университет "Высшая школа экономики", г. Москва c Московский центр фундаментальной и прикладной математики
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 6, Pages DOI: https://doi.org/10.1134/S0001434623050218 
Реферативные базы данных:
  1. Введение, определения, формулировка основного результатаИсследуется схемная сложность (см., например, [1], [2]) функций $k$-значной логики в полных базисах, отличительной особенностью которых является деление функций из базиса на два типа: использование в схемах элементов, которым приписаны функции первого типа, не увеличивает значение сложности, а использование базисных функций второго типа увеличивает его на фиксированную величину. В настоящей работе в качестве “бесплатной” части базиса берется множество всех монотонных относительно стандартного порядка $0<1<\dots<k-1$ функций $k$-значной логики или, это непринципиально, какая-либо порождающая класс монотонных функций система функций. Постановка этой задачи восходит [3], [4] к задаче об инверсионной сложности булевых функций, заключающейся в нахождении для заданной функции минимально возможного числа инверторов (отрицаний) в схемах, допускающих помимо инверторов использование конъюнкторов и дизъюнкторов. Интерес к изучению указанной меры сложности возник в связи с тем, что на практике в некоторых технологиях изготовления реальных электронных схем элементы, реализующие отрицание, являются более дорогими и менее надежными, чем элементы, которые реализуют другие функции [3]. Исследуемую в работе задачу можно также рассматривать как обобщение на случай реализации функций многозначной логики частного случая более общей задачи (см, например, [5], [6]) о сложности реализации булевых функций в вырожденных базисах, содержащих элементы с нулевыми весами, формулируется следующим образом. Рассматриваются булевы схемы в базисе $B$, состоящем из элементов двух типов. Каждый элемент первого типа имеет положительную стоимость (вес), а каждый элемент второго типа – нулевую стоимость. Сложность схемы определяется как сумма весов (или число) элементов первого типа (ненулевая часть базиса $B$). Элементы второго типа не влияют на сложность схем. Настоящая работа является развитием работы [7], результаты которой значительно усилены как в части нижней, так и в части верхней оценок. В работе [7] можно также найти все необходимые определения и ознакомиться с историей вопроса. Здесь же напомним только основные определения. Пусть $P_k$ – множество всех функций $k$-значной логики, $k\ge2$, $M$ – класс всех функций из $P_k$, монотонных относительно порядка $0<1<\dots<k-1$. В настоящей работе исследуется сложность реализации функций $k$-значной логики схемами из функциональных элементов над базисами $B$, имеющими вид
$$
\begin{equation*}
B=M \cup \{\omega_1, \dots, \omega_p \}, \qquad \omega_i \in P_k \setminus M, \quad i=1, \dots, p, \quad p\ge 1,
\end{equation*}
\notag
$$
причем функциям из множества $M$ приписан нулевой вес, а функциям $\omega_1, \dots, \omega_p$ – единичный. Немонотонная сложность $I_B(S)$ схемы $S$ над базисом $B$ – это число немонотонных элементов схемы $S$ или суммарный вес всех элементов схемы $S$. Немонотонную сложность над базисом $B$ функции $k$-значной логики $f$, обозначаемую $I_B(f)$, определим как минимальную немонотонную сложность схем, вычисляющих над базисом $B$ функцию $f$. Пусть $f(x_1, \dots,x_n)$ – функция $k$-значной логики. Упорядоченную пару наборов $\widetilde{\alpha}=(\alpha_{1},\dots, \alpha_{n})$ и $\widetilde{\beta}=(\beta_{1},\dots, \beta_{n})$, $\widetilde{\alpha}, \widetilde{\beta} \in E_k^n$, будем называть обрывом для функции $f$, если выполнены следующие условия: ${\alpha_j} \le {\beta_j}$, $j=1, \dots, n$, и $f(\widetilde{\alpha}) > f(\widetilde{\beta})$. Пусть $C$ – цепь, имеющая вид $\widetilde{\alpha}_1, \widetilde{\alpha}_2, \dots,\widetilde{\alpha}_r$. Определим величины $d_C(f)$ и $u_C(f)$ следующим образом: $d_C(f)$ – число обрывов функции $f$ на парах вида $(\widetilde{\alpha}_i, \widetilde{\alpha}_{i+1})$; $u_C(f)$ – наибольшая длина $t$ подпоследовательности $\widetilde{\beta}_1, \widetilde{\beta}_2, \dots, \widetilde{\beta}_t$ последовательности $C$, удовлетворяющей условию $f(\widetilde{\beta}_1) > f(\widetilde{\beta}_2) > \dots > f(\widetilde{\beta}_t)$. Определим спад $d(f)$ и инверсионную силу $u(f)$ функции $f$ равенствами $d(f)=\max d_C(f)$ и $u(f)=\max u_C(f)$, где максимум берется по всем цепям $C$. Кроме того, для произвольного базиса $B$ описанного выше вида положим $D(B)=\max d(f)$ и $u(B)=\max u(f)$, где максимум берется по всем функциям $f$ из базиса $B$. Исчерпывающее описание немонотонной сложности булевых функций в базисе $B_0=M \cup \{ \overline{x} \}$, называемой в этом случае инверсионной сложностью, было получено Марковым [4], [8]: для любой булевой функции $f$ установлено равенство
$$
\begin{equation*}
I_{B_0}(f)=\bigl\lceil \log_{2} (d(f)+1)\bigr\rceil .
\end{equation*}
\notag
$$
В работе [9] для произвольной функции $k$-значной логики установлено точное значение немонотонной сложности над двумя естественными базисами $B_P=M \cup \{N_P(x) \}$ и $B_L=M \cup \{N_L(x) \}$, где $N_P(x)$ – отрицание Поста, т.е. функция $x+1 \pmod{k}$, а $N_L(x)$ – отрицание Лукасевича, т.е. функции $k-1-x$:
$$
\begin{equation*}
I_{B_P}(f)=\bigl\lceil \log_{2} (d(f)+1)\bigr\rceil, \qquad I_{B_L}(f)=\bigl\lceil \log_{k} (d(f)+1)\bigr\rceil .
\end{equation*}
\notag
$$
Эти равенства стали основой для нахождения близких к точным оценкам “обычной” сложности (когда подсчитывается общее число элементов в схеме) функций $k$-значной логики в базисах $B_P$ и $B_L$ [10], [11]. В случае произвольного базиса $B$ указанного вида из результатов работ [9], [12] следует, что найдется такая константа $c(B)$, что для любой функции $k$-значной логики $f$ выполняются неравенства
$$
\begin{equation*}
\bigl\lceil \log_{u(B)} (d(f)+1)\bigr\rceil-c(B) \leq I_B(f) \leq\bigl\lceil \log_{u(B)} (d(F)+1)\bigr\rceil.
\end{equation*}
\notag
$$
Эти оценки далеки от окончательных, так как константа $c(B)$ может оказаться сколь угодно большой: для любого заданного значения $N$ найдется базис $B_N$ вида $M \cup \{ h_N\}$ и функция $g_N$, для которых справедливо неравенство
$$
\begin{equation*}
\bigl\lceil \log_{u(B)} (d(g_N) + 1)\bigr\rceil -{I_{B_N}(g_N)} > N.
\end{equation*}
\notag
$$
В булевом случае удалось получить окончательный результат [13]: для любой булевой функции $f$ и любого базиса $B$ описанного вида справедливо равенство
$$
\begin{equation*}
I_B(f)=\biggl\lceil \log_2\biggl(\frac{d(f)}{D(B)}+1\biggr)\biggr\rceil,
\end{equation*}
\notag
$$
где $D(B)=\max \{ d(\omega_1), \dots, d(\omega_p) \}$. Для случая реализации функций $k$-значной логики существенное продвижение получено в работе [7]: установлено, что для любой функции $k$-значной логики $f$ и для произвольного базиса $B$ указанного вида выполняются неравенства
$$
\begin{equation*}
\biggl\lceil \log_{u(B)}\biggl(\frac{d(f)}{D(B)} + 1\biggr)\biggr\rceil- (\log_2 k+2) \le I_B(f) \le\biggl\lceil \log_{u(B)}\biggl(\frac{d(f)}{D(B)} + 1\biggr)\biggr\rceil+k^3.
\end{equation*}
\notag
$$
Основным результатом настоящей работы является доказательство следующих оценок немонотонной сложности функций многозначной логики. Теорема 1. Пусть базис $B$ имеет вид $B=M \cup \{\omega_1, \dots, \omega_p \}$, где $ \omega_i \in P_k \setminus M$, $i=1, \dots, p$. Тогда для любой функции $k$-значной логики $f$ справедливы неравенства 2. Нижняя оценкаВ основе доказательства нижней оценки немонотонной сложности функций $k$-значной логики лежат идеи из работы [12], которые позже были развиты в [7]. Лемма 1. Пусть последовательность $A=(a_1, a_2, \dots, a_r)$ элементов множества $\{ 0, 1, \dots, k-1 \}$ для некоторого натурального $l$ обладает следующим свойством: для всякой подпоследовательности $(a_{i_1}, a_{i_2}, \dots, a_{i_t})$ последовательности $A$, удовлетворяющей условию $a_{i_1} > a_{i_2} > \dots > a_{i_t}$, выполняется неравенство $t \le l$. Тогда последовательность $A$ можно разбить на $l$ непересекающихся неубывающих подпоследовательностей $A_1, \dots, A_l$, удовлетворяющих следующему свойству: для любых двух идущих подряд элементов $a_i$ и $a_{i+1}$ последовательности $A$, лежащих соответственно в подпоследовательностях $A_{j(i)}$ и $A_{j(i+1)}$, в случае выполнения неравенства $j(i) > j(i+1)$ должно выполняться и неравенство $a_i > a_{i+1}$. Доказательство. Проведем индукцию по параметру $l$.
Если параметр равен 1, то последовательность $A$ не убывает. Следовательно, сама последовательность $A$ и является искомым разбиением на $l$ последовательностей. Пусть для всех значений параметра, не превосходящих $l-1$, утверждение леммы справедливо. Докажем его для значения параметра, равного $l$. Если в последовательности $A$ не существует подпоследовательности $a_{i_1}, a_{i_2}, \dots, a_{i_{l}}$ длины в точности $l$, удовлетворяющей условию $a_{i_1} > a_{i_2} > \dots > a_{i_{l}}$, то достаточно воспользоваться предположением индукции. Если же хотя бы одна такая подпоследовательность существует, то выпишем все эти подпоследовательности длины $l$ (пусть их будет $p$ штук, $p \ge 1$):
$$
\begin{equation*}
\begin{gathered} \, a_{i(1,1)},\quad a_{i(2,1)},\quad \dots,\quad a_{i(l,1)}, \\ a_{i(1,2)},\quad a_{i(2,2)},\quad \dots,\quad a_{i(l,2)}, \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots\dots. \\ a_{i(1,p)},\quad a_{i(2,p)},\quad \dots,\quad a_{i(l,p)}. \end{gathered}
\end{equation*}
\notag
$$
Отметим следующий важный факт: условие $i(1,j_1)<i(1,j_2)$ влечет соотношение $a_{i(1,j_1)} \le a_{i(1,j_2)}$. Действительно, если бы было верно неравенство $a_{i(1,j_1)} > a_{i(1,j_2)}$, то для подпоследовательности
$$
\begin{equation*}
a_{i(1,j_1)}, \quad a_{i(1,j_2)},\quad a_{i(2,j_2)},\quad \dots,\quad a_{i(l,j_2)}
\end{equation*}
\notag
$$
длины $l+1$ выполнялись бы соотношения
$$
\begin{equation*}
a_{i(1,j_1)} > a_{i(1,j_2)} > a_{i(2,j_2)} > \dots > a_{i(l,j_2)},
\end{equation*}
\notag
$$
что противоречит условию леммы.
Теперь в качестве искомой подпоследовательности $A_l$ возьмем упорядоченную по увеличению значения номера (в последовательности $A$) последовательность элементов множества $\{ a_{i(1,1)}, a_{i(1,2)}, \dots, a_{i(1,p)} \}$. Пусть $a_i \in A_l$, $a_{i+1} \not\in A_l$. Покажем, что тогда $a_i > a_{i+1}$. Действительно, по построению элемент $a_i$ – начало некоторой строго убывающей подпоследовательности длины $l$ последовательности $A$. Если было бы верно неравенство $a_i \le a_{i+1}$, то, заменив в этой подпоследовательности элемент $a_i$ на элемент $a_{i+1}$, получили бы строго убывающую подпоследовательность длины $l$, начинающуюся с элемента $a_{i+1}$, что противоречит отсутствию элемента $a_{i+1}$ в подпоследовательности $A_l$. После удаления подпоследовательности $A_l$ из исходной последовательности $A$ для любой подпоследовательности $ a_{i(1)}, a_{i(2)}, \dots, a_{i(t)}$ получившейся последовательности, удовлетворяющей соотношениям $ a_{i(1)}> a_{i(2)} > \dots > a_{i(t)}$, выполняется неравенство $t \le l-1$. Применение предположения индукции завершает доказательство леммы. Лемма 2. Пусть схема $S$ реализует над базисом $B$ функцию $k$-значной логики $f$. Тогда справедливо неравенство Доказательство. Проведем индукцию по величине $I_B(S)$.
Если $I_B(S)=0$, то функция $f$ монотонна. Следовательно, $d(f)=0$. Пусть для любой схемы $S'$ над базисом $B$, для которой справедливо соотношение $I_B(S') \leq I_B(S) -1$, утверждение леммы выполняется. В схеме $S$ со входами $x_1, \dots, x_n$ выделим первую относительно некоторой правильной нумерации (т.е. нумерации, при которой на входы элементов не могут подаваться выходы элементов с бо́льшими номерами) вершину, которой приписана какая-либо функция из множества $ \{\omega_1, \dots, \omega_p \}$. Функциональный элемент, соответствующий этой вершине, обозначим через $E$, а функцию из немонотонной части базиса $B$, приписанную элементу $E$, обозначим через $\omega_E$. Пусть на выходе элемента $E$ реализуется функция $h(x_1, \dots, x_n)$. Преобразуем схему $S$, удалив из нее элемент $E$, создав вместо него еще один вход схемы, на который подадим переменную $y$. Полученная таким перестроением схема $S'$ реализует функцию $g(y, x_1, \dots, x_n)$, для которой выполняется соотношение
$$
\begin{equation*}
f(x_1, \dots, x_n)=g\bigl(h(x_1, \dots, x_n), x_1, \dots, x_n\bigr).
\end{equation*}
\notag
$$
Кроме того, справедливо равенство $I_B(S')=I_B(S)-1$.
Пусть цепь
$$
\begin{equation*}
C=(\widetilde{\alpha}_1, \widetilde{\alpha}_2, \dots,\widetilde{\alpha}_{r})
\end{equation*}
\notag
$$
имеет падение $d(f)$.
Рассмотрим последовательность $C'$ наборов длины $n+1$:
$$
\begin{equation*}
({h(\widetilde{\alpha}_1)}, \widetilde{\alpha}_1), \quad \dots,\quad ({h(\widetilde{\alpha}_r)}, \widetilde{\alpha}_r).
\end{equation*}
\notag
$$
Последовательность $C'$, вообще говоря, не является цепью, так как последовательность
$$
\begin{equation*}
C_h=\bigl({h(\widetilde{\alpha}_1)}, \dots, {h(\widetilde{\alpha}_r)}\bigr),
\end{equation*}
\notag
$$
вообще говоря, не является неубывающей. Обозначим через $l$ наименьшее натуральное число такое, что для всякой подпоследовательности $({h(\widetilde{\alpha}_{i_1})}, {h(\widetilde{\alpha}_{i_2})}, \dots, {h(\widetilde{\alpha}_{i_t})})$ последовательности $C_h$, удовлетворяющей условию ${h(\widetilde{\alpha}_{i_1})} > {h(\widetilde{\alpha}_{i_2})} > \dots > {h(\widetilde{\alpha}_{i_t})}$, выполняется неравенство $t \le l$. Отметим, что выполняются неравенства $l \le u(\omega_E) \le u(B)$.
В соответствии с леммой 1 разобьем последовательность $C_h$ на $l$ непересекающихся неубывающих последовательностей $C_{h1}, \dots, C_{hl}$. Пусть $p$ – минимальное значение среди всех значений индекса $i$, для которых элементы $h(\widetilde{\alpha_i})$ и $h(\widetilde{\alpha}_{i+1})$ последовательности $C_h$ лежат в разных подпоследовательностях. Без ограничения общности можно считать, что выполняется неравенство $h(\widetilde{\alpha_i}) > h(\widetilde{\alpha}_{i+1})$ (в ином случае присоединим начальный кусок первой подпоследовательности ко второй подпоследовательности). Полученное разбиение последовательности $C_h$ индуцирует разбиение последовательности $C'$ на подпоследовательности $C_1', C_2', \dots, C_l'$. Каждая из последовательностей наборов $C_j'$, $j=1, 2, \dots, l$, является цепью наборов длины $n+1$. Отметим, что первые разряды в наборах последовательности $C'$ уменьшают свое значение не более $d(h)\le d(\omega_E)$ раз. Поэтому в силу построения разбиения последовательности $C'$ при движении от элемента с номером $p+1$ последовательности $C'$ к ее концу количество переходов от одной подпоследовательности к подпоследовательности с меньшим номером не превосходит величины $d(\omega_E)-1$. Следовательно, при движении от начала последовательности $C'$ к ее концу количество всех переходов от одной подпоследовательности к другой также не превосходит величины $l d(\omega_E)$. Из этих соображений вытекает оценка
$$
\begin{equation*}
d(f)=d_C(f) \le d_{C_1'}(g)+d_{C_2'}(g)+\dots+d_{C_{l}'}(g)+l d(\omega_E).
\end{equation*}
\notag
$$
По предположению индукции для $i$, $i=1, 2, \dots, l$, выполняются соотношения
$$
\begin{equation*}
d_{C_i'}(g) \leq d(g) \leq D(B) u(B) \frac{(u(B))^{I_B(S')}-1}{u(B)-1} =D(B) u(B) \frac{(u(B))^{I_B(S)-1}-1}{u(B)-1} .
\end{equation*}
\notag
$$
Окончательно, учитывая неравенства $l\le u(\omega_E) \le u(B)$, $d(\omega_E)\le D(B)$, получаем
$$
\begin{equation*}
\begin{aligned} \, d(f)&=d_C(f) \le d_{C_1'}(g)+d_{C_2'}(g)+\dots+d_{C_{l}'}(g)+u(B) D(B) \\ &\leq D(B) u(B)\biggl(u(B) \frac{(u(B))^{I_B(S)-1}-1}{u(B)-1}+1\biggr) =D(B) u(B) \frac{(u(B))^{I_B(S)}-1}{u(B)-1}. \end{aligned}
\end{equation*}
\notag
$$
Лемма 2 доказана. Доказательство. Для любой схемы $S$, реализующей в базисе $B$ функцию $f$, в силу леммы 2 выполняется соотношение
$$
\begin{equation*}
\frac{d(f)}{D(B)} \leq \frac{(u(B))^{I_B(S)+1}-u(B)}{u(B)-1}.
\end{equation*}
\notag
$$
Поэтому
$$
\begin{equation*}
\frac{d(f)}{D(B)}+1 \leq \frac{(u(B))^{I_B(f)+1}-1}{u(B)-1}= (u(B))^{I_B(f)}+\frac{(u(B))^{I_B(f)}-1}{u(B)-1}<(u(B))^{I_B(f)} \, \frac{u(B)}{u(B)-1}.
\end{equation*}
\notag
$$
Логарифмируя, получаем нужное неравенство. Лемма 3 доказана. Из леммы 3 непосредственно следует нижняя оценка теоремы. 3. Верхняя оценкаСледуя [14] (случай булевых функций) и [9] (случай функций $k$-значной логики), введем понятие переключателя функций. Для упорядоченного набора функций $k$-значной логики
$$
\begin{equation*}
f_1(x_1, x_2, \dots, x_n), \quad f_2(x_1, x_2, \dots, x_n),\quad \dots, \quad f_s(x_1, x_2, \dots, x_n)
\end{equation*}
\notag
$$
будем называть $s$-переключателем функций $f_1, \dots, f_s$ любую функцию $k$-значной логики $g(z_1, \dots, z_s, x_1, x_2, \dots, x_n)$, удовлетворяющую условиям
$$
\begin{equation*}
\begin{gathered} \, g(1,0, \dots, 0, x_1, x_2, \dots, x_n) = f_1(x_1, x_2, \dots, x_n), \\ g(0,1, \dots, 0, x_1, x_2, \dots, x_n)= f_2(x_1, x_2, \dots, x_n), \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots. \\ g(0, \dots, 0, 1, x_1, x_2, \dots, x_n)= f_s(x_1, x_2, \dots, x_n). \end{gathered}
\end{equation*}
\notag
$$
В [9] установлен следующий важный факт, на котором основываются верхние оценки немонотонной сложности. Лемма 4 [9]. Пусть базис $B$ имеет следующий вид: $B=M \cup \{\omega\}$, где $ \omega \in P_k \setminus M$. Тогда для любого упорядоченного набора $ (f_{1}, \dots, f_{s}) $ функций $k$-значной логики найдется $s$-переключатель $g$ этого множества функций, удовлетворяющий условию Нам потребуется подобный факт, справедливый уже для базиса, содержащего несколько немонотонных функций. Формулировка будет более громоздкой, но при этом она позволит не переделывать доказательство леммы 4. Предварительно дадим некоторые дополнительные определения. Пусть базис $B$ имеет вид $B=M \cup \{\omega_1, \dots, \omega_p \}$, где $ \omega_i \in P_k \setminus M$, $i=1, \dots, p$. Тогда для фиксированной немонотонной функции $\psi$ из базиса $B$ произвольную схему $S$ над базисом $B$ будем называть $\psi$-правильной, если существует такая правильная нумерация всех элементов схемы $S$, что среди всех элементов схемы, которым приписаны немонотонные функции базиса, наименьший номер имеет элемент, которому приписана функция $\psi$. Будем также схему считать $\psi$-правильной, если всем элементам схемы приписаны монотонные функции базиса. Доказательство следующей леммы почти полностью совпадает с доказательством леммы 4, изложенным в [9]. Лемма 5. Пусть базис $B$ вида $B=M \cup \{\omega_1, \dots, \omega_p \}$, где $ \omega_i \in P_k \setminus M$, $i=1, \dots, p$, содержит немонотонную функцию $\psi$; пусть для функций $f_{1}, \dots, f_{s}$ и некоторого натурального $A$ найдутся $\psi$-правильные схемы $S_{1}, \dots, S_{s}$ над базисом $B$, реализующие эти функции и удовлетворяющие условию $I_B(S_j) \le A$, $j=1, \dots, s$. Тогда для упорядоченного набора функций $ (f_{1}, \dots, f_{s}) $ найдется $s$-переключатель $g$ и такая реализующая его $\psi$-правильная схема $S$ над базисом $B$, что выполняется неравенство $I_B(S) \le A$. Лемма 6. Пусть $f \in P_{k}$, $\psi \in P_k \setminus M$, $B=M \cup \{\psi\}$, $d(f)\le {d(\psi)}/{(k-1)^2}-1$. Тогда Доказательство. Пусть функции $f$ и $\psi$ зависят от $s$ и $t$ переменных соответственно.
Положим
$$
\begin{equation*}
\chi_i(x_1, \dots, x_t)=\begin{cases} 1,&\text{если }\psi(x_1, \dots, x_t) \ge i, \\ 0,&\text{если }\psi(x_1, \dots, x_t)<i, \end{cases} \qquad i=1,2, \dots, k-1.
\end{equation*}
\notag
$$
Отметим, что если пара $(\widetilde{\alpha},\widetilde{\beta})$ наборов из $E_k^t$ является обрывом для функции $\psi$, то эта пара наборов является обрывом хотя бы для одной из функций $\chi_i(x_1, \dots, x_t)$, $i=1,2, \dots, k-1$. Поэтому справедливо неравенство Обозначим через $\varphi$ функцию из построенного множества $\{ \chi_1, \chi_2, \dots, \chi_{k-1} \}$, имеющую наибольшее значение спада. Очевидно, что выполняются соотношения
$$
\begin{equation*}
d(\varphi) \ge \frac{d(\psi)}{k-1}, \qquad I_B(\varphi)=1.
\end{equation*}
\notag
$$
Положим $q=\lceil \log_2 k \rceil$. Представим исходную функцию $f=f(\widetilde{x})$ в виде набора из $q$ функций $f_1(\widetilde{x}), f_2(\widetilde{x}), \dots, f_{q}(\widetilde{x})$ в соответствии с двоичным представлением: Отметим, что для получения функции $f(\widetilde{x})$ из функций $f_1(\widetilde{x}), f_2(\widetilde{x}), \dots, f_{q}(\widetilde{x})$ достаточно использовать только монотонные функции. Теперь докажем, что для каждого $i$, $i=1, \dots, q$, истинно неравенство Это соотношение вытекает из следующего утверждения.Пусть подпоследовательность идущих подряд элементов максимальной (неуплотняемой) цепи наборов из множества $E_k^s$ для некоторого $i \in \{1, 2, \dots, q \}$ содержит $2^{i-1}$ обрывов для функции $f_i$. Тогда среди этих $2^{i-1}$ обрывов для функции $f_i$ есть хотя бы один обрыв для функции $f$. Действительно, пусть это не так, т.е. найдется подпоследовательность идущих подряд наборов исходной последовательности, в которой для функции $f_i$ содержится $2^{i-1}$ обрывов, а для функции $f$ обрывы отсутствуют. Тогда в этой подпоследовательности найдется, в свою очередь, подпоследовательность $\widetilde{\beta}_1, \widetilde{\beta}_2, \dots, \widetilde{\beta}_{2^{i}}$, удовлетворяющая следующим условиям: 1) $f_i(\widetilde{\beta}_{2j-1})=1$, $j=1, \dots, 2^{i-1}$; 2) $f_i(\widetilde{\beta}_{2j})=0$, $j=1, \dots, 2^{i-1}$; 3) $f(\widetilde{\beta}_1) \le f(\widetilde{\beta}_2) \le \dots \le f(\widetilde{\beta}_{2^{i}})$. Так как для любых двух соседних наборов $\widetilde{\beta}_{a}$ и $\widetilde{\beta}_{a+1}$ выполняются соотношения $f_i(\widetilde{\beta}_{a}) \neq f_i(\widetilde{\beta}_{a+1})$ и $f(\widetilde{\beta}_{a}) \le f(\widetilde{\beta}_{a+1})$, то справедливы неравенства $f(\widetilde{\beta}_{a})<f(\widetilde{\beta}_{a+1})$. С учетом этих неравенств получаем также неравенства
$$
\begin{equation*}
f(\widetilde{\beta}_{2j-1}) \ge 2^{q-i}+(j-1)2^{q-i+1}, \quad f(\widetilde{\beta}_{2j}) \ge j 2^{q-i+1}, \qquad j=1, \dots, 2^{i-1}.
\end{equation*}
\notag
$$
Тем самым при $j=2^{i-1}$ получаем неравенство $f(\widetilde{\beta}_{2^i}) \ge 2^q$, что невозможно.
Таким образом, неформально говоря, для любой максимальной цепи среди любых идущих подряд $2^i$ обрывов для функции $f_i$ найдется хотя бы один обрыв для функции $f$. Поэтому
$$
\begin{equation*}
d(f) \ge\biggl\lfloor \frac{d(f_i)}{2^{i-1}}\biggr\rfloor > \frac{d(f_i)}{2^{i-1}}-1.
\end{equation*}
\notag
$$
Следовательно,
Таким образом, для любого $i$, $i=1, \dots, q$, с учетом условий леммы выполняются неравенства
$$
\begin{equation*}
d(f_i)<(d(f)+1) (k-1) \le \frac{d(\psi)}{k-1} \le d(\varphi).
\end{equation*}
\notag
$$
Отсюда в силу того, что и функции $f_i$, и функция $\varphi$ принимают не более двух значений, имеем
$$
\begin{equation*}
I_B(f_i) \le I_{M\cup \{ \varphi \} }(f_i) \le 1, \qquad i=1, \dots, q.
\end{equation*}
\notag
$$
Как уже отмечалось, из функций $f_i$, $i=1, \dots, q$, можно построить монотонную формулу для функции $f$, поэтому $I_B(f) \le q=\lceil \log_2 k \rceil$. Лемма 6 доказана. Непосредственно из леммы 6 вытекает следующее утверждение. Лемма 7. Пусть $f \in P_{k}$, $\psi \in P_k \setminus M$, $B \supseteq M \cup \{\psi\}$, $D(B)=d(\psi)$, $d(f)\le {D(B)}/{(k-1)^2}$. Тогда для функции $f$ найдется $\psi$-правильная схема в базисе $B$, удовлетворяющая условию Лемма 8. Пусть базис $B$ имеет вид $B=M \cup \{\omega_1, \dots, \omega_p \}$, где $ \omega_i \in P_k \setminus M$, $i=1, \dots, p$. Тогда для любой функции $f$ найдется немонотонная функция $\psi$ из базиса $B$, для которой существует $\psi$-правильная схема $S$, реализующая функцию $f$ над базисом $B$ и удовлетворяющая условию Доказательство. Пусть $u(B)=s$, $D(B)=t$. Выберем в базисе $B$ функцию $\omega(x_1, \dots, x_l)$, удовлетворяющую условию $u(\omega)=s$, и функцию $\varphi$, удовлетворяющую условию $d(\varphi)=t$. Положим $B'=M \cup \{\omega, \varphi\}$. Искомую $\psi$-правильную схему $S$ будем строить в базисе $B'$ и в качестве функции $\psi$ будет выступать либо функция $\varphi$, либо функция $\omega$.
Утверждение леммы будем доказывать индукцией по величине
$$
\begin{equation*}
W(f)=\biggl\lceil \log_{s} \max\biggl(\frac{(k-1)^2 d(f)}{t}, 1\biggr)\biggr\rceil, \qquad W(f)=0,1,2, \dots,
\end{equation*}
\notag
$$
причем при $W(f)=0$ роль функции $\psi$ из формулировки леммы будет выполнять функция $\varphi$, а при $W(f) \ge 1$ – функция $\omega$.
База индукции $W(f)=0$. В этом случае выполняется неравенство Тогда в силу леммы 7 для функции $f$ найдется $\varphi$-правильная схема $S$ над базисом $M \cup \{ \varphi \}$, а следовательно, и над базисом $B'$, удовлетворяющая неравенству $I_{B'}(S) \le \lceil \log_2 k \rceil+1$.Шаг индукции. Пусть $W(f)\ge 1$ и для любой функции $g$, для которой справедливо соотношение $W(g) \le W(f) -1$, утверждение, доказываемое по индукции, выполняется. Будем считать, что функция $f$ зависит от $n$ переменных. Обозначим через $T_1$ множество $k$-значных наборов длины $n$, обладающих тем свойством, что для любой цепи $C$ с концом в таком наборе выполняется неравенство $d_C(f) \le s^{W(f)-1}t/(k-1)^2$, т.е.
$$
\begin{equation*}
T_1=\biggl\{ \widetilde{\alpha} \in E_k^n \biggm| d_C(f) \le \frac{s^{W(f)-1}t}{(k-1)^2} \text{ для любой цепи } C \text{ с концом } \widetilde{\alpha} \biggr\}.
\end{equation*}
\notag
$$
Далее, для $i=2, \dots, s-1$ обозначим через $T_i$ множество $k$-значных наборов длины $n$, обладающих тем свойством, что для любой цепи $C$ наборов из множества $E_k^n \setminus (T_1 \cup \dots \cup T_{i-1})$ с концом в таком наборе выполняется неравенство $d_C(f) \le s^{W(f)-1}t/(k-1)^2$, т.е.
$$
\begin{equation*}
\begin{aligned} \, T_i &=\biggl\{ \widetilde{\alpha} \in E_k^n \setminus (T_1 \cup \dots \cup T_{i-1}) \biggm| d_C(f) \le \frac{s^{W(f)-1}t}{(k-1)^2} \\ &\qquad \text{ для любой цепи }C \text{ с концом }\widetilde{\alpha},\, C \subset E_k^n \setminus (T_1 \cup \dots \cup T_{i-1}) \biggr\}. \end{aligned}
\end{equation*}
\notag
$$
Наконец, положим Отметим, что если $\widetilde{\alpha} \in T_i$ и $\widetilde{\beta} \prec \widetilde{\alpha}$, то $\widetilde{\beta} \in T_1 \cup \dots \cup T_{i-1}$, $i=1, \dots, s$. Теперь докажем, что для любой цепи $C$ наборов из множества $T_s$ также выполняется неравенство $d_C(f) \le s^{W(f)-1}t/(k-1)^2$. Действительно, предположив противное, получаем, что существует цепь $C_s$ с началом в наборе $\widetilde{\alpha}_s$, $\widetilde{\alpha}_s \in T_s$, для которой выполняется неравенство $d_{C_s}(f) > s^{W(f)-1}t$. С другой стороны, так как набор $\widetilde{\alpha}_s$ не лежит в множестве $T_{s-1}$, то найдется цепь $C_{s-1}$ с началом в наборе $\widetilde{\alpha}_{s-1}$, $\widetilde{\alpha}_{s-1} \in T_{s-1}$, и с концом в наборе $\widetilde{\alpha}_s$, $\widetilde{\alpha}_s \in T_s$, для которой выполняется неравенство $d_{C_{s-1}}(f) > s^{W(f)-1}t/(k-1)^2$. Аналогично, последовательно для $i=s-2, \dots, 1$ устанавливаем существование цепи $C_{i}$ с началом в наборе $\widetilde{\alpha}_{i}$, $\widetilde{\alpha}_{i} \in T_{i}$, и с концом в наборе $\widetilde{\alpha}_{i+1}$, $\widetilde{\alpha}_{i+1} \in T_{i+1}$, для которой выполняется неравенство $d_{C_{i}}(f) > s^{W(f)-1}t/(k-1)^2$. Тогда для цепи $C=C_1 \cup \dots \cup C_s$ справедливы соотношения
$$
\begin{equation*}
d_C(f)=d_{C_1}(f)+\dots+d_{C_s}(f) > s \frac {s^{W(f)-1} t}{(k-1)^2} =\frac{s^{W(f)}t}{(k-1)^2} \ge d(f),
\end{equation*}
\notag
$$
что противоречит определению величины $d(f)$.
Далее, для $ i=1, \dots, s$ положим
$$
\begin{equation*}
f_{i}(x_1, x_2, \dots, x_n)= \begin{cases} 0,&\text{если } (x_1, x_2, \dots, x_n) \in T_1 \cup \dots \cup T_{i-1}, \\ f(x_1, x_2, \dots, x_n),&\text{если }(x_1, x_2, \dots, x_n) \in T_i, \\ k-1,&\text{если }(x_1, x_2, \dots, x_n) \in T_{i+1} \cup \dots \cup T_{s}. \end{cases}
\end{equation*}
\notag
$$
В силу определения функций $f_i$ выполняются неравенства
$$
\begin{equation*}
d(f_i) \le \frac{s^{W(f)-1}t}{(k-1)^2}, \qquad i=1, \dots, s.
\end{equation*}
\notag
$$
Поэтому
$$
\begin{equation*}
\begin{aligned} \, W(f_i)&=\biggl\lceil \log_{s} \max\biggl(\frac{(k-1)^2d(f_i)}{t}, 1\biggr)\biggr\rceil \\ &\le\lceil \log \max(s^{W(f)-1}, 1)\rceil=W(f) -1, \qquad i=1, \dots, s. \end{aligned}
\end{equation*}
\notag
$$
В силу определения величины $s=u(\omega)$ найдется цепь
$$
\begin{equation*}
(\beta_{11}, \dots, \beta_{1l}), \quad (\beta_{21}, \dots, \beta_{2l}), \quad \dots, \quad (\beta_{s1}, \dots, \beta_{sl}),
\end{equation*}
\notag
$$
удовлетворяющая условию
$$
\begin{equation*}
\omega(\beta_{11}, \dots, \beta_{1l}) > \omega(\beta_{21}, \dots, \beta_{2l}) > \dots > \omega(\beta_{s1}, \dots, \beta_{sl}).
\end{equation*}
\notag
$$
Функции $\xi_1, \dots, \xi_l$ определим равенствами
$$
\begin{equation*}
\xi_j (x_1, \dots, x_n)=\beta_{ij}, \qquad i=1, \dots, s, \quad j=1, \dots, l,
\end{equation*}
\notag
$$
справедливыми для всех наборов $ (x_1, \dots, x_n)$ из множества $T_i$.
Далее положим $b_i=\omega(\beta_{i1}, \dots, \beta_{il})$, $i=1, \dots, s$. Теперь определим функции $\lambda_j (x)$, $j=1, \dots, k-1$:
$$
\begin{equation*}
\lambda_j (x)=\begin{cases} 0,&\text{если }x<j, \\ 1,&\text{если }x \ge j. \end{cases}
\end{equation*}
\notag
$$
И, наконец, введем функции $\mu_i (x_1, \dots, x_n)$, $i=1, \dots, s$:
$$
\begin{equation*}
\mu_i (x_1, \dots, x_n)=\begin{cases} 0,&\text{если }(x_1, \dots, x_n) \in T_1 \cup \dots \cup T_{i-1}, \\ 1,&\text{если }(x_1, \dots, x_n) \in T_i \cup \dots \cup T_{s}. \end{cases}
\end{equation*}
\notag
$$
Отметим, что все введенные функции монотонны. Теперь рассмотрим упорядоченный набор функций $(f_{1}(\widetilde{x}), \dots, f_{s}(\widetilde{x})) $. Отметим, что выполняются соотношения $W(f_i) \le W(f)-1$, $i=1, \dots, s$. В случае истинности равенства $W(f)=1$ для каждой функции $f_i$, $i=1, \dots, s$, по доказанному найдется $\varphi$-правильная схема $S_i$ над базисом $B'$, удовлетворяющая неравенству $I_{B'}(S_i) \le W(f)+\lceil \log_2 k \rceil $. При выполнении соотношения $W(f) \ge 2$ для каждой функции $f_i$, для которой верно равенство $W(f_i)=W(f)-1$, по предположению индукции найдется $\omega$-правильная схема $S_i$ над базисом $B'$, удовлетворяющая неравенству $I_{B'}(S_i) \le W(f)+\lceil \log_2 k \rceil $, а для каждой функции $f_j$, для которой верно соотношение $W(f_j) \le W(f)-2$, по предположению индукции выполняется неравенство и, следовательно, найдется $\omega$-правильная схема $S_j$ над базисом $B'$, удовлетворяющая неравенству $I_{B'}(S_j) \le W(f)+\lceil \log_2 k \rceil $.Таким образом, в любом случае выполнены условия леммы 5. Применяя эту лемму, получаем, что найдется $s$-переключатель $g(z_1, \dots, z_s, \widetilde{x})$ набора функций $(f_{1}(\widetilde{x}), \dots, f_{s}(\widetilde{x})) $ и схема $S_g$, реализующая функцию $g$ над базисом $B'$ и удовлетворяющая условию $I_{B'}(S_g) \le W(f)+\lceil \log_2 k \rceil $. Перестроим схему $S_g$, реализующую функцию $g(z_1, \dots, z_s, \widetilde{x})$ над базисом $B'$, подав на входы, соответствующие переменным $z_i$, $i=1, \dots,s$, функции
$$
\begin{equation*}
Z_i(x_1, \dots, x_n)=\min\bigl\{ \lambda_{b_i}(\omega (\xi_1 (x_1, \dots, x_n), \dots, \xi_l (x_1, \dots, x_n) )), \mu_i (x_1, \dots, x_n)\bigr\}.
\end{equation*}
\notag
$$
Учитывая, что функция $Z_i(x_1, \dots, x_n)$ обращается в единицу на наборах из множества $T_i$, а на остальных наборах равна нулю, получаем, что на наборах $(x_1, \dots, x_n)$ из множества $T_i$ справедливы равенства
$$
\begin{equation*}
g\bigl(Z_1(x_1, \dots, x_n), \dots, Z_s(x_1, \dots, x_n), x_1, \dots, x_n\bigr) =f_{i}(x_1, \dots, x_n)=f(x_1, \dots, x_n),
\end{equation*}
\notag
$$
$ i=1, \dots, s$.
Для реализации функций $Z_1, \dots, Z_s$ помимо использования монотонных функций потребовалось лишь однократное использование функции $\omega$. Схема $S$ реализует функцию $f$ над базисом $B'$, является $\omega$-правильной, и для нее справедливы соотношения
$$
\begin{equation*}
I_{B'}(S) \le I_{B'}(S_g)+1 \le W(f)+\lceil \log_2 k \rceil+1.
\end{equation*}
\notag
$$
Лемма 8 доказана. Лемма 9. Пусть базис $B$ имеет вид $B=M \cup \{\omega_1, \dots, \omega_p \}$, где $ \omega_i \in P_k \setminus M$, $i=1, \dots, p$. Тогда для любой функции $k$-значной логики $f$ справедливо неравенство Лемма 9 непосредственно следует из леммы 8 и завершает доказательство верхней оценки теоремы. 4. ЗаключениеИ нижняя, и верхняя оценки, сформулированные в теореме, несколько слабее соответствующих оценок из лемм 3 и 9. Во многих случаях из леммы 3 вытекает неравенство
$$
\begin{equation*}
I_B(f) \ge \biggl\lceil \log_{u(B)}\biggl(\frac{d(f)}{d(B)}+1\biggr)\biggr\rceil,
\end{equation*}
\notag
$$
в котором величина в правой части очень похожа на точное значение немонотонной сложности булевых функций, установленное в [13], с той лишь разницей, что у булевых функций инверсионная сила базиса всегда равна 2. Однако в случае реализации функций многозначной логики указанная нижняя оценка может как совпадать с величиной немонотонной сложности, так и отличаться от нее с ростом значности логики $k$ на величину порядка $\log k$. Например, с одной стороны, для функций $k$-значной логики $f$ и $\varphi$, $ \varphi \not\in M$, принимающих только два значения, немонотонная сложность функции $f$ в базисе $B_1=M \cup \{ \varphi \}$ определяется равенством
$$
\begin{equation*}
I_{B_1}(f)=\biggl\lceil \log_{u(B_1)}\biggl(\frac{d(f)}{d(B_1)}+1\biggr)\biggr\rceil,
\end{equation*}
\notag
$$
а с другой стороны, при реализации отрицания Лукасевича $N_L$ в базисе $B_2=M \cup \{ x_1+x_2+\dots+x_m \pmod{2} \}$ справедливо равенство в то время как при всех достаточно больших $m$ верно равенство
$$
\begin{equation*}
\biggl\lceil \log_{u(B_2)}\biggl(\frac{d(f)}{d(B_2)}+1\biggr)\biggr\rceil=1.
\end{equation*}
\notag
$$
Последний пример также показывает, что в случае реализации функций многозначной логики немонотонная сложность функции $f$ в базисе $B$, вообще говоря, не определяется только параметрами $d(f)$, $D(B)$ и $u(B)$. Действительно, при достаточно больших значениях $m$ при реализации в базисе $B_2$ функции $g$, принимающей два значения и удовлетворяющей условию $d(g)=d(N_L)$, истинно равенство $I_{B_2}(g)=1$, а следовательно, и равенство $I_{B_2}(f)-I_{B_2}(g)=\lceil \log_2 k\rceil -1$. При формулировке верхней оценки теоремы на основании оценки из леммы 9 во главу угла была поставлена компактность формулировки при некотором огрублении самой оценки. Это связано с тем, что качественный результат формулировка теоремы предоставляет очень наглядно, а до окончательного результата, заключающегося в нахождении точного значения немонотонной сложности каждой функции многозначной логики в произвольном базисе описанного вида, еще очень далеко. Последняя задача представляется очень тяжелой. 
Цитирование в формате AMSBIB
\RBibitem{KocMik23} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|