| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях) О существовании и свойствах выпуклых продолжений булевых функций Д. Н. Баротов Финансовый университет при Правительстве Российской Федерации, г. Москва
Английская версия:
Mathematical Notes, 2024, Volume 115, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434624030210 
Реферативные базы данных:
  1. ВведениеНа протяжении многих десятилетий в истории цифровой науки булевы переменные были основными переменными, используемыми в большинстве компьютерных операций. Встречается много основных задач, связанных с булевыми переменными, а некоторые задачи, несмотря на зрелость области, не имеют удовлетворительных методов решения. Среди них проблема решения булевых уравнений и систем булевых уравнений [1]. Эта задача имеет множество приложений, таких как синтез, моделирование и тестирование цифровых сетей и систем СБИС, кодирование выходных данных и назначение состояний конечных автоматов, временной анализ и генерация тестов с задержкой-сбоем для комбинационных схем, автоматическая генерация тестовых шаблонов, определение начального состояния в схемах, содержащих петли обратной связи. В области криптографии у этой задачи есть приложения для анализа и взлома блочных шифров, поскольку их можно свести к проблеме решения крупномасштабной системы булевых уравнений [1]–[3]. И в настоящее время теория булевых функций – увлекательная область исследований в области дискретной математики с приложениями к криптографии и теории кодирования [4]. Булевы функции с высокой нелинейностью могут быть использованы для внесения путаницы в алгоритмы блочного шифрования [4], [5]. В связи с этим развивается множество новых направлений и алгоритмов решения систем булевых уравнений. Одно из направлений заключается в том, что, во-первых, система булевых уравнений, заданная над кольцом булевых полиномов, преобразуется в систему уравнений над полем действительных чисел, а во-вторых, преобразованная система сводится либо к задаче численной минимизации соответствующей целевой функции [6]–[8], либо к задаче MILP или QUBO [9], либо к системе полиномиальных уравнений, решаемой на множестве целых чисел [1], либо к эквивалентной системе полиномиальных уравнений, решаемой символьными методами [10]. Имеется много способов, позволяющих преобразовать систему булевых уравнений в задачу непрерывной минимизации, поскольку принципиальное отличие таких методов от “переборных” алгоритмов локального поиска состоит в том, что на каждой итерации алгоритма сдвиг по антиградиенту производится по всем переменным одновременно [2], [3], [6]–[8], [11]–[14]. Но одна из основных проблем, возникающая при применении этих способов, заключается в том, что минимизируемая целевая функция в искомой области может иметь множество локальных минимумов, что значительно усложняет их практическое использование [2], [3], [6]–[8], [11], [12]. По теореме Баротова полилинейное продолжение булевой функции тоже играет важную роль для уменьшения числа локальных минимумов целевой функции [3], [11]. По данной тематике недавно в работе [11] были найдены явные формы полилинейных продолжений для произвольных функций, определенных на множестве вершин $n$-мерного единичного куба, произвольного куба и параллелепипеда, и в каждом конкретном случае была доказана единственность соответствующего полилинейного продолжения. В данной работе рассматривается задача существования выпуклого продолжения произвольной булевой функции $f(x_1,x_2,\dots,x_n)$ на множество $[0,1]^n$. Конструируется $f_C(x_1,x_2,\dots,x_n)$ – выпуклое продолжение произвольной булевой функции $f(x_1,x_2,\dots,x_n)$ на множество $[0,1]^n$. На основе одного конструированного выпуклого продолжения $f_C(x_1,x_2,\dots,x_n)$ доказывается, что для любой булевой функции $f(x_1,x_2,\dots,x_n)$ существует бесконечно много функций, каждая из которых является ее выпуклым продолжением на $[0,1]^n$. Также конструктивно доказывается, что для любой булевой функции $f(x_1,x_2,\dots,x_n)$ существует единственная функция $f_{DM}(x_1,x_2,\dots,x_n)$, являющаяся максимальной среди всех ее выпуклых продолжений на множество $[0,1]^n$. В конце работы дается одно из возможных приложений полученных результатов, а именно, конструктивно утверждается, что задача решения системы булевых уравнений может быть сведена к задаче минимизации функции, любой локальный минимум которой в искомой области является глобальным минимумом. 2. Определения и обозначенияПусть
