Конструирование гладких выпуклых продолжений булевых функций

Полный текст

Введение

На протяжении многих десятилетий в истории цифровой науки булевы переменные были основными переменными, используемыми в большинстве компьютерных операций. Встречается много основных задач, связанных с булевыми переменными, а некоторые задачи, несмотря на зрелость области, не имеют удовлетворительных методов решения. Среди них проблема решения булевых и систем булевых уравнений [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] были найдены явные формы полилинейных продолжений для произвольных функций, определенных на множестве вершин -мерного единичного куба, произвольного куба и параллелепипеда, и в каждом конкретном случае была доказана единственность соответствующего полилинейного продолжения.

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

1. Основные понятия

Пусть $B^n=\left\{\right(b_1,b_2,\dots ,b_n):b_1,b_2,\dots ,b_n\in \{\mathrm{0,1}\left\}\right\}$ — множество всевозможных двоичных слов (булевых векторов) длины n, ${\mathit{K}}^n=\left\{\right(x_1,x_2,\dots ,x_n):x_1,x_2,\dots ,x_n\in [\mathrm{0,1}\left]\right\}$ — n-мерный куб, натянутый на булевые векторы длины n, $\mathrm{int}\left({\mathit{K}}^n\right)=\left\{\right(x_1,x_2,\dots ,x_n):x_1,x_2,\dots ,x_n\in (\mathrm{0,1}\left)\right\}$ — внутренность куба ${\mathit{K}}^n,$ $\mathit{F}{\mathit{K}}_{(b_1,b_2,\dots ,b_n)}^n=\left\{\right(x_1,x_2,\dots ,x_n)\in {\mathit{K}}^n:(2b_1-1)x_1+(2b_2-1)x_2+\dots +(2b_n-1)x_n\le b_1+b_2+\dots +b_n-1\}$ — фрагмент куба ${\mathit{K}}^n,$ противолежащий вершине $(b_1,b_2,\dots ,b_n)\in {\mathit{B}}^n.$

Определение 1.1. Функцию $f:{\mathit{K}}^n\to \mathit{R}$ назовем неотрицательной выпуклой функцией на ${\mathit{K}}^n,$ если для любых $x,y\in {\mathit{K}}^n$ и любого $\alpha \in \left[\mathrm{0,1}\right]$ выполняется

$0\le f(\alpha \cdot x+(1-\alpha )\cdot y)\le \alpha \cdot f\left(x\right)+(1-\alpha )\cdot f\left(y\right).$

Определение 1.2. Функцию $p_C:{\mathit{K}}^n\to \mathit{R}$ назовем неотрицательным выпуклым продолжением на ${\mathit{K}}^n$ булевой функции $p:{\mathit{B}}^n\to \left\{\mathrm{0,1}\right\},$ если выполнены два следующих условия:

а) функция $p_C$ является выпуклой и неотрицательной на ${\mathit{K}}^n$,

b) $p_C(b_1,b_2,\dots ,b_n)=p(b_1,b_2,\dots ,b_n)\forall (b_1,b_2,\dots ,b_n)\in {\mathit{B}}^n.$

2. Основные результаты

Лемма 2.1. Для булевой функции $K_{b_1\mathrm{,}{b}_2\mathrm{,}\dots \mathrm{,}{b}_n}\mathrm{,}$ заданной формулой

$K_{(b_1,b_2,\dots ,b_n)}(x_1,x_2,\dots ,x_n)=x_1^{b_1}\wedge x_2^{b_2}\wedge \dots \wedge x_n^{b_n},$

существует выпуклое неотрицательное продолжение $f_{(b_1,b_2,\dots ,b_n)}$ на ${\mathit{K}}^n.$ 

Доказательство. Для конструирования искомого продолжения заданной булевой функции сначала покажем, что если $f_{(b_1,b_2,\dots ,b_n)}$ — неотрицательное выпуклое продолжение на ${\mathit{K}}^n$ функции $K_{(b_1,b_2,\dots ,b_n)},$ то для любого вектора $(x_1^{*},x_2^{*},\dots ,x_n^{*})\in \mathit{F}{\mathit{K}}_{(b_1,b_2,\dots ,b_n)}^n$ выполнено $f_{(b_1,b_2,\dots ,b_n)}(x_1^{*},x_2^{*},\dots ,x_n^{*})=0.$

Включение $(x_1^{*},x_2^{*},\dots ,x_n^{*})\in \mathit{F}{\mathit{K}}_{(b_1,b_2,\dots ,b_n)}^n$ означает, что

$x_1^{}\mathrm{,}{x}_2^{}\mathrm{,}\dots \mathrm{,}{x}_n^{}\sum _{a_1\mathrm{,}{a}_2\mathrm{,}\dots \mathrm{,}{a}_n{\in }^n\backslash b_1\mathrm{,}{b}_2\mathrm{,}\dots \mathrm{,}{b}_n}{\lambda }_{a_1\mathrm{,}{a}_2\mathrm{,}\dots \mathrm{,}{a}_n}^{}\cdot a_1\mathrm{,}{a}_2\mathrm{,}\dots \mathrm{,}{a}_n$

где ${\lambda }_{(a_1,a_2,\dots ,a_n)}^{*}\ge 0$ и $\sum _{(a_1,a_2,\dots ,a_n)\in B^n\backslash \left\{\right(b_1,b_2,\dots ,b_n\left)\right\}}{\lambda }_{(a_1,a_2,\dots ,a_n)}^{*}=1.$ Теперь, с одной стороны, $(x_1^{*},x_2^{*},\dots ,x_n^{*})\in {\mathit{K}}^n$ и функция $f_{(b_1,b_2,\dots ,b_n)}(x_1,x_2,\dots ,x_n)$ неотрицательна на ${\mathit{K}}^n$ и, следовательно, $0\le f_{(b_1,b_2,\dots ,b_n)}(x_1^{*},x_2^{*},\dots ,x_n^{*}),$ с другой стороны, в силу неравенства Йенсена [15]

$f_{(b_1,b_2,\dots ,b_n)}(x_1^{*},x_2^{*},\dots ,x_n^{*})=f_{(b_1,b_2,\dots ,b_n)}(\sum _{(a_1,a_2,\dots ,a_n)\in B^n\backslash \left\{\right(b_1,b_2,\dots ,b_n\left)\right\}}\text{}{\lambda }_{(a_1,a_2,\dots ,a_n)}^{*}\cdot (a_1,a_2,\dots ,a_n\left)\right)$

$\le \sum _{(a_1,a_2,\dots ,a_n)\in B^n\backslash \left\{\right(b_1,b_2,\dots ,b_n\left)\right\}}\text{}{\lambda }_{(a_1,a_2,\dots ,a_n)}^{*}\cdot f_{(b_1,b_2,\dots ,b_n)}(a_1,a_2,\dots ,a_n)$

$=\sum _{(a_1,a_2,\dots ,a_n)\in B^n\backslash \left\{\right(b_1,b_2,\dots ,b_n\left)\right\}}\text{}{\lambda }_{(a_1,a_2,\dots ,a_n)}^{*}\cdot 0=0.$

Из двух полученных неравенств $0\le f_{(b_1,b_2,\dots ,b_n)}(x_1^{*},x_2^{*},\dots ,x_n^{*})\le 0$ следует, что

$f_{(b_1,b_2,\dots ,b_n)}(x_1^{*},x_2^{*},\dots ,x_n^{*})=0\forall (x_1^{*},x_2^{*},\dots ,x_n^{*})\in \mathit{F}{\mathit{K}}_{(b_1,b_2,\dots ,b_n)}^n.$ (2.1)

Теперь, пусть $(x_1^{*},x_2^{*},\dots ,x_n^{*})\in {\mathit{K}}^n\backslash \mathit{F}{\mathit{K}}_{(b_1,b_2,\dots ,b_n)}^n.$ В этой точке значение функции $f_{(b_1,b_2,\dots ,b_n)}$ определим формулой

$f_{(b_1,b_2,\dots ,b_n)}(x_1^{*},x_2^{*},\dots ,x_n^{*})={(1+\sum _{k=1}^n((2b_k-1)x_k^{*}-b_k\left)\right)}^2.$ (2.2)

Заметим, что

$f_{(b_1,b_2,\dots ,b_n)}(b_1,b_2,\dots ,b_n)={(1+\sum _{k=1}^n((2b_k-1)b_k-b_k\left)\right)}^2={(1-\sum _{k=1}^{n}2b_k(1-b_k\left)\right)}^2=1.$ (2.3)

Таким образом, из равенств (2.1)–(2.3) следует, что сконструированная выше функция $f_{(b_1,b_2,\dots ,b_n)}$ неотрицательна и