$$
\begin{equation*}
\mathbb B^n=\bigl\{(b_1,b_2,\dots,b_n)\colon b_1,b_2,\dots,b_n\in\{0,1\}\bigr\}
\end{equation*}
\notag
$$
– множество всевозможных двоичных слов (булевых векторов) длины $n$,
$$
\begin{equation*}
\mathbb K^n=\bigl\{(x_1,x_2,\dots,x_n)\colon x_1,x_2,\dots,x_n\in[0,1]\bigr\}
\end{equation*}
\notag
$$
– $n$-мерный куб, натянутый на булевы векторы длины $n$. Пусть $\mathrm{int}(\mathbb K^n)=\{(x_1,x_2,\dots,x_n)\colon x_1,x_2,\dots,x_n\in(0,1)\}$ – множество внутренних точек куба $\mathbb K^n$. Пусть $\rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))=|a_1-b_1|+|a_2-b_2|+\dotsb+|a_n-b_n|$ – расстояние (по Хэммингу) между булевыми векторами $(b_1,b_2,\dots,b_n)$ и $(a_1,a_2,\dots,a_n)$. Пусть
$$
\begin{equation*}
\begin{aligned} \, \boldsymbol\Lambda(x_1,x_2,\dots,x_n) &=\biggl\{(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots,\lambda_{(1,1,\dots,1)})\in\mathbb K^{2^n}\colon \\ &\qquad \sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot(b_1,b_2,\dots,b_n) =(x_1,x_2,\dots,x_n), \\ &\qquad\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n}\lambda_{(b_1,b_2,\dots,b_n)}=1\biggr\} \end{aligned}
\end{equation*}
\notag
$$
– множество весовых коэффициентов, используемых для представления точки $(x_1, x_2,\dots,x_n)$ как выпуклой комбинации вершин куба $\mathbb K^n$. Пусть
$$
\begin{equation*}
\begin{aligned} \, \mathbb P^n_{(b_1,b_2,\dots,b_n)} &=\bigl\{(x_1,x_2,\dots,x_n)\in\mathbb K^n\colon \\ &\qquad (2b_1-1)x_1+(2b_2-1)x_2 +\dotsb+(2b_n-1)x_n>b_1+b_2+\dotsb+b_n-1\bigr\} \end{aligned}
\end{equation*}
\notag
$$
– $n$-мерная пирамида, прилежащая к вершине $(b_1,b_2,\dots,b_n)\in\mathbb B^n$. Пусть $\operatorname{supp}(f)=\{(b_1,b_2,\dots,b_n)\in\mathbb B^n\colon f(b_1,b_2,\dots,b_n)=1\}$ – носитель булевой функции $f(x_1,x_2,\dots,x_n)$, т.е. множество всех булевых векторов, на которых булева функция $f(x_1,x_2,\dots,x_n)$ принимает значение $1$. Определение 2. Функцию вида $f\colon\mathbb K^n\to\mathbb R$ назовем выпуклой функцией на $\mathbb K^n$, если для любых $x,y\in\mathbb K^n$ и любого $\alpha\in[0,1]$ выполняется Определение 3. Непрерывную функцию вида $f_C\colon\mathbb K^n\to\mathbb R$ назовем выпуклым продолжением булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$, если она на $\mathbb K^n$ выпуклая и Определение 4. Функцию вида $f_{DM}\colon\mathbb K^n\to\mathbb R$ назовем суммарно-максимально выпуклым продолжением булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$, если справедливы следующие утверждения: 3. Конструирование выпуклых продолжений булевых функцийВ этом пункте в явном виде построим суммарно-максимально выпуклое продолжение для конкретной булевой функции
$$
\begin{equation*}
f_{(b_1,b_2,\dots,b_n)}(x_1,x_2,\dots,x_n) =x_1^{b_1}\wedge x_2^{b_2}\wedge\dotsb\wedge x_n^{b_n},
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
x_k^{b_k}=\begin{cases} \overline{x_k}, &\text{если}\ b_k=0, \\ x_k, &\text{если}\ b_k=1, \end{cases}\qquad \forall\,k\in\{1,2,\dots,n\},
\end{equation*}
\notag
$$
и докажем единственность этого продолжения. Теорема 1. Пусть задана булева функция вида Тогда существует единственная функция $f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)$, являющаяся суммарно-максимально выпуклым продолжением этой функции $f_{(b_1, b_2,\dots,b_n)}(x_1,x_2, \dots,x_n)$ на $\mathbb K^n$. Доказательство. Существование. Пусть $g_C(x_1,x_2,\dots,x_n)$ – произвольное выпуклое продолжение булевой функции $f_{(b_1,b_2,\dots,b_n)}(x_1,x_2,\dots,x_n)$. Идея построения суммарно-максимально выпуклого продолжения будет заключаться в том, что во-первых, исходя из выпуклости функции $g_C(x_1,x_2,\dots,x_n)$ оцениваем ее значение сверху с помощью неравенства Йенсена [15], а во-вторых, благодаря оценке сверху строим $f_{DM}(x_1,x_2,\dots,x_n)$ – суммарно-максимально выпуклое продолжение булевой функции $f_{(b_1,b_2,\dots,b_n)}(x_1,x_2,\dots,x_n)$. Пусть $(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb K^n\setminus\mathbb P^n_{(b_1,b_2,\dots,b_n)}$. В этом случае покажем, что
$$
\begin{equation}
g_C(x_1^*,x_2^*,\dots,x_n^*)\leqslant 0\qquad \forall\,(x_1^*,x_2^*,\dots,x_n^*) \in\mathbb K^n\setminus\mathbb P^n_{(b_1,b_2,\dots,b_n)}.
\end{equation}
\tag{3.1}
$$
В силу выпуклости множества $\mathbb K^n\setminus\mathbb P^n_{(b_1,b_2,\dots,b_n)}$ условие
$$
\begin{equation*}
(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb K^n\setminus\mathbb P^n_{(b_1,b_2,\dots,b_n)}
\end{equation*}
\notag
$$
означает, что
$$
\begin{equation*}
(x_1^*,x_2^*,\dots,x_n^*) =\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\}} \lambda_{(a_1,a_2,\dots,a_n)}^{*}\cdot(a_1,a_2,\dots,a_n),
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\lambda_{(a_1,a_2,\dots,a_n)}^*\geqslant 0\qquad \text{и}\qquad \sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\}} \lambda_{(a_1,a_2,\dots,a_n)}^*=1.
\end{equation*}
\notag
$$
Теперь в силу неравенства Йенсена [15]
$$
\begin{equation*}
\begin{aligned} \, &g_C(x_1^*,x_2^*,\dots,x_n^*) =g_C\biggl(\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot(a_1,a_2,\dots,a_n)\biggr) \\ &\qquad\leqslant\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot g_C(a_1,a_2,\dots,a_n) \\ &\qquad=\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot f_{(b_1,b_2,\dots,b_n)}(a_1,a_2,\dots,a_n) \\ &\qquad=\sum_{(a_1,a_2,\dots,a_n)\in\mathbb{B}^n\setminus\{(b_1,b_2,\dots,b_n)\}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot 0 =\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\}} 0=0. \end{aligned}
\end{equation*}
\notag
$$
Пусть $(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb P^n_{(b_1,b_2,\dots,b_n)}$. В этом случае покажем, что
$$
\begin{equation}
g_C(x_1^*,x_2^*,\dots,x_n^*)\leqslant 1+\sum_{k=1}^n((2b_k-1)x_k^*-b_k)\qquad \forall\,(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb P^n_{(b_1,b_2,\dots,b_n)}.
\end{equation}
\tag{3.2}
$$
В силу выпуклости множества $\mathbb P^n_{(b_1,b_2,\dots,b_n)}$ условие $(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb P^n_{(b_1,b_2,\dots,b_n)}$ означает, что
$$
\begin{equation}
(x_1^*,x_2^*,\dots,x_n^*) =\sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon\\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))\leqslant 1}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot(a_1,a_2,\dots,a_n),
\end{equation}
\tag{3.3}
$$
где
$$
\begin{equation*}
\lambda_{(a_1,a_2,\dots,a_n)}^*\geqslant 0\qquad \text{и}\qquad \sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon\\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))\leqslant 1}} \lambda_{(a_1,a_2,\dots,a_n)}^*=1.
\end{equation*}
\notag
$$
Приравняв покоординатно, заметим, что
$$
\begin{equation*}
\lambda_{(b_1,b_2,\dots,b_n)}^*=1+\sum_{k=1}^n((2b_k-1)x_k^*-b_k).
\end{equation*}
\notag
$$
Теперь в силу неравенства Йенсена [15]
$$
\begin{equation*}
\begin{aligned} \, &g_C(x_1^*,x_2^*,\dots,x_n^*) =g_C\biggl(\sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon \\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))\leqslant 1}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot(a_1,a_2,\dots,a_n)\biggr) \\ &\qquad\leqslant\sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon \\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))\leqslant 1}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot g_C(a_1,a_2,\dots,a_n) \\ &\qquad=\sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon \\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))=0}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot g_C(a_1,a_2,\dots,a_n) \\ &\qquad\qquad{}+\sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon \\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))=1}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot g_C(a_1,a_2,\dots,a_n) \\ &\qquad=\lambda_{(b_1,b_2,\dots,b_n)}^*\cdot g_C(b_1,b_2,\dots,b_n) +\sum_{\substack{(a_1,a_2,\dots,a_n)\in\mathbb B^n\colon \\ \rho((b_1,b_2,\dots,b_n),(a_1,a_2,\dots,a_n))=1}} \lambda_{(a_1,a_2,\dots,a_n)}^*\cdot 0 \\ &\qquad=\lambda_{(b_1,b_2,\dots,b_n)}^*\cdot 1+0 =\lambda_{(b_1,b_2,\dots,b_n)}^*=1+\sum_{k=1}^n((2b_k-1)x_k^*-b_k). \end{aligned}
\end{equation*}
\notag
$$
Объединив (3.1) и (3.2), получим
$$
\begin{equation}
g_C(x_1,x_2,\dots,x_n)\leqslant\!\begin{cases} 0, &\text{если}\ 1+\displaystyle{\sum_{k=1}^n((2b_k-1)x_k-b_k)\leqslant 0}, \\ 1\,{+}\displaystyle{\sum_{k=1}^n((2b_k\,{-}\,1)x_k\,{-}\,b_k)}, &\text{если}\ 1\,{+}\sum_{k=1}^n((2b_k\,{-}\,1)x_k\,{-}\,b_k)\geqslant 0. \end{cases}
\end{equation}
\tag{3.4}
$$
Заметим, что правая часть последнего неравенства задается следующей кусочно-линейной функцией:
$$
\begin{equation*}
\frac{1}{2}\cdot\biggl(1+\sum_{k=1}^n((2b_k-1)x_k-b_k) +\biggl|1+\sum_{k=1}^n((2b_k-1)x_k-b_k)\biggr|\biggr).
\end{equation*}
\notag
$$
Теперь докажем, что конструированная оценка является наиболее точной, т.е.
$$
\begin{equation}
\begin{aligned} \, &f^{(b_1,b_2,\dots,b_n)}_{C}(x_1,x_2,\dots,x_n) \nonumber \\ &\qquad=\frac{1}{2} \cdot\biggl(1+\sum_{k=1}^n((2b_k-1)x_k-b_k) +\biggl|1+\sum_{k=1}^n((2b_k-1)x_k-b_k)\biggr|\biggr). \end{aligned}
\end{equation}
\tag{3.5}
$$
Для этого осталось проверить справедливость следующих свойств:
i) имеет место равенство
$$
\begin{equation*}
f^{(b_1,b_2,\dots,b_n)}_C(a_1,a_2,\dots,a_n) =f_{(b_1,b_2,\dots,b_n)}(a_1,a_2,\dots,a_n)\qquad \forall\,(a_1,a_2,\dots,a_n)\in\mathbb B^n;
\end{equation*}
\notag
$$
ii) функция $f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)$ на множестве $\mathbb K^n$ непрерывна и выпукла; iii) имеет место равенство
$$
\begin{equation*}
\begin{aligned} \, &\max_{g_C}\biggl\{\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n\biggr\} \\ &\qquad=\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n. \end{aligned}
\end{equation*}
\notag
$$
i) Действительно,
$$
\begin{equation*}
\begin{aligned} \, &f^{(b_1,b_2,\dots,b_n)}_C(a_1,a_2,\dots,a_n) \\ &\qquad=\begin{cases} 0, &\text{если}\ (a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(b_1,b_2,\dots,b_n)\} \\ 1, &\text{если}\ (a_1,a_2,\dots,a_n)=(b_1,b_2,\dots,b_n) \end{cases}=f_{(b_1,b_2,\dots,b_n)}(a_1,a_2,\dots,a_n). \end{aligned}
\end{equation*}
\notag
$$
ii) Непрерывность очевидна, поэтому проверим только выпуклость. Видно, что $f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)\equiv F(L(x_1,x_2,\dots,x_n))$, где
$$
\begin{equation*}
F(y)=\frac{1}{2}\cdot(y+|y|),\qquad L(x_1,x_2,\dots,x_n)=1+\sum_{k=1}^n((2b_k-1)x_k-b_k).
\end{equation*}
\notag
$$
Теперь легко видеть, что из выпуклости функции $F(y)$ и линейности функции $L(x_1,x_2,\dots,x_n)$ следует выпуклость суперпозиции $F(L(x_1,x_2,\dots,x_n))$.
iii) Действительно, поскольку, с одной стороны, из i) и ii) следует, что функция $f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)$ является одним из выпуклых продолжений функции $f_{(b_1,b_2,\dots,b_n)}(x_1,x_2,\dots,x_n)$ и, следовательно,
$$
\begin{equation*}
\begin{aligned} \, &\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n \\ &\qquad\leqslant\max_{g_C} \biggl\{\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n\biggr\}, \end{aligned}
\end{equation*}
\notag
$$
с другой стороны, из (3.4) следует, что
$$
\begin{equation*}
\begin{aligned} \, &\max_{g_C}\biggl\{\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n\biggr\} \\ &\qquad\leqslant\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n. \end{aligned}
\end{equation*}
\notag
$$
Из этого рассуждения получим
$$
\begin{equation}
\begin{aligned} \, &\max_{g_C}\biggl\{\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n\biggr\} \nonumber \\ &\qquad=\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n. \end{aligned}
\end{equation}
\tag{3.6}
$$
Единственность. Докажем от противного: пусть существует другая функция $r(x_1,x_2,\dots,x_n)$, т.е. такая, что
$$
\begin{equation*}
\exists\,(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb K^n\colon r(x_1^*,x_2^*,\dots,x_n^*) -f^{(b_1,b_2,\dots,b_n)}_C(x_1^*,x_2^*,\dots,x_n^*)\ne 0,
\end{equation*}
\notag
$$
которая является суммарно-максимально выпуклым продолжением $f_{(b_1, b_2,\dots ,b_n)}(x_1, x_2,\dots,x_n)$ на $\mathbb K^n$. Тогда, с одной стороны, в силу (3.6)
$$
\begin{equation}
\underset{\mathbb K^n}{\int\!\!\int\dotsi\int}(r(x_1,x_2,\dots,x_n) -f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n))\, dx_1\,dx_2\,\dots\,dx_n=0,
\end{equation}
\tag{3.7}
$$
с другой стороны, в силу (3.4)
$$
\begin{equation}
r(x_1,x_2,\dots,x_n)-f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)\leqslant 0\qquad \forall(x_1,x_2,\dots,x_n)\in\mathbb K^n.
\end{equation}
\tag{3.8}
$$
Теперь во-первых, из (3.8) следует, что
$$
\begin{equation*}
d=r(x_1^*,x_2^*,\dots,x_n^*)-f^{(b_1,b_2,\dots,b_n)}_C(x_1^*,x_2^*,\dots,x_n^*)<0,
\end{equation*}
\notag
$$
во-вторых, в силу непрерывности $r(x_1,x_2,\dots,x_n)-f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)$ существует $\delta$-окрестность
$$
\begin{equation*}
O_\delta=\bigl\{(x_1,x_2,\dots,x_n)\in\mathbb K^n\colon \|(x_1,x_2,\dots,x_n) -(x_1^*,x_2^*,\dots,x_n^*)\|<\delta,\,\delta>0\bigr\}
\end{equation*}
\notag
$$
такая, что
$$
\begin{equation}
r(x_1,x_2,\dots,x_n)-f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n) <\frac{d}{2}\qquad \forall\,(x_1,x_2,\dots,x_n)\in O_\delta
\end{equation}
\tag{3.9}
$$
и, следовательно,
$$
\begin{equation*}
\begin{aligned} \, &\underset{\mathbb K^n}{\int\!\!\int\dotsi\int}(r(x_1,x_2,\dots,x_n) -f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n))\, dx_1\,dx_2\,\dots\,dx_n \\ &\qquad=\underset{\mathbb K^n\setminus O_\delta}{\int\!\!\int\dotsi\int} (r(x_1,x_2,\dots,x_n)-f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)) \, dx_1\,dx_2\,\dots\,dx_n \\ &\qquad\qquad{}+\underset{O_\delta}{\int\!\!\int\dotsi\int} (r(x_1,x_2,\dots,x_n)-f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n)) \, dx_1\,dx_2\,\dots\,dx_n \\ &\qquad\leqslant\underset{\mathbb K^n\setminus O_\delta}{\int\!\!\int\dotsi\int}0 \, dx_1\,dx_2\,\dots\,dx_n +\underset{O_\delta}{\int\!\!\int\dotsi\int}\frac{d}{2}\, dx_1\,dx_2\,\dots\,dx_n \\ &\qquad=0+\frac{d}{2}\cdot\underset{O_\delta}{\int\!\!\int\dotsi\int}dx_1\,dx_2\,\dots\,dx_n \leqslant\frac{d}{2}\cdot\frac{1}{2^n}\cdot\frac{\pi^n}{\Gamma(n/2+1)}\cdot\delta^n<0. \end{aligned}
\end{equation*}
\notag
$$
Получили противоречие. Теорема доказана. На этом этапе уместно конструировать выпуклое продолжение произвольной булевой функции $f(x_1,x_2,\dots,x_n)$. Для этого, во-первых, сначала на основе теоремы 2 в [11] и формы СДНФ заметим, что для любой булевой функции $f(x_1,x_2,\dots,x_n)$ выполняется следующее вспомогательное тождество:
$$
\begin{equation}
f(x_1,x_2,\dots,x_n)\equiv\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} f(b_1,b_2,\dots,b_n)\cdot f_{(b_1,b_2,\dots,b_n)}(x_1,x_2,\dots,x_n).
\end{equation}
\tag{3.10}
$$
Действительно, так как для всех $(a_1,a_2,\dots,a_n)\in\mathbb B^n$ справедливо
$$
\begin{equation*}
\begin{aligned} \, &f(a_1,a_2,\dots,a_n) =\sum_{(b_1,b_2,\dots,b_n)\in\mathbb{B}^n}f(b_1,b_2,\dots,b_n) \cdot f_{(b_1,b_2,\dots,b_n)}(a_1,a_2,\dots,a_n) \\ &\qquad=\sum_{(b_1,b_2,\dots,b_n)=(a_1,a_2,\dots,a_n)}f(b_1,b_2,\dots,b_n) \cdot f_{(b_1,b_2,\dots,b_n)}(a_1,a_2,\dots,a_n) \\ &\qquad\qquad{}+\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n\setminus(a_1,a_2,\dots,a_n)} f(b_1,b_2,\dots,b_n)\cdot f_{(b_1,b_2,\dots,b_n)}(a_1,a_2,\dots,a_n) \\ &\qquad=f(a_1,a_2,\dots,a_n)\cdot f_{(a_1,a_2,\dots,a_n)}(a_1,a_2,\dots,a_n) \\ &\qquad\qquad+\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n\setminus(a_1,a_2,\dots,a_n)} f(b_1,b_2,\dots,b_n)\cdot 0 \\ &\qquad=f(a_1,a_2,\dots,a_n)\cdot 1+0=f(a_1,a_2,\dots,a_n). \end{aligned}
\end{equation*}
\notag
$$
Во-вторых, заменив булеву функцию $f_{(b_1,b_2,\dots,b_n)}(x_1,x_2,\dots,x_n)$ на $f^{(b_1,b_2,\dots,b_n)}_C(x_1, x_2,\dots,x_n)$, конструируем вещественную функцию вида
$$
\begin{equation}
f_C(x_1,x_2,\dots,x_n)=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} f(b_1,b_2,\dots,b_n)\cdot f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n).
\end{equation}
\tag{3.11}
$$
Далее сформулируем и докажем следствие теоремы 1, утверждающее, что для любой булевой функции $f(x_1,x_2,\dots,x_n)$ соответствующая ей вещественная функция $f_C(x_1,x_2,\dots,x_n)$ вида (3.11) является ее выпуклым продолжением на $\mathbb K^n$. Следствие 1. Для любой булевой функции $f(x_1,x_2,\dots,x_n)$ соответствующая ей вещественная функция $f_C(x_1,x_2,\dots,x_n)$ вида (3.11) является ее выпуклым продолжением на $\mathbb K^n$. Доказательство. Сначала заметим, что функция $f_C(x_1,x_2,\dots,x_n)$ выпукла по построению как сумма некоторых выпуклых (непрерывных) функций на множестве $\mathbb K^n$. Пусть $x,y\in\mathbb K^n$, $\alpha\in[0,1]$. Тогда в силу теоремы 1 и $f(b_1,b_2,\dots,b_n)\in\{0,1\}$ имеем
$$
\begin{equation*}
\begin{aligned} \, &f_C(\alpha\cdot x+(1-\alpha)\cdot y) \\ &\qquad=f_C\bigl(\alpha\cdot x_1+(1-\alpha)\cdot y_1,\,\alpha\cdot x_2 +(1-\alpha)\cdot y_2,\,\dots,\,\alpha\cdot x_n+(1-\alpha)\cdot y_n\bigr) \\ &\qquad=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} f(b_1,b_2,\dots,b_n) \cdot f^{(b_1,b_2,\dots,b_n)}_C\bigl(\alpha\cdot x_1+(1-\alpha)\cdot y_1, \\ &\qquad\qquad{}\alpha\cdot x_2+(1-\alpha)\cdot y_2,\,\dots,\,\alpha\cdot x_n+(1-\alpha)\cdot y_n\bigr) \\ &\qquad\leqslant\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} f(b_1,b_2,\dots,b_n)\cdot\bigl(\alpha\cdot f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n) \\ &\qquad\qquad{}+(1-\alpha)\cdot f^{(b_1,b_2,\dots,b_n)}_{C}(y_1,y_2,\dots,y_n)\bigr) \\ &\qquad=\alpha\cdot\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} f(b_1,b_2,\dots,b_n)\cdot f^{(b_1,b_2,\dots,b_n)}_C(x_1,x_2,\dots,x_n) \\ &\qquad\qquad{}+(1-\alpha)\cdot\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} f(b_1,b_2,\dots,b_n)\cdot f^{(b_1,b_2,\dots,b_n)}_C(y_1,y_2,\dots,y_n) \\ &\qquad=\alpha\cdot f_C(x)+(1-\alpha)\cdot f_C(y). \end{aligned}
\end{equation*}
\notag
$$
Остается показать, что
$$
\begin{equation*}
\forall\,(a_1,a_2,\dots,a_n)\in\mathbb B^n\qquad f_C(a_1,a_2,\dots,a_n)=f(a_1,a_2,\dots,a_n).
\end{equation*}
\notag
$$
В силу теоремы 1 и тождества (3.10) получим
$$
\begin{equation*}
\begin{aligned} \, &f_C(a_1,a_2,\dots,a_n)=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb{B}^n} f(b_1,b_2,\dots,b_n)\cdot f^{(b_1,b_2,\dots,b_n)}_C(a_1,a_2,\dots,a_n) \\ &\qquad=\sum_{(b_1,b_2,\dots,b_n)=(a_1,a_2,\dots,a_n)} f(b_1,b_2,\dots,b_n)\cdot f^{(b_1,b_2,\dots,b_n)}_C(a_1,a_2,\dots,a_n) \\ &\qquad\qquad{}+\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n\setminus(a_1,a_2,\dots,a_n)} f(b_1,b_2,\dots,b_n)\cdot f^{(b_1,b_2,\dots,b_n)}_C(a_1,a_2,\dots,a_n) \\ &\qquad=f(a_1,a_2,\dots,a_n)\cdot f^{(a_1,a_2,\dots,a_n)}_C(a_1,a_2,\dots,a_n) \\ &\qquad\qquad{}+\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n\setminus(a_1,a_2,\dots,a_n)} f(b_1,b_2,\dots,b_n)\cdot 0 \\ &\qquad=f(a_1,a_2,\dots,a_n)\cdot 1+0=f(a_1,a_2,\dots,a_n). \end{aligned}
\end{equation*}
\notag
$$
Замечание 1. Конструированное выпуклое продолжение вида (3.11) булевой функции $f(x_1,x_2,\dots,x_n)$, вообще говоря, не является суммарно-максимально выпуклым. В качестве иллюстрирующего примера можно привести булеву функцию вида $f(x_1,x_2)=x_1\wedge x_2\vee\overline{x_1}\wedge x_2$. Теорема 2. Для любой булевой функции $f(x_1,x_2,\dots,x_n)$ существует бесконечно много функций, каждая из которых является ее выпуклым продолжением на $\mathbb K^n$. Доказательство. Существование. Согласно следствию 1 для любой булевой функции $f(x_1,x_2,\dots,x_n)$ функция вида является ее выпуклым продолжением на $\mathbb K^n$.
Бесконечность. Докажем от противного: пусть имеется конечное множество
$$
\begin{equation*}
S_C=\bigl\{g_1(x_1,x_2,\dots,x_n),g_2(x_1,x_2,\dots,x_n),\dots,g_N(x_1,x_2,\dots,x_n)\bigr\}
\end{equation*}
\notag
$$
выпуклых продолжений булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$. Тогда
$$
\begin{equation}
\begin{aligned} \, &\exists\,N_0\in\{1,2,\dots,N\}\colon \qquad \underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_{N_0}(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n \nonumber \\ &\qquad\leqslant\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_k(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n\qquad \forall\,k\in\{1,2,\dots,N\}, \end{aligned}
\end{equation}
\tag{3.12}
$$
так как существует минимум среди конечного числа чисел, являющихся интегральными значениями непрерывно выпуклых функций. Теперь рассмотрим специальную функцию вида
$$
\begin{equation}
\begin{aligned} \, &g_{\mathrm{new}}(x_1,x_2,\dots,x_n) \nonumber \\ &\qquad=g_{N_0}(x_1,x_2,\dots,x_n) -A\cdot\min(x_1,1-x_1,x_2,1-x_2,\dots,x_n,1-x_n), \end{aligned}
\end{equation}
\tag{3.13}
$$
где $A$ – любое положительное число. Докажем, что функция $g_{\mathrm{new}}(x_1,x_2,\dots,x_n)$ также является выпуклым продолжением булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$. Для этого достаточно показать справедливость следующих свойств:
i) Действительно,
$$
\begin{equation*}
\begin{aligned} \, g_{\mathrm{new}}(a_1,a_2,\dots,a_n) &=g_{N_0}(a_1,a_2,\dots,a_n)-A\cdot\min(a_1,1-a_1,a_2,1-a_2,\dots,a_n,1-a_n) \\ &=g_{N_0}(a_1,a_2,\dots,a_n)-A\cdot 0 =g_{N_0}(a_1,a_2,\dots,a_n) \\ &=f(a_1,a_2,\dots,a_n)\qquad \forall\,(a_1,a_2,\dots,a_n)\in\mathbb B^n, \end{aligned}
\end{equation*}
\notag
$$
так как, во-первых, $g_{N_0}(x_1,x_2,\dots,x_n)$ – одно из выпуклых продолжений булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$, во-вторых, $a_k\in\{0,1\}$ для всех $k\in\{1,2,\dots,n\}$ и, следовательно,
$$
\begin{equation*}
\min(a_1,1-a_1,a_2,1-a_2,\dots,a_n,1-a_n)=0\qquad \forall(a_1,a_2,\dots,a_n)\in\mathbb B^n.
\end{equation*}
\notag
$$
ii) Непрерывность очевидна как разность непрерывных функций, поэтому проверяем только выпуклость. Пусть $x^*,x^{**}\in\mathbb K^n$, $\alpha\in[0,1]$ и
$$
\begin{equation*}
\alpha\cdot x^*+(1-\alpha)\cdot x^{**} =\bigl(\alpha\cdot x_1^*+(1-\alpha)\cdot x_1^{**}, \alpha\cdot x_2^*+(1-\alpha)\cdot x_2^{**},\dots, \alpha\cdot x_n^*+(1-\alpha)\cdot x_n^{**}\bigr).
\end{equation*}
\notag
$$
Тогда для всех $k\in\{1,2,\dots,n\}$ справедливы неравенства
$$
\begin{equation*}
\begin{aligned} \, \alpha\cdot x_k^*+(1-\alpha)\cdot x_k^{**} &\geqslant\alpha\cdot\min(x_1^*,1-x_1^*,\dots,x_n^*,1-x_n^*) \\ &\qquad{}+(1-\alpha)\cdot\min(x_1^{**},1-x_1^{**},\dots,x_n^{**},1-x_n^{**}), \\ \alpha\cdot(1-x_k^*)+(1-\alpha)\cdot(1-x_k^{**}) &\geqslant\alpha\cdot\min(x_1^*,1-x_1^*,\dots,x_n^*,1-x_n^*) \\ &\qquad{}+(1-\alpha)\cdot\min(x_1^{**},1-x_1^{**},\dots,x_n^{**},1-x_n^{**}). \end{aligned}
\end{equation*}
\notag
$$
Следовательно,
$$
\begin{equation*}
\begin{aligned} \, &\min\bigl(\alpha x_1^*+(1-\alpha)x_1^{**},\alpha(1-x_1^*) +(1-\alpha)(1-x_1^{**}), \dots, \alpha x_n^*+(1-\alpha)x_n^{**}, \\ &\qquad\qquad\alpha(1-x_n^*)+(1-\alpha)(1-x_n^{**})\bigr) \\ &\qquad\geqslant\alpha\cdot\min(x_1^*, 1-x_1^*,\dots, x_n^*,1-x_n^*) +(1-\alpha)\cdot\min(x_1^{**},1-x_1^{**},\dots,x_n^{**},1-x_n^{**}). \end{aligned}
\end{equation*}
\notag
$$
Отсюда в силу $A>0$ и выпуклости $g_{N_0}(x_1,x_2,\dots,x_n)$ справедливо
$$
\begin{equation*}
\begin{aligned} \, &g_{\mathrm{new}}(\alpha x^*+(1-\alpha)x^{**}) \\ &\qquad=g_{\mathrm{new}}\bigl(\alpha x_1^*+(1-\alpha)x_1^{**}, \alpha x_2^*+(1-\alpha)x_2^{**},\dots,\alpha x_n^*+(1-\alpha)x_n^{**}\bigr) \\ &\qquad=g_{N_0}\bigl(\alpha x_1^*+(1-\alpha)x_1^{**},\alpha x_2^*+(1-\alpha)x_2^{**}, \dots,\alpha x_n^*+(1-\alpha)x_n^{**}\bigr) \\ &\qquad\qquad{}-A\cdot\min\bigl(\alpha x_1^*+(1-\alpha)x_1^{**}, 1-\alpha x_1^*-(1-\alpha)x_1^{**},\dots, \\ &\qquad\qquad\qquad\alpha x_n^*+(1-\alpha)x_n^{**}, 1-\alpha x_n^*-(1-\alpha)x_n^{**}\bigr) \\ &\qquad=g_{N_0}\bigl(\alpha x_1^*+(1-\alpha)x_1^{**}, \alpha x_2^*+(1-\alpha)x_2^{**},\dots,\alpha x_n^*+(1-\alpha)x_n^{**}\bigr) \\ &\qquad\qquad{}-A\cdot\min\bigl(\alpha x_1^*+(1-\alpha)x_1^{**}, \alpha(1-x_1^*)+(1-\alpha)(1-x_1^{**}), \dots, \\ &\qquad\qquad\qquad \alpha x_n^*+(1-\alpha)x_n^{**}, \alpha(1-x_n^*) +(1-\alpha)(1-x_n^{**})\bigr) \\ &\qquad \leqslant \alpha\cdot g_{N_0}(x_1^*,x_2^*,\dots,x_n^*) +(1-\alpha)\cdot g_{N_0}(x_1^{**},x_2^{**},\dots,x_n^{**}) \\ &\qquad\qquad{}+\alpha\cdot(-A)\cdot\min(x_1^*,1-x_1^*,\dots, x_n^*, 1-x_n^*) \\ &\qquad\qquad{}+(1-\alpha)\cdot(-A)\cdot\min(x_1^{**},1-x_1^{**},\dots,x_n^{**},1-x_n^{**}) \\ &\qquad=\alpha\cdot(g_{N_0}(x_1^*,x_2^*,\dots,x_n^*) -A\cdot\min(x_1^*,1-x_1^*,\dots,x_n^*,1-x_n^*)) \\ &\qquad\qquad{}+(1-\alpha)\cdot\bigl(g_{N_0}(x_1^{**},x_2^{**},\dots,x_n^{**}) -A\cdot\min(x_1^{**},1-x_1^{**},\dots,x_n^{**},1-x_n^{**})\bigr) \\ &\qquad=\alpha\cdot g_{\mathrm{new}}(x_1^*,x_2^*,\dots,x_n^*) +(1-\alpha)\cdot g_{\mathrm{new}}(x_1^{**},x_2^{**},\dots,x_n^{**}) \\ &\qquad =\alpha\cdot g_{\mathrm{new}}(x^*)+(1-\alpha)\cdot g_{\mathrm{new}}(x^{**}). \end{aligned}
\end{equation*}
\notag
$$
Теперь докажем, что
$$
\begin{equation}
\begin{aligned} \, &g_{\mathrm{new}}(x_1,x_2,\dots,x_n) <g_{N_0}(x_1,x_2,\dots,x_n)\qquad \forall\,(x_1,x_2,\dots,x_n)\in\mathrm{int}(\mathbb K^n), \nonumber \\ &\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_{\mathrm{new}}(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n \nonumber \\ &\qquad=\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_{N_0}(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n-\frac{A}{2n+2}\,. \end{aligned}
\end{equation}
\tag{3.14}
$$
Действительно, если $(x_1,x_2,\dots,x_n)\in\mathrm{int}(\mathbb K^n)$, то так как $0<x_k<1$ для всех $k\in\{1,2,\dots,n\}$. Отсюда в силу (3.13) справедливо
$$
\begin{equation*}
g_{\mathrm{new}}(x_1,x_2,\dots,x_n) <g_{N_0}(x_1,x_2,\dots,x_n)\qquad \forall\,(x_1,x_2,\dots,x_n)\in\mathrm{int}(\mathbb K^n).
\end{equation*}
\notag
$$
Учитывая симметрию, нетрудно заметить, что
$$
\begin{equation*}
\begin{aligned} \, 1 &=\underset{\mathbb K^{n+1}}{\int\!\!\int\dotsi\int} 1\cdot dx_1\,dx_2\,\dots\,dx_n\,dx_{n+1} \\ &=(2n+2)\cdot\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} \min(x_1,1-x_1,x_2,1-x_2,\dots,x_n,1-x_n)\,dx_1\,dx_2\,\dots\,dx_n. \end{aligned}
\end{equation*}
\notag
$$
Следовательно, в силу (3.13) выполняется равенство (3.14). Отсюда в силу (3.12) и (3.14) предъявленное выпуклое продолжение $g_{\mathrm{new}}(x_1,x_2,\dots,x_n)$ булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$ не принадлежит множеству $S_C$. Получили противоречие. Теорема доказана. 4. Суммарно-максимально выпуклое продолжение произвольной булевой функцииВ этом пункте, во-первых, обоснуем справедливость одной вспомогательной леммы, а во-вторых, для булевой функции $f(x_1,x_2,\dots,x_n)$ сопоставим соответствующую ей вещественную функцию $f_{DM}(x_1,x_2,\dots,x_n)$ и докажем, что $f_{DM}(x_1,x_2,\dots,x_n)$ является ее единственным суммарно-максимально выпуклым продолжением на $\mathbb K^n$. Лемма 1. Для любого $(b_1,b_2,\dots,b_n)\in\mathbb B^n$ множество $\boldsymbol\Lambda(b_1,b_2,\dots,b_n)$ состоит из одного элемента, в котором на месте $\lambda_{(b_1,b_2,\dots,b_n)}$ стоит единица, а на остальных местах стоят нули. Доказательство. Рассмотрим три случая.
Случай 1. Пусть Тогда согласно приведенному выше обозначению
$$
\begin{equation*}
\begin{aligned} \, &\boldsymbol\Lambda(b_1,b_2,\dots,b_n) =\boldsymbol\Lambda(0,0,\dots,0) =\biggl\{(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots, \lambda_{(1,1,\dots,1)})\in\mathbb K^{2^n}\colon \\ &\qquad\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n} \lambda_{(a_1,a_2,\dots,a_n)}\cdot(a_1,a_2,\dots,a_n) =(0,0,\dots,0),\, \\ &\qquad \sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n}\lambda_{(a_1,a_2,\dots,a_n)}=1\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
В силу
$$
\begin{equation*}
\lambda_{(a_1,a_2,\dots,a_n)}\in[0,1]\quad \forall\,(a_1,a_2,\dots,a_n)\in\mathbb B^n\qquad \text{и}\qquad \sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n}\lambda_{(a_1,a_2,\dots,a_n)}=1,
\end{equation*}
\notag
$$
приравняв покоординатно, легко заметить, что
$$
\begin{equation*}
\lambda_{(a_1,a_2,\dots,a_n)}=\begin{cases} 1, &\text{если}\ (a_1,a_2,\dots,a_n)=(0,0,\dots,0), \\ 0, &\text{если}\ (a_1,a_2,\dots,a_n)\in\mathbb B^n\setminus\{(0,0,\dots,0)\}, \end{cases}
\end{equation*}
\notag
$$
так как если предположить, что существует $(a_1^*,a_2^*,\dots,a_n^*)\in\mathbb B^n\setminus\{(0,0,\dots,0)\}$ такой, что $\lambda_{(a_1^*,a_2^*,\dots,a_n^*)}>0$, то хотя бы одна координата вектора
$$
\begin{equation*}
\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n} \lambda_{(a_1,a_2,\dots,a_n)}\cdot(a_1,a_2,\dots,a_n)
\end{equation*}
\notag
$$
будет положительна и, следовательно, он не будет равен $(0,0,\dots,0)$.
Случай 2. Пусть Тогда
$$
\begin{equation*}
\begin{aligned} \, &\boldsymbol\Lambda(b_1,b_2,\dots,b_n)=\boldsymbol\Lambda(1,1,\dots,1) =\biggl\{(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots, \lambda_{(1,1,\dots,1)})\in\mathbb K^{2^n}\colon \\ &\qquad \sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n} \lambda_{(a_1,a_2,\dots,a_n)}\cdot(a_1,a_2,\dots,a_n)=(1,1,\dots,1), \\ &\qquad\sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n} \lambda_{(a_1,a_2,\dots,a_n)}=1\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
В силу
$$
\begin{equation*}
\lambda_{(a_1,a_2,\dots,a_n)}\in[0,1]\quad \forall\,(a_1,a_2,\dots,a_n)\in\mathbb B^n\qquad \text{и}\qquad \sum_{(a_1,a_2,\dots,a_n)\in\mathbb B^n}\lambda_{(a_1,a_2,\dots,a_n)}=1,
\end{equation*}
\notag
$$
приравняв $k$-е координаты обеих частей, заметим, что $\lambda_{(a_1,a_2,\dots,a_{k-1},0,a_{k+1},\dots,a_n)}=0$ для всех $(a_1,a_2,\dots,a_{k-1},a_{k+1},\dots,a_n)\in\mathbb B^{n-1}$ и, следовательно, в силу произвольности $k\in\{1,2,\dots,n\}$ справедливо
$$
\begin{equation*}
\lambda_{(a_1,a_2,\dots,a_n)}=\begin{cases} 1, &\text{если}\ (a_1,a_2,\dots,a_n)=(1,1,\dots,1), \\ 0, &\text{если}\ (a_1,a_2,\dots,a_n) \in\mathbb B^n\setminus\{(1,1,\dots,1)\}. \end{cases}
\end{equation*}
\notag
$$
Случай 3. Пусть
$$
\begin{equation*}
(b_1,b_2,\dots,b_n)\in\mathbb B^n\setminus\{(0,0,\dots,0),(1,1,\dots,1)\}.
\end{equation*}
\notag
$$
Тогда существуют числа $p,q\in\mathbb N$ и множества $\{i_1,i_2,\dots,i_p\}$, $\{j_1,j_2,\dots,j_q\}$ такие, что Теперь, во-первых, исходя из рассуждения, аналогичного рассуждению в случае 1, получим, что если хотя бы одна из этих $a_{i_1},a_{i_2},\dots,a_{i_p}$ координат вектора $(a_1,a_2, \dots,a_n)$ равна единице, то $\lambda_{(a_1,a_2,\dots,a_n)}=0$, во-вторых, исходя из рассуждения, аналогичного рассуждению в случае 2, получим, что если хотя бы одна из этих $a_{j_1},a_{j_2},\dots,a_{j_q}$ координат вектора $(a_1,a_2,\dots,a_n)$ равна нулю, то $\lambda_{(a_1,a_2,\dots,a_n)}=0$. Отсюда Лемма доказана. Теперь для произвольной булевой функции $f(x_1,x_2,\dots,x_n)$ сопоставим соответствующую ей вещественную функцию вида
$$
\begin{equation}
\begin{aligned} \, \notag &f_{DM}(x_1,x_2,\dots,x_n) \\ &\qquad =\min_{(\lambda_{(0,0,\dots,0)},\dots,\lambda_{(1,1,\dots,1)})\in\boldsymbol\Lambda(x_1,x_2,\dots,x_n)} \biggl[\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n)\biggr]. \end{aligned}
\end{equation}
\tag{4.1}
$$
В силу компактности множества $\boldsymbol\Lambda(x_1^*,x_2^*,\dots,x_n^*)$ для всех $(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb K^n$, непрерывности функции
$$
\begin{equation*}
s(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots,\lambda_{(1,1,\dots,1)}) =\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n)
\end{equation*}
\notag
$$
и теоремы Вейерштрасса функция $f_{DM}(x_1,x_2,\dots,x_n)$, $(x_1,x_2,\dots,x_n)\in\mathbb K^n$, корректно определена. Далее сформулируем и докажем теорему, утверждающую, что для любой булевой функции $f(x_1,x_2,\dots,x_n)$ функция $f_{DM}(x_1,x_2,\dots,x_n)$ является единственным суммарно-максимально выпуклым продолжением на множестве $\mathbb K^n$. Теорема 3. Для произвольной булевой функции $f(x_1,x_2,\dots,x_n)$ ее единственным суммарно-максимально выпуклым продолжением на $\mathbb K^n$ является функция $f_{DM}(x_1,x_2,\dots,x_n)$ вида (4.1). Доказательство. Сначала покажем, что если $g_C(x_1,x_2,\dots,x_n)$ – произвольное выпуклое продолжение булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$, то
$$
\begin{equation}
g_C(x_1,x_2,\dots,x_n)\leqslant f_{DM}(x_1,x_2,\dots,x_n)\qquad \forall\,(x_1,x_2,\dots,x_n)\in\mathbb K^n.
\end{equation}
\tag{4.2}
$$
Пусть $(x_1^*,x_2^*,\dots,x_n^*)\in\mathbb K^n$. Тогда в силу выпуклости множества $\mathbb K^n$
$$
\begin{equation*}
\begin{aligned} \, &\exists\,\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots, \lambda_{(1,1,\dots,1)}\colon \\ &\qquad (\lambda_{(0,0,\dots,0)}, \lambda_{(0,0,\dots,1)},\dots,\lambda_{(1,1,\dots,1)}) \in\boldsymbol\Lambda(x_1^*,x_2^*,\dots,x_n^*), \end{aligned}
\end{equation*}
\notag
$$
т.е. такие, что
$$
\begin{equation*}
\begin{gathered} \, \sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot(b_1,b_2,\dots,b_n)=(x_1^*,x_2^*,\dots,x_n^*), \lambda_{(b_1,b_2,\dots,b_n)}\geqslant 0, \\ \sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n}\lambda_{(b_1,b_2,\dots,b_n)}=1. \end{gathered}
\end{equation*}
\notag
$$
Теперь в силу выпуклости функции $g_C(x_1,x_2,\dots,x_n)$ и неравенства Йенсена [15] получим
$$
\begin{equation*}
\begin{aligned} \, g_C(x_1^*,x_2^*,\dots,x_n^*) &=g_C\biggl(\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot(b_1,b_2,\dots,b_n)\biggr) \\ &\leqslant\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot g_C(b_1,b_2,\dots,b_n) \\ &=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n) \\ &\qquad \forall\,(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots, \lambda_{(1,1,\dots,1)})\in\boldsymbol\Lambda(x_1^*,x_2^*,\dots,x_n^*). \end{aligned}
\end{equation*}
\notag
$$
В частности,
$$
\begin{equation*}
\begin{aligned} \, &g_C(x_1^*,x_2^*,\dots,x_n^*) \leqslant f_{DM}(x_1^*,x_2^*,\dots,x_n^*) \\ &\qquad=\min_{\substack{(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots,\\ \lambda_{(1,1,\dots,1)})\in\boldsymbol\Lambda(x_1^*,x_2^*,\dots,x_n^*)}} \biggl[\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n)\biggr]. \end{aligned}
\end{equation*}
\notag
$$
В силу произвольности $(x_1^*,x_2^*,\dots,x_n^*)$ из последнего неравенства получим справедливость (4.2).
Остается показать, что функция $f_{DM}(x_1,x_2,\dots,x_n)$ также является выпуклым продолжением булевой функции $f(x_1,x_2,\dots,x_n)$. Для этого достаточно показать справедливость следующих свойств:
i) Действительно,
$$
\begin{equation*}
\begin{aligned} \, f_{DM}(a_1,a_2,\dots,a_n) &=\!\!\min_{\substack{(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots,\\ \lambda_{(1,1,\dots,1)})\in\boldsymbol\Lambda(a_1,a_2,\dots,a_n)}} \biggl[\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n}\!\! \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n)\biggr] \\ &=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n) \\ &=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n\setminus\{(a_1,a_2,\dots,a_n)\}}0 \cdot f(b_1,b_2,\dots,b_n) \\ &\qquad+\sum_{(b_1,b_2,\dots,b_n) =(a_1,a_2,\dots,a_n)}1\cdot f(b_1,b_2,\dots,b_n) \\ &=0+f(a_1,a_2,\dots,a_n) =f(a_1,a_2,\dots,a_n), \end{aligned}
\end{equation*}
\notag
$$
так как в силу леммы 1 множество $\boldsymbol\Lambda(a_1,a_2,\dots,a_n)$, $(a_1,a_2,\dots,a_n)\in\mathbb B^n$, состоит из одного элемента, в котором на месте $\lambda_{(a_1,a_2,\dots,a_n)}$ стоит единица, а на остальных местах – нули.
ii) Непрерывность $f_{DM}(x_1,x_2,\dots,x_n)$ очевидна, поэтому проверим только выпуклость. Пусть $x^*,x^{**}\in\mathbb K^n$, $\alpha\in[0,1]$ и
$$
\begin{equation*}
\alpha\cdot x^*+(1-\alpha)\cdot x^{**} =(\alpha\cdot x_1^*+(1-\alpha)\cdot x_1^{**},\alpha\cdot x_2^* +(1-\alpha)\cdot x_2^{**},\dots,\alpha\cdot x_n^*+(1-\alpha)\cdot x_n^{**}).
\end{equation*}
\notag
$$
В силу теоремы Вейерштрасса существуют
$$
\begin{equation*}
\begin{aligned} \, (\lambda_{(0,0,\dots,0)}^*,\lambda_{(0,0,\dots,1)}^*,\dots,\lambda_{(1,1,\dots,1)}^*) &\in\boldsymbol\Lambda(x_1^*,x_2^*,\dots,x_n^*), \\ (\lambda_{(0,0,\dots,0)}^{**},\lambda_{(0,0,\dots,1)}^{**},\dots,\lambda_{(1,1,\dots,1)}^{**}) &\in\boldsymbol\Lambda(x_1^{**},x_2^{**},\dots,x_n^{**}) \end{aligned}
\end{equation*}
\notag
$$
такие, что
$$
\begin{equation*}
\begin{aligned} \, f_{DM}(x_1^*,x_2^*,\dots,x_n^*) &=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}^*\cdot f(b_1,b_2,\dots,b_n), \\ f_{DM}(x_1^{**},x_2^{**},\dots,x_n^{**}) &=\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}^{**}\cdot f(b_1,b_2,\dots,b_n). \end{aligned}
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation*}
\begin{aligned} \, &f_{DM}(\alpha x^*+(1-\alpha)x^{**}) \\ &\qquad=f_{DM}(\alpha x_1^*+(1-\alpha)x_1^{**},\alpha x_2^*+(1-\alpha)x_2^{**}, \dots,\alpha x_n^*+(1-\alpha)x_n^{**}) \\ &\qquad=\min_{\substack{(\lambda_{(0,0,\dots,0)},\lambda_{(0,0,\dots,1)},\dots, \\ \lambda_{(1,1,\dots,1)}) \in\boldsymbol\Lambda(\alpha x^*+(1-\alpha)x^{**})}} \biggl[\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}\cdot f(b_1,b_2,\dots,b_n)\biggr] \\ &\qquad\leqslant\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} (\alpha\cdot\lambda_{(b_1,b_2,\dots,b_n)}^* +(1-\alpha)\cdot\lambda_{(b_1,b_2,\dots,b_n)}^{**})\cdot f(b_1,b_2,\dots,b_n) \\ &\qquad=\alpha\cdot\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}^*\cdot f(b_1,b_2,\dots,b_n) \\ &\qquad\qquad{}+(1-\alpha)\cdot\sum_{(b_1,b_2,\dots,b_n)\in\mathbb B^n} \lambda_{(b_1,b_2,\dots,b_n)}^{**}\cdot f(b_1,b_2,\dots,b_n) \\ &\qquad=\alpha\cdot f_{DM}(x_1^*,x_2^*,\dots,x_n^*) +(1-\alpha)\cdot f_{DM}(x_1^{**},x_2^{**},\dots,x_n^{**}) \\ &\qquad=\alpha\cdot f_{DM}(x^*)+(1-\alpha)\cdot f_{DM}(x^{**}), \end{aligned}
\end{equation*}
\notag
$$
так как легко заметить, что
$$
\begin{equation*}
\begin{aligned} \, &\bigl(\alpha\lambda_{(0,0,\dots,0)}^*+(1-\alpha)\lambda_{(0,0,\dots,0)}^{**},\, \alpha\lambda_{(0,0,\dots,1)}^*+(1-\alpha)\lambda_{(0,0,\dots,1)}^{**},\,\dots, \\ &\qquad\qquad \alpha\lambda_{(1,1,\dots,1)}^* +(1-\alpha)\lambda_{(1,1,\dots,1)}^{**}\bigr) \\ &\qquad{} \in \boldsymbol\Lambda\bigl(\alpha x_1^*+(1-\alpha)x_1^{**},\,\alpha x_2^* +(1-\alpha)x_2^{**},\,\dots,\,\alpha x_n^*+(1-\alpha)x_n^{**}\bigr). \end{aligned}
\end{equation*}
\notag
$$
Из произвольности $(x_1^*,x_2^*,\dots,x_n^*)$ и $(x_1^{**},x_2^{**},\dots,x_n^{**})$ следует выпуклость функции $f_{DM}(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$.
iii) В силу пунктов i) и ii), исходя из рассуждения, аналогичного рассуждению доказательства свойства iii) в теореме 1, получим
$$
\begin{equation*}
\begin{aligned} \, &\max_{g_C}\biggl\{\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} g_C(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n\biggr\} \\ &\qquad =\underset{\mathbb K^n}{\int\!\!\int\dotsi\int} f_{DM}(x_1,x_2,\dots,x_n)\,dx_1\,dx_2\,\dots\,dx_n. \end{aligned}
\end{equation*}
\notag
$$
Единственность. Доказательство аналогично доказательству единственности в теореме 1. Теорема доказана. В качестве следствий предъявим явные формы суммарно-максимально выпуклых продолжений булевых функций не более чем от двух переменных и булевой функции
$$
\begin{equation*}
f(x_1,x_2,\dots,x_n)=x_1^{b_1}\vee x_2^{b_2}\vee\dotsb\vee x_n^{b_n},
\end{equation*}
\notag
$$
которые непосредственно вытекают из теоремы 3. Следствие 2. Для любой булевой функции $f(x)$, зависящей от одной переменной, функция вида является ее единственным суммарно-максимально выпуклым продолжением на множество $\mathbb K^1$. Следствие 3. Для любой булевой функции $f(x,y)$, зависящей от двух переменных, функция вида Следствие 4. Для булевой функции функция вида является ее единственным суммарно-максимально выпуклым продолжением на множество $\mathbb K^n$. 5. Применение выпуклого продолжения булевой функцииВ этом пункте приводится одно из возможных (теоретически обоснованных) применений полученных результатов. Рассмотрим систему произвольных булевых уравнений с единственным решением общего вида
$$
\begin{equation}
\begin{cases} p_1(x_1,x_2,\dots,x_n)=q_1(x_1,x_2,\dots,x_n), \\ p_2(x_1,x_2,\dots,x_n) = q_2(x_1,x_2,\dots,x_n), \\ p_3(x_1,x_2,\dots,x_n) = q_3(x_1,x_2,\dots,x_n), \\ \qquad\qquad\dotsb \\ p_m(x_1,x_2,\dots,x_n)=q_m(x_1,x_2,\dots,x_n), \end{cases}
\end{equation}
\tag{5.1}
$$
где $p_i(x_1,x_2,\dots,x_n)$ и $q_i(x_1,x_2,\dots,x_n)$ – произвольные булевы функции для любого $i\in\{1,2,\dots,n\}$. Легко заметить, что система (5.1) эквивалентна системе вида
$$
\begin{equation}
\begin{cases} p_1(x_1,x_2,\dots,x_n)\oplus q_1(x_1,x_2,\dots,x_n)=0, \\ p_2(x_1,x_2,\dots,x_n)\oplus q_2(x_1,x_2,\dots,x_n)=0, \\ p_3(x_1,x_2,\dots,x_n)\oplus q_3(x_1,x_2,\dots,x_n)=0, \\ \qquad\qquad\dotsb \\ p_m(x_1,x_2,\dots,x_n)\oplus q_m(x_1,x_2,\dots,x_n)=0. \end{cases}
\end{equation}
\tag{5.2}
$$
Система (5.2) может быть трансформирована к одному скалярному булеву уравнению вида
$$
\begin{equation}
f(x_1,x_2,\dots,x_n)=1\oplus\bigwedge_{i=1}^m\bigl(p_i(x_1,x_2,\dots,x_n) \oplus q_i(x_1,x_2,\dots,x_n)\oplus 1\bigr)=0.
\end{equation}
\tag{5.3}
$$
Введем обозначения. Пусть $ f_{DM}^*(x_1,x_2,\dots,x_n)$ – суммарно-максимально выпуклое продолжение булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$, а $(b_1^*,b_2^*,\dots,b_n^*)\in\mathbb B^n$ – решение системы (5.1). Тогда справедливо следующее утверждение, устанавливающее связь между системой (5.1) и суммарно-максимально выпуклым продолжением $f_{DM}^*(x_1,x_2,\dots,x_n)$. Утверждение 1. Если $(x_1,x_2,\dots,x_n)\in\mathbb K^n$, то $f_{DM}^*(x_1,x_2,\dots,x_n)=0$ тогда и только тогда, когда $(x_1,x_2,\dots,x_n)=(b_1^*,b_2^*,\dots,b_n^*)$. Доказательство. В одну сторону очевидно, так как во-первых, система (5.1) и уравнение (5.3) эквивалентны, во-вторых, $f_{DM}^*(x_1,x_2,\dots,x_n)$ – одно из выпуклых продолжений булевой функции $f(x_1,x_2,\dots,x_n)$ и, следовательно, если $(x_1,x_2, \dots,x_n)=(b_1^*,b_2^*,\dots,b_n^*)$, то $f_{DM}^*(x_1,x_2,\dots,x_n)=0$.
Проведем доказательство в другую сторону. Пусть $(x_1,x_2,\dots,x_n)\in\mathbb K^n$ и $f_{DM}^*(x_1, x_2,\dots,x_n)=0$. В этом случае мы покажем, что $(x_1,x_2,\dots,x_n)=(b_1^*,b_2^*,\dots,b_n^*)$. Из следствия 4 теоремы 3 вытекает, что суммарно-максимально выпуклое продолжение булевой функции
$$
\begin{equation*}
f(x_1,x_2,\dots,x_n)=\begin{cases} 0, &\text{если}\ (x_1,x_2,\dots,x_n)=(b_1^*,b_2^*,\dots,b_n^*), \\ 1, &\text{если}\ (x_1,x_2,\dots,x_n)\ne(b_1^*,b_2^*,\dots,b_n^*), \end{cases}
\end{equation*}
\notag
$$
на $\mathbb K^n$ имеет следующий вид:
$$
\begin{equation}
f_{DM}^*(x_1,x_2,\dots,x_n) =\max\bigl(b_1^*-(2b_1^*-1)\cdot x_1,\,b_2^*-(2b_2^*-1)\cdot x_2,\,\dots,\,b_n^*-(2b_n^*-1)\cdot x_n\bigr).
\end{equation}
\tag{5.4}
$$
Теперь, благодаря (5.4), из $(x_1,x_2,\dots,x_n)\in\mathbb K^n$ и $f_{DM}^*(x_1,x_2,\dots,x_n)=0$ следует $(x_1,x_2,\dots,x_n)=(b_1^*,b_2^*,\dots,b_n^*)$, так как $0\leqslant b_i^*-(2b_i^*-1)\cdot x_i\leqslant 1$ при всех $i\in\{1,2,\dots,n\}$. Утверждение доказано. Замечание 2. В утверждении 1 важно, что $f_{DM}^*(x_1,x_2,\dots,x_n)$ – суммарно-максимально выпуклое продолжение булевой функции $f(x_1,x_2,\dots,x_n)$ на $\mathbb K^n$, так как если в качестве $f_{DM}^*(x_1,x_2,\dots,x_n)$ взять другое выпуклое продолжение булевой функции $f(x_1,x_2,\dots,x_n)$, то легко привести пример того, что из $(x_1,x_2,\dots,x_n)\,{\in}\,\mathbb K^n$ и $f_{DM}^*(x_1,x_2,\dots,x_n)=0$ не следует $(x_1,x_2,\dots,x_n)=(b_1^*,b_2^*,\dots,b_n^*)$. Автор искренне благодарит рецензента за ряд существенных замечаний, которые помогли улучшить содержание статьи. 
Цитирование в формате AMSBIB
\RBibitem{Bar24} |
|
||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|