$f_{(b_1,b_2,\dots ,b_n)}(a_1,a_2,\dots ,a_n)=\left\{\begin{array}{c}\mathrm{0,}если(a_1,a_2,\dots ,a_n)\in {\mathit{B}}^n\backslash \left\{\right(b_1,b_2,\dots ,b_n\left)\right\},\\ \mathrm{1,}если(a_1,a_2,\dots ,a_n)=(b_1,b_2,\dots ,b_n),\end{array}\right.$

$=K_{(b_1,b_2,\dots ,b_n)}(a_1,a_2,\dots ,a_n).$

Чтобы завершить доказательство, остается показать, что функция $f_{(b_1,b_2,\dots ,b_n)}$ является выпуклой на ${\mathit{K}}^n.$ Объединив (2.1), (2.2), получим

$f_{(b_1,b_2,\dots ,b_n)}(x_1,x_2,\dots ,x_n)=\text{}\left\{\begin{array}{cc}\mathrm{0,}\text{}& \text{}если1+\sum _{k=1}^n\text{}\left(\right(2b_k\text{}-1)x_k\text{}-b_k)\text{}\le \mathrm{0,}\\ {(1+\sum _{k=1}^n\text{}((2b_k\text{}-1)x_k\text{}-b_k\left)\right)}^2\text{},\text{}& \text{}если1+\sum _{k=1}^n\text{}\left(\right(2b_k\text{}-1)x_k\text{}-b_k)\text{}\ge 0.\end{array}\right.$

Правая часть этого равенства может быть записана в следующем виде

$\frac{1}{4}{\left[\right(1+\sum _{k=1}^n\left(\right(2b_k-1)x_k-b_k))+|1+\sum _{k=1}^n\left(\right(2b_k-1)x_k-b_k)\left|\right]}^2.$ (2.4)

Используя (2.4), для любых $x,y\in {\mathit{K}}^n$ и $\alpha \in \left[\mathrm{0,1}\right]$ получаем

$f_{(b_1,b_2,\dots ,b_n)}(\alpha x+(1-\alpha \left)y\right)=\frac{1}{4}\left[\sum _{k=1}^n\right((2b_k-1)(\alpha x_k+(1-\alpha \left)y_k\right)-b_k)+1$

$+|\sum _{k=1}^n\left((2b_k-1)(\alpha x_k+(1-\alpha \left)y_k\right)-b_k\right)+1|{]}^2$

$=\frac{1}{4}\left[\alpha \right(\sum _{k=1}^n\left((2b_k-1)x_k-b_k\right)+1)+(1-\alpha \left)\right(\sum _{k=1}^n\left(\right(2b_k-1)y_k-b_k)+1)$

$+\left|\alpha \right(\sum _{k=1}^n\left((2b_k-1)x_k-b_k\right)+1)+(1-\alpha \left)\right(\sum _{k=1}^n\left(\right(2b_k-1)\cdot y_k-b_k)+1\left)\right|{]}^2$

$\le \frac{1}{4}\left[\alpha \right(\sum _{k=1}^n\left(\right(2b_k-1)x_k-b_k)+1)+(1-\alpha \left)\right(\sum _{k=1}^n\left(\right(2b_k-1)y_k-b_k)+1)$

$+\alpha \left|\sum _{k=1}^n\right((2b_k-1)x_k-b_k)+1|+(1-\alpha )\left|\sum _{k=1}^n\right((2b_k-1)y_k-b_k)+1|{]}^2$

$=\frac{1}{4}\left[\alpha \right\{\sum _{k=1}^n\left(\right(2b_k-1)x_k-b_k)+1+\left|\sum _{k=1}^n\right((2b_k-1)x_k-b_k)+1|\}$

$+(1-\alpha )\left\{\sum _{k=1}^n\right((2b_k-1)y_k-b_k)+1+|\sum _{k=1}^n\left(\right(2b_k-1)y_k-b_k)+1\left|\right\}{]}^2$

$\le \frac{1}{4}[\alpha {\left\{\sum _{k=1}^n\right((2b_k-1)x_k-b_k)+1+|\sum _{k=1}^n\left(\right(2b_k-1)x_k-b_k)+1\left|\right\}}^2$

$+(1-\alpha ){\left\{\sum _{k=1}^n\right((2b_k-1)y_k-b_k)+1+|\sum _{k=1}^n\left(\right(2b_k-1)y_k-b_k)+1\left|\right\}}^2]$

$=\alpha f_{(b_1,b_2,\dots ,b_n)}\left(x\right)+(1-\alpha )f_{(b_1,b_2,\dots ,b_n)}\left(y\right).$

Таким образом, функция $f_{(b_1,b_2,\dots ,b_n)}$ является выпуклой на ${\mathit{K}}^n.$  

Замечание 2.1. Неотрицательное выпуклое продолжение на ${\mathit{K}}^n$ булевой функции $K_{(b_1,b_2,\dots ,b_n)}$ является не единственным. Например, если $f_{(b_1,b_2,\dots ,b_n)}$ является таким продолжением, то и функция, имеющая значения ${\left(f_{(b_1,b_2,\dots ,b_n)}\right(x_1,x_2,\dots ,x_n\left)\right)}^2,$ также будет неотрицательным выпуклым продолжением на ${\mathit{K}}^n$ функции $K_{(b_1,b_2,\dots ,b_n)}.$ 

Теорема 2.1. Для произвольной булевой функции $p:{\mathit{B}}^n\to \left\{\mathrm{0,1}\right\}$ существует выпуклое неотрицательное продолжение $p_C$ на ${\mathit{K}}^n.$ 

Доказательство. Пусть задана булева функция $p:{\mathit{B}}^n\to \left\{\mathrm{0,1}\right\}.$ Используя подходы, предложенные в [11, теорема 2], зададим функцию $p_C:{\mathit{K}}^n\to \mathit{R}$ формулой

$p_C(x_1,x_2,\dots ,x_n)=\sum _{(b_1,b_2,\dots ,b_n)\in {\mathit{B}}^n}p(b_1,b_2,\dots ,b_n)\cdot f_{(b_1,b_2,\dots ,b_n)}(x_1,x_2,\dots ,x_n),$ (2.5)

где функция $f_{(b_1,b_2,\dots ,b_n)},$ являющаяся выпуклым неотрицательным продолжением булевой функции $K_{(b_1,b_2,\dots ,b_n)},$ определена в лемме 2.1. Докажем, что функция (2.5) является требуемым продолжением булевой функции p.

Сначала заметим, что в силу определения функция $p_C$ выпукла на множестве ${\mathit{K}}^n,$ так как является суммой выпуклых функций.

Остается проверить, что для любого $(a_1,a_2,\dots ,a_n)\text{}\in \text{}{\mathit{B}}^n$ выполнено $p_C(a_1,a_2,\dots ,a_n)\text{}=p(a_1,a_2,\dots ,a_n).$ Действительно, в силу леммы 2.1 имеем:

$p_C(a_1,a_2,\dots ,a_n)=\sum _{(b_1,b_2,\dots ,b_n)=(a_1,a_2,\dots ,a_n)}p(b_1,b_2,\dots ,b_n)\cdot f_{(b_1,b_2,\dots ,b_n)}(a_1,a_2,\dots ,a_n)$

$+\sum _{(b_1,b_2,\dots ,b_n)\in B^n\backslash (a_1,a_2,\dots ,a_n)}p(b_1,b_2,\dots ,b_n)\cdot f_{(b_1,b_2,\dots ,b_n)}(a_1,a_2,\dots ,a_n)$

$=p(a_1,a_2,\dots ,a_n)\cdot f_{(a_1,a_2,\dots ,a_n)}(a_1,a_2,\dots ,a_n)$

$+\sum _{(b_1,b_2,\dots ,b_n)\in B^n\backslash (a_1,a_2,\dots ,a_n)}p(b_1,b_2,\dots ,b_n)\cdot 0=p(a_1,a_2,\dots ,a_n).$

Итак, доказано, что функция (2.5) является выпуклым неотрицательным продолжением на ${\mathit{K}}^n$ булевой функции p. 

Замечание 2.2. Если для булевой функции p выполнено $p(x_1,x_2,\dots ,x_n)\equiv \mathrm{0,}$ то ее неотрицательное выпуклое продолжение $p_C$ на ${\mathit{K}}^n$ определяется единственным образом, причем в этом случае $p_C(x_1,x_2,\dots ,x_n)=0$ $\forall (x_1,x_2,\dots ,x_n)\in {\mathit{K}}^n.$ Действительно, для $(x_1,x_2,\dots ,x_n)\in {\mathit{K}}^n$ выполнено

$0\le p_C(x_1,x_2,\dots ,x_n)=p_C\left(\right(1-x_1)\cdot 0+x_1\cdot \mathrm{1,}{x}_2,\dots ,x_n)$

$=p_C\left(\right(1-x_1)\cdot 0+x_1\cdot \mathrm{1,}(1-x_1)\cdot x_2+x_1\cdot x_2,\dots ,(1-x_1)\cdot x_n+x_1\cdot x_n)$

$\le (1-x_1)\cdot p_C(\mathrm{0,}{x}_2,\dots ,x_n)+x_1\cdot p_C(\mathrm{1,}{x}_2,\dots ,x_n)$

$\le \dots \le \sum _{(b_1,b_2,\dots ,b_n)\in B^n}{p}_C(b_1,b_2,\dots ,b_n)\cdot \prod _{k=1}^n\left(\right(2b_k-1)x_k+1-b_k)$

$=\text{}\sum _{(b_1,b_2,\dots ,b_n)\in B^n}\text{}p(b_1,b_2,\dots ,b_n)\cdot \prod _{k=1}^n\left(\right(2b_k\text{}-1)x_k\text{}+1-b_k)=\text{}\sum _{(b_1,b_2,\dots ,b_n)\in B^n}\text{}0\cdot \prod _{k=1}^n\left(\right(2b_k\text{}-1)x_k\text{}+1-b_k)=0.$

Замечание 2.3. Если для булевой функции p выполнено $p(x_1,x_2,\dots ,x_n)\cancel{\equiv }\mathrm{0,}$ то ее неотрицательное выпуклое продолжение $p_C$ на ${\mathit{K}}^n$ не является единственным. Это прямо следует из неединственности функции $f_{(b_1,b_2,\dots ,b_n)},$ через которую формулой (2.5) определяется функция $p_C$ (см. замечание 2.1).

3. Применение выпуклого продолжения булевой функции к решению системы булевых уравнений

Рассмотрим систему булевых уравнений

$p_1(x_1,x_2,\dots ,x_n)=\mathrm{0,}\cdots ,p_m(x_1,x_2,\dots ,x_n)=0.$ (3.1)

Трансформируем эту систему в соответствующую систему выпуклых уравнений

${p_C}_1(x_1,x_2,\dots ,x_n)=\mathrm{0,}\cdots ,{p_C}_m(x_1,x_2,\dots ,x_n)=\mathrm{0,}$ (3.2)

где функция ${p_C}_i$ — выпуклое продолжение булевой функции $p_i\mathrm{,}$ $i=\overline{\mathrm{1,}m},$ т. е., как показано при доказательстве теоремы 2.1, может быть определена формулой

${p_C}_i(x_1,x_2,\dots ,x_n)=\sum _{(b_1,b_2,\dots ,b_n)\in B^n}{p}_i(b_1,b_2,\dots ,b_n)\cdot f_{(b_1,b_2,\dots ,b_n)}(x_1,x_2,\dots ,x_n).$

Задача решения системы (3.2), очевидно, сводится к задаче минимизации функции ${\overline{p}}_C\mathrm{,}$ определяемой соотношением

${\overline{p}}_C(x_1,x_2,\dots ,x_n)=\sum _{i=1}^n{p_C}_i(x_1,x_2,\dots ,x_n).$

Перечислим некоторые свойства функции ${\overline{p}}_C\mathrm{,}$ полезные при решении задачи минимизации (в частности, с точки зрения уменьшения количества локальных минимумов).

Свойство 3.1. На множестве ${\mathit{K}}^n$ функция ${\overline{p}}_C$ выпуклая и непрерывно дифференцируемая.

Свойство 3.2. На множестве ${\mathit{K}}^n$ любой локальный минимум функции ${\overline{p}}_C$ является также и глобальным минимумом.

Свойство 3.3. Если вектор $(s_1,s_2,\dots ,s_n)\in {\mathit{B}}^n$ является решением системы (6), то он будет являться решением системы (7) и ${\overline{p}}_C(s_1,s_2,\dots ,s_n)=0.$  

Свойство 3.4. Вектор $(r_1,r_2,\dots ,r_n)\in {\mathit{K}}^n$ будет решением системы (7) в том и только в том случае, когда ${\overline{p}}_C(r_1,r_2,\dots ,r_n)=0.$ 

Справедливость свойств 3.1–3.4 следует из определения функции ${\overline{p}}_C\mathrm{.}$

Авторы выражают искреннюю благодарность рецензенту за полезные замечания и нахождение ряда недостатков, исправление которых помогло улучшить содержание статьи.

Об авторах

Достонжон Нумонжонович Баротов

ФГОБУ ВО «Финансовый университет при Правительстве Российской Федерации»

Автор, ответственный за переписку.
Email: DNBarotov@fa.ru
ORCID iD: 0000-0001-5047-7710

старший преподаватель департамента анализа данных и машинного обучения

Россия, 125167, Москва, пр-т Ленинградский, 49/2

Рузибой Нумонжонович Баротов

Худжандский государственный университет имени академика Б. Гафурова

Email: ruzmet.tj@mail.ru
ORCID iD: 0000-0003-3729-6143

докторант, кафедра математического анализа имени профессора А. Мухсинова

Россия, 735700, Республика Таджикистан, Худжанд, проезд Мавлонбекова, 1

Список литературы

Дополнительные файлы