Автоматика и телемеханика, № 9, 2021
Оптимизация, системный анализ
и исследование операций
© 2021 г. В.К. ЛЕОНТЬЕВ, д-р физ.-мат. наук (vkleontiev@yandex.ru)
(ВЦ им. А.А. Дородницына ФИЦ ИУ РАН, Москва),
Э.Н. ГОРДЕЕВ, д-р физ.-мат. наук (werhorn@yandex.ru)
(МГТУ им. Н.Э. Баумана, Москва)
О ЧИСЛЕ РЕШЕНИЙ СИСТЕМЫ БУЛЕВЫХ УРАВНЕНИЙ1
Рассматриваются вопросы, касающиеся разрешимости и числа реше-
ний систем булевых уравнений. Многие математические модели, возни-
кающие как в исследовании операций, так и в криптографии, описыва-
ются на языке таких систем. Это связано, в частности, и с тем, что в
общем виде проблема проверки совместности таких систем уравнений яв-
ляется NP-полной, поэтому исследование качественных свойств системы
булевых уравнений дает дополнительную информацию, позволяющую ли-
бо выделить полиномиально разрешимые частные случаи, либо повысить
эффективность переборных схем. Основное внимание уделено двум ас-
пектам. Первый касается исследования наличия и числа решений булева
уравнения и системы уравнений при параметризации задачи по правым
частям. Даются формулы и оценки для подсчета этого числа как в общем,
так и в частных случаях. Исследуется и его максимум в зависимости от
указанного параметра. Второй аспект посвящен частному случаю задачи,
когда уравнение задается так называемой непрерывной линейной формой.
Изучаются свойства таких форм и различные критерии непрерывности.
Ключевые слова: NP-полнота, булевы уравнения, задача булева програм-
мирования, линейное преобразование, непрерывная линейная форма.
DOI: 10.31857/S0005231021090063
1. Введение
Линейные диофантовы уравнения и неравенства являются стандартным
объектом для различного рода математических моделей, относящихся к це-
лочисленной оптимизации, защите информации, теории чисел, геометрии и
т.д.
Классическая задача о ранце с булевыми переменными имеет вид
∑
∑
(1)
cjxj → max,
aixi
≤ b,
j=1
i=1
где x = (x1, . . . , xn) - n-мерный булевский вектор.
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований
(проект № 20-01-00645).
150
Пусть L(x1, . . . , xn) - линейная форма
∑
(2)
L(x1, . . . , xn) =
aixi,
i=1
где все параметры {ai} и неизвестные {xi} - натуральные числа. Накладывая
определенные условие на вид этой формы, можно получить разные частные
случаи общей задачи. Так, в булевой задаче о ранце переменные полагаются
булевыми.
Таким образом, множество допустимых решений должно удовлетворять
∑n
условию
aixi ≤ b, т.е. векторы x = (x1,... ,xn) должны лежать ниже ги-
i=1
перплоскости L(x1, . . . , xn) = b.
В матричной форме система ограничений имеет вид
(3)
Ax = b,
где A = (aij )m×n - матрица.
Накладывая определенные ограничения на матрицу A и вектор b, полу-
чаем различные частные случаи задачи, см., например, [1, 2].
Если все параметры и переменные - произвольные вещественные числа, то
вопрос о разрешимости системы решается в терминах ранга матрицы огра-
ничений.
Из этих результатов линейной алгебры можно получить необходимые усло-
вия разрешимости и для таких частных случаев задачи, как задача целочис-
ленного линейного программирования и задача булева программирования,
см., например, [1-3].
В области исследования операций и комбинаторной оптимизации данная
задача целочисленного линейного программирования или ее обобщения и
сужения занимают ключевое место, как это показано, например, в [1]. То,
что задача является NP-полной, было установлено в числе первых резуль-
татов подобных исследований. Кроме того, в классической публикации [2]
можно найти многочисленные примеры известных задач, которые к ней сво-
дятся, и, наоборот, задача целочисленного линейного программирования (или
ее булев вариант) сводится к той или иной проблеме.
Данная статья в одной из своих частей является продолжением исследова-
ний авторов этой работы, опубликованных в [4, 5], где речь шла про задачу о
рюкзаке. Ключевую роль в получении результатов там сыграл аппарат про-
изводящих функций, который используется и в настоящей статье. Как видно
из подробнейшей монографии [6], данный подход позволил получить ряд но-
вых и оригинальных результатов.
Следует заметить, что вопросы, поставленные в статье, ранее с той или
иной точки зрения, рассматривались в статьях В.К. Леонтьева и Г.П. Тонояна
[7, 8]. В монографии [9] ряд результатов получен на основе комбинаторных
подходов в задачах рюкзачного типа.
С прикладной точки зрения, изучаемая проблематика затрагивалась ав-
торами в связи с криптографическими объектами: аннигиляторами и алгеб-
151
раической иммунностью. Одно из ключевых утверждений публикации [10],
посвященной аннигиляторам и алгебраической иммунности, базируется на
анализе совместимости системы уравнений и сводится к нахождению комби-
наторной характеристики (аналога ранга) матрицы.
В [10, 11], где речь идет о булевых полиномах, как частный случай возни-
кают линейные булевы полиномы.
Исследования в той же области, но другими методами проводились в ин-
ститутах Екатеринбурга и Новосибирска. В качестве примеров можно приве-
сти работы [12, 13].
Статья состоит из четырех разделов. Раздел 2 посвящен применению ме-
тода производящих функций для исследования решений системы уравнений.
Затем рассматривается как общий случай, так и частные случаи задачи.
Раздел 3 посвящен комбинаторным свойствам линейных форм L(x1, . . . , xn).
В разделе 4 приведены выводы.
Некоторые определения, понятия и методы доказательств ранее были ис-
пользованы авторами этой статьи в публикациях [4, 5, 14-16].
Везде в дальнейшем будем считать, что все параметры рассматриваемой
задачи, числа c1, . . . , cn; a1, . . . , an; b - неотрицательные целые числа.
2. О числе решений системы булевых уравнений
Актуальность исследования наличия решений системы булевых уравнений
вытекает из того факта, что NP-полной проблемой является уже ответ на
вопрос: совместна ли система булевых уравнений?
Поэтому получение нижней оценки числа решений системы булевых урав-
нений является достаточно естественной задачей. Если хотя бы в каких-то
случаях оценка эта дает значение, не меньшее единицы, то это может иметь
прикладное значение, так как решается NP-полная задача. Кроме того, полу-
чение такой оценки основывается на учете комбинаторики задачи, в то время
как очевидный алгоритм проверки разрешимости задачи булева программи-
рования - перебор всех 2m булевых векторов - не дает понимания, от чего
зависит разрешимость системы (в отличие от классического случая системы
линейных уравнений).
Обозначим через tb1...bm(A)-числорешенийзадачибулевапрограммиро-
вания с системой ограничений вида Ax = b, где A = (aij )m×n - матрица.
Зафиксируем матрицу ограничений и будем варьировать вектор правых
частей. Получим последовательность чисел {tb1...bm(A)},гдеtb1...bm(A)-ко-
личество решений системы для фиксированного вектора правых частей.
Для этой последовательности имеем производящую функцию
FA(z1, . . . , zn) в виде полинома
∑
FA(z1, . . . , zn) =
zb11z22 ... znm tb1...bm (A).
{b1,...,bm}
152
Заметим, что согласно введенным выше обозначениям вектор
(a1k, . . . , amk) - это k-й столбец матрицы ограничений.
Лемма 1. Справедлива формула
∏
(4)
FA(z1, . . . , zm) =
).
(1 + za1k1 ... zmmk
k=1
Доказательство.
∑
FA(z1, . . . , zm) =
zb11z22 ... zmm tb1...bm (A) =
{b1,...,bm}
∑
=
za11x1+...+a1nxn1z221x1+...+a2nxn . . . zmm1x1+...+amnxn =
x∈Bn
∑
∑
1
= za11x11z221x1 ... zmm1x
za21x21z222x2 . . . zmm2x2 . . .
x1=0
x2=0
∑
za1nxn1z22nxn . . . zmmnxn =
xB=0
= (1 + za111 z221 . . . zmm1 ) (1 + z112 z222 . . . zmm2 ) . . . (1 + z11n z22n . . . zmmn ) =
∏
=
(1 + za1k1 . . . zmmk ) .
k=1
Лемма 1 доказана.
Этот подход дает возможность найти число решений задачи булева про-
граммирования в зависимости от параметров A и b.
Пример 1. Рассмотрим задачу:
x1 + x2 + ... + xn = b1,
x2 + x3 + ... + xn+1 = b2.
Здесь матрица ограничений задана и имеет вид
(
)
11 . . . 10
A=
01 . . . 11
Из леммы 1 следует, что FA(z1, z2) = (1 + z1)(1 + z1z2)n-1(1 + z2). Отсюда
видно, что мономы с положительными коэффициентами zα11 z22 определяют
те векторы (b1, b2), для которых система уравнений разрешима.
В частности, для n = 3 рассмотрим следующий пример:
x1 + x2 + x3 = b1,
x2 + x3 + x4 = b2.
153
Здесь матрица ограничений задана и имеет вид
(
)
1110
A=
0111
Из леммы 1 следует, что
FA(z1, z2) = (1 + z1)(1 + z1z2)2(1 + z2) =
= 1 + z1 + z2 + 3z1z2 + 2z21z2 + 2z1z22 + 2z21z22 + z31z32.
Отсюда видим, что система разрешима для следующих векторов правых
частей: (0,0), (0,1), (1,0), (1,1), (2,1), (1,2), (2,2), (2,3), (3,2), (3,3).
Кроме того, непосредственно из доказанной леммы 1 следует утверждение.
Следствие 1. Число разрешимых систем булевых уравнений вида
Ax = b равно числу мономов, входящих с ненулевыми коэффициентами в
полином FA(z1, . . . , zn).
Так как в рассматриваемом случае матрица системы фиксируется, то бу-
дем считать, что различные разрешимые системы отличаются значением
вектора правых частей, при котором обе системы имеют решение. Заметим
теперь, что число различных мономов в полиноме FA(z1, . . . , zn) не может
превышать его степени. Поэтому отсюда получаем еще одно утверждение.
Следствие 2. Число разрешимых систем булевых уравнений вида
Ax = b не превышает степени полинома FA(z1, . . . , zn).
Рассмотрим теперь еще одну комбинаторную задачу, которую можно ре-
шить с помощью доказанной леммы 1.
Пусть система разрешима. Мы ищем ее решения с помощью какой-нибудь
эвристики, задающей правило перебора по всему Bn. Чем больше у системы
решений, тем быстрее на какое-то из них можно “наткнуться”. Если решаем
не произвольную систему уравнений, а отражающую специфику некоторой
прикладной задачи исследования операций, то особенности этой задачи от-
ражаются на параметрах системы, в частности на векторе правых частей.
В связи с этим могут быть интересны оценки числа tb1...bm(A). Следующая
теорема дает одну такую оценку.
∑
Теорема 1. Пусть v =
max
ark, тогда справедливо неравенство
r=1,...,m
k=1
n
2
(5)
max
tb1...bm(A)≥
{b1,...,bm}
mv
Доказательство. C одной стороны, сумма всех коэффициентов поли-
нома FA(z1, . . . , zn) равна FA(1, . . . , 1), т.е. равна 2n.
Из леммы 1 имеем
∑
∏
(6)
FA(z1, . . . , zn) =
).
zb11z22 ... znm tb1...bm (A) =
(1 + za1k1 . . . zmmk
{b1,...,bm}
k=1
154
Поэтому, с другой стороны, можно оценить общее число мономов в (6).
Положим по определению, что степень монома W = zv11 . . . zmm равна
deg W = max
vi.
i=1,...,m
Тогда справедливо неравенство:
deg(W1W2) ≤ deg W1 + deg W2.
Теперь имеем сначала равенство
deg W = deg(za1k1 . . . zmmk ) = maxr=1,...,m ark,
а затем получаем соотношение
(
)
∏
∑
deg
=
max
ark = v.
(1 + za1k1 ... zmmk )
r=1,...,m
k=1
k=1
Отсюда следует, что степень любого монома в (6) не превосходит v. По-
этому общее число мономов на превосходит mv.
Но это означает, что хотя бы один коэффициент у полинома FA(z1, . . . , zn)
не меньше2nmv.
Теорема 1 доказана.
Конечно, оценка (5) очень слабая и бывает полезна только в специальных
случаях. Но так и должно быть, так как проблема проверки разрешимости
задачи булева программирования является NP-трудной, а проверка соотно-
шения (5) осуществляется с полиномиальной трудоемкостью. (Заметим, что
в рассматриваемой ситуации имеем не конкретную индивидуальную задачу
булева программирования, а семейство таких задач, параметризованное по
{b1, . . . , bm}.)
Пример 2. Пусть есть два уравнения и A = (aij)2×n - матрица из нулей
и единиц.
Тогда при m = 2 и v ≤ n из (5) получаем, что max
tb1b2 (A) ≥ 1.
{b1,b2}
Но это очевидно, так как число единиц в строке матрицы определяет век-
тор правых частей того набора, на котором достигается максимум. В более
сложных случаях структура подобного набора не всегда очевидна. Однако
и сам подход к проблеме нахождения max
tb1b2 (A) на основе схемы доказа-
{b1,b2}
тельства теоремы 1 может быть полезен, что показывает следующий пример.
Пример 3. Рассмотрим систему уравнений:
x1 + 2x2 + 3x3 + 4x4 = b1,
2x1 + x2 + x3 + 3x4 = b2.
(
)(
)(
)(
)
(7)
FA(z1, z2) =
1+z1z22
1+z21z2
1+z31z2
1+z41z32
Раскрывая скобки, видим, что моном максимальной степени z101z72. Поэтому
< 1.
правая часть (5) меньше единицы:2nmν
217
155
Но приводя подобные в (7), видим, что max
(A) = 2 и максимум
tb1b2
{b1,b2}
достигается на парах b1 = 4, b2 = 3 и b1 = 6, b2 = 4. (Для первого случая это
решения (0,0,0,1) и (1,0,1,0), а для второго - (0,1,0,1) и (1,1,1,0).)
Пример 4. Рассмотрим систему уравнений:
x1 + x2 + x3 + x4 = b1,
x2 + 2x4 = b2.
(8)
FA(z1, z2) = (1 + z1z2)(1 + z1)2(1 + z1z2).
Раскрывая скобки, видим, что моном максимальной степени z41z32. Поэтому
правая часть (5) вновь меньше единицы.
Но приводя подобные в (8), видим, что max
tb1b2 (A) = 2 и максимум до-
{b1,b2}
стигается на парах b1 = 2, b2 = 1, b1 = 2, b2 = 2 и b1 = 3, b2 = 3. (Для первого
случая это решения (1,1,0,0) и (0,1,1,0), для второго - (0,0,1,1) и (1,0,0,1), а
для третьего - (0,1,1,1) и (1,1,0,1).)
Рассмотрим теперь вопрос о числе решений системы булевых уравнений
с несколько иной точки зрения. Пусть дана линейная форма (2) с булевы-
ми переменными. Множество значений этой линейной формы обозначим че-
рез L∗(a1, . . . , an). (А если это не вызывает неопределенности, то просто че-
рез L∗.)
∑n
Сама же форма L∗(x1, . . . , xn) =
aixi, зависящая от переменных
i=1
x1,... ,xn, будет для краткости обозначаться через L.
Пример 5. Если ai = 1, i = 1,...,n, то L∗ = {0,1,2,... ,n}.
Пример 6. Если ai = 2i-1, i = 1,...,n, то L∗ = {0,1,2,... ,2n - 1}.
Пример 7. Если L(x1,...,xn) = x1 + x2 + ... + xn-1 + nxn, то L∗ =
= {0, 1, . . . , n, n + 1, . . . , 2n - 1}.
В этом случае уравнение L(x1, . . . , xn) = b имеет решение для всех b, удовлет-
воряющих условию 0 ≤ b ≤ 2n - 1.
Пример 8. Если L(x1,...,xn) = 2x1 + 3x2 + 3x3 + 3x4, то L∗ =
= {0, 2, 3, 5, 6, 8, 9, 11}. В этом случае уравнение L(x1, . . . , xn) = b имеет
решение для всех b, удовлетворяющих условию
0 ≤ b ≤ 11, кроме b =
= 1, 4, 7, 10.
Просто из введенных определений получаем следующее утверждение.
Утверждение 1. Уравнение L(x) = b разрешимо тогда и только то-
гда, когда b ∈ L∗.
Заметим, что L∗(a1, . . . , an) не зависит от упорядоченности элементов
a1,... ,an, поэтому в дальнейшем будем считать, что
(9)
a1 ≤ a2 ... ≤ an.
Определение 1. Формы L1(x1,...,xn) и L2(x1,...,xn) называются эк-
вивалентными, если L∗1 = L∗2.
156
Пусть, как обычно, n - число переменных, а N - целое число такое, что
(10)
1≤ak
≤ N, k = 1,... ,n.
Через t(n, N) обозначим число линейных форм с параметрами n и N.
Лемма 2. Справедливо равенство t(n,N) = CnN+n-1.
Доказательство. Каждая линейная форма с условиями (9) и (10) мо-
жет быть закодирована в алфавите {1, . . . , N} словом вида 1y1 2y2 . . . NyN ,
где yr, r = 1, . . . , N, - число коэффициентов, равных r, среди чисел a1, . . . , an.
Отсюда следует, что искомое число слов t(n, N) - это число решений уравне-
ния y1 + y2 + . . . + yN = n, yi ≥ 0, i = 1, . . . , N. Но отсюда и следует равенство
t(n, N) = CnN+n-1.
Лемма 2 доказана.
Пусть, как и раньше, tb(a1, . . . , an)
- число решений уравнения
∑n
L(x1, . . . , xn) =
aixi = b, а ntb(a1,... ,an) - число решений неравенства
i=1
∑
n
L(x1, . . . , xn) =
aixi ≤ b. Исследуем эти величины. Обозначим через Vb
i=1
множество решений соответствующей задачи (уравнения или неравенства).
Пусть производящая функция для числа решений неравенства
∑
(11)
Pb(z1,... ,zn) =
).
za1x11z22x2 ... znnxnntb(a1,... ,an
x∈Vb
Лемма 3. Справедлива формула
∑
(1 + (z1u)a1 ) . . . (1 + (znu)an )
(12)
Pb(z1,... ,zn)ub =
1-u
b=0
Доказательство. Преобразуем сумму (11), используя метод коэффи-
циентов (в первом равенстве цепочки нижеприведенных выкладок учтено со-
∑n
отношение
aixi ≤ b),
i=1
∑
aixi
∑
∑
ui=1
Pb(z1,... ,zn) =
=
za1x11z22x2 ... znnxn Coef
u
ut+1
t=0 x∈Vt
{
}
∑
∑
∑
1
= Coef
(z1u)a1x1 . . .
(znu)anxn
=
u
ut+1
t=0
x=0
x=0
{
}
1
∏
-1
ub+2
= Coefu
(1 + (zku)ak )
=
u
1-1
u k=1
{
}
n
∏
1
(13)
= Coef
(1 + (zku)ak )
u
ub+1(1 - u)
k=1
Сравним (12) и (13) и увидим, что (12) просто “содержится” в (13).
157
Лемма 3 доказана.
Рассмотрим теперь следствие 3 из леммы 3 и с его помощью проиллю-
стрируем ее смысл. (Все нижеприведенные интегралы берутся по контуру,
который указан под знаком интеграла.)
Следствие 3. Пусть 0 < ρ < 1. Тогда для объема области решений име-
ет место равенство
∮
1
(1 + ua1 ) . . . (1 + uan )
(14)
ntb(a1,... ,an) =
du.
2πi
(1 - u)ub+1
|u|=ρ
Сам смысл метода коэффициентов - это выражение коэффициента при
минус первой степени переменной (оно представлено формулой (13)) через
сумму вычетов, что представлено формулой (14). Именно это и приведено в
качестве следствия 3 из леммы 3.
Пример 9. Пусть все aj = 0, j = 1,...,n.
Очевидно, что в этом случае множество решений совпадает со всем буле-
вым кубом. Но это и следует из (14):
∮
1
(1 + ua1 ) . . . (1 + uan )
|Vb| =
du =
2πi
(1 - u)ub+1
|u|=ρ
{
}
∮
∮
∑
1
1
2n
=
du =
uk-b+1
du = 2n.
2πi
(1 - u)ub+1
2πi
k=0
|u|=ρ
|u|=ρ
Пример 10. Пусть все aj = 1, j = 1,...,n.
∑b
Очевидно, что в этом случае объем множества решений равен
Ckn.
k=0
Но это и следует из (14):
∮
1
(1 + ua1 ) . . . (1 + uan )
|Vb| =
du =
2πi
(1 - u)ub+1
|u|=ρ
∮
∑
1
(1 + u)n
=
du = Ckn.
2πi
(1 - u)ub+1
k=0
|u|=ρ
Пример 11. Пусть все aj = 2j-1, j = 1,...,n. Тогда в неравенстве
∑n
aixi ≤ b слева стоит некоторая двоичная запись натурального числа.
i=1
Поэтому при b > 2n допустимые решения - весь булев куб. В противном слу-
чае решений ровно b, так как любое натуральное число однозначно пред-
ставимо в двоичной записи. Отсюда следует, что объем множества решений
равен min {b, 2n}.
158
В рассматриваемом случае из (14) следует:
∮
1
(1 + ua1 ) . . . (1 + uan )
|Vb| =
du =
2πi
(1 - u)ub+1
|u|=ρ
∮
1
(1 + u)(1 + u2) . . . (1 + u2n-1 )
=
du =
2πi
(1 - u)ub+1
|u|=ρ
{
}
∮
∮
∑
∑
1
1
1
=
um du =
du = min{b,2n}.
2πi
2πi
(1 - u)ub-k+1
m=0
k=0
|u|=ρ
|u|=ρ
Здесь тот факт, что любое натуральное число однозначно представимо в
двоичной системе исчисления, заключается в использовании соотношения
∏
∑
(1 + u2k ) =
um.
k=0
m=0
Очевидно, что интеграл в последнем равенстве равен единице при
b > k - 1 и нулю в противном случае. (Заметим, что единица не является
особой точкой!)
Теперь перейдем к рассмотрению числа решений уравнения.
Лемма 4. Справедливо соотношение
∮
1
(1 + ua1 ) . . . (1 + uan )
tb(a1,... ,an) =
du, ρ < 1.
2πi
ub+1
|u|=ρ
Доказательство. Из леммы 1 совершенно аналогично доказательству
леммы 3 получаем:
∑
aixi
∑
ui=1
FA(z1, . . . , zn) =
za1x11 ... znnxn Coef
=
u
ub+1
x∈Vb
{
}
1
∑
∑
1
= Coef
(z1u)a1x1 . . .
(znu)anxn
=
u
ub+1
x=0
x=0
{
}
n
∏
1
(15)
= Coef
(1 + (zku)ak )
u
ub+1
k=1
Откуда и следует утверждение леммы. Лемма 4 доказана.
159
Рассмотрим теперь вопрос о среднем значении tb(a1, . . . , an) для фиксиро-
ванного значения b по всему булеву кубу при условиях (9) и (10).
Обозначим это число через tb. (То есть это среднее значение tb(a1, . . . , an)
по всему множеству 1 ≤ ak ≤ N, k = 1, . . . , n.)
С учетом (9), (10) из леммы 4 имеем следующее соотношение
∑
∑
1
(16)
tb =
tb(a1,... ,an
).
Cn
n+N-1 i=1 ai=ai-1
Здесь считаем, что a0 = 1.
Лемма 5. Справедлива формула
(
)n
∮
N+u-uN+1
1
1
1-u
(17)
tb =
du, ρ < 1.
Cn
2πi
ub+1
n+N-1
|u|=ρ
Для доказательства леммы 5 непосредственно подставляем (15) в (16) и
проводим суммирование, используя наличие геометрической прогрессии.
Рассмотрим в качестве примера случай трех переменных при произволь-
ном N. (Всюду далее считаем, что ρ < 1.)
В этом случае CnN+n-1 = C3N+2, а отсюда
(
)3
u-uN+1
(u-uN+1)
N +
= N3 + 3N2
+
1-u
1-u
)2
N+1
(u-u
(u-uN+1)3
+ 3N
+
1-u
1-u
Из (17) следует
(
)
(
)2
(
)3
∮
u-uN+1
u-uN+1
u-uN+1
N3 + 3N2
+ 3N
+
1
1
1-u
1-u
1-u
tb =
du =
C3
2πi
ub+1
N+2
|u|=ρ
∮
∮
3
N
1
1
3N2
1
1-uN
=
du +
du +
b
C3
2πi
ub+1
C3
2πi
(1 - u)u
N+2
N+2
|u|=ρ
|u|=ρ
∮
(
)2
∮
(
)3
3N
1
1-uN-1
1
1
1-uN-2
+
du +
du.
C3
2πi
(1 - u)2ub-1
C3
2πi
(1 - u)3ub-2
N+2
N+2
|u|=ρ
|u|=ρ
Для двух переменных при произвольном N имеем следующее.
160
В этом случае CnN+n-1 = C2N+1, а отсюда
(
)2
u-uN+1
(u-uN+1)
(u-uN+1)2
N+
= N2 + 2N
+
1-u
1-u
1-u
Из (17) следует
(
)
(
)2
∮
u-uN+1
u-uN+1
N2 + 2N
+
1
1
1-u
1-u
tb =
du =
C2
2πi
ub+1
N+1
|u|=ρ
∮
∮
2
N
1
1
2N
1
1-uN
=
du +
du +
b
C2
2πi
ub+1
C2
2πi
(1 - u)u
N+1
N+1
|u|=ρ
|u|=ρ
∮
(
)2
1
1
1-uN
+
du =
C2
2πi
(1 - u)2ub-1
N+1
|u|=ρ
∮
∮
2
N
1
1
2N
1
1-uN
=
du +
du +
b
C2
2πi
ub+1
C2
2πi
(1 - u)u
N+1
N+1
|u|=ρ
|u|=ρ
∮
1
1
(1 - u)-2
(
)2
+
1-uN
du =
C2
2πi
ub-1
N+1
|u|=ρ
∮
∮
2
N
1
1
2N
1
du
=
du +
+
b
C2
2πi
ub+1
C2
2πi
(1 - u)u
N+1
N+1
|u|=ρ
|u|=ρ
∮
∮
(
)
2N
1
du
1
1
(1 - u)-2
1 - 2uN + u2N
+
+
du.
C2
2πi
(1 - u)ub-N
C2
2πi
ub-1
N+1
N+1
|u|=ρ
|u|=ρ
Представим это выражение в виде двух слагаемых, которые рассмотрим по
отдельности, т.е. tb = A + B, где
∮
∮
2
N
1
1
2N
1
du
A=
du +
+
b
C2
2πi
ub+1
C2
2πi
(1 - u)u
N+1
N+1
|u|=ρ
|u|=ρ
∮
2N
1
du
+
,
C2
2πi
(1 - u)ub-N
N+1
|u|=ρ
∮
(
)
1
1
(1 - u)-2
1 - 2uN + u2N
B=
du.
C2
2πi
ub-1
N+1
|u|=ρ
161
Пусть δ - некоторая константа. Тогда первое слагаемое можно представить
в виде
∑
∮
∮
uj
2
N
1
1
2N
1
j=0
A=
du +
du +
b
C2
2πi
ub+1
C2
2πi
u
N+1
N+1
|u|=ρ
|u|=ρ
∑
∮
uj
2N
1
j=0
N2
2N
2N
+
du =
δb +
+
δb-N .
C2
2πi
ub-N
C2N+1
C2N+1
C2
N+1
N+1
|u|=ρ
А второе имеет вид
∮
(
)
1
1
(1 - u)-2
1 - 2uN + u2N
B=
du.
C2
2πi
ub-1
N+1
|u|=ρ
Далее получаем
∮
(
)
1
(1 - u)-2
1 - 2uN + u2N
du =
2πi
ub-1
|u|=ρ
∮
∮
∮
1
(1 - u)-2
1
(1 - u)-2
1
(1 - u)-2
=
du +
du +
du =
2πi
ub-1
2πi
ub-N
2πi
ub-2N-1
|u|=ρ
|u|=ρ
|u|=ρ
= (-1)b-2C-2b-2 + 2(-1)b-N-2C-2b-N-2 + (-1)b-2N-2C-2b-2N-2 =
= Cb-22+b-2-1 + 2Cb-N-22+b-N-2-1 + Cb-2N-22+b-2N-2-1 =
= Cb-2b-1 + 2Cb-N-2b-N-1 + Cb-2N-2b-2N-1 =
= (b - 1) - 2C1b-N-1 + C1b-2N-1 = 0.
Окончательно имеем:
2
N
2N
2N
tb =
δb +
+
δb-N .
C2N+1
C2N+1
C2
N+1
Рассмотрим теперь случай N = 2 при произвольном количестве пере-
∑n
менных. Пусть, как обычно, ∥x∥ =
xi. В рассматриваемом случае b
i=1
∑p
∑n
можно представить в виде b =
xi + 2
xi. Очевидно, что b ≤ p+
i=1
i=p+1
+ 2(n - p) = 2n - p.
Утверждение 2. При N = 2 справедливо соотношение
∑
1
(18)
tb =
CknCb-kk2n-k.
n+1
k=0
162
Доказательство. В рассматриваемом случае из (17) имеем
(
)n
(
)n
∮
∮
N+u-uN+1
2+u-u3
1
1
1-u
1
1
1-u
tb =
du =
du =
Cn
2πi
ub+1
Cn
2πi
ub+1
n+N-1
n+1
|u|=ρ
|u|=ρ
∑
∮
∮
Cknuk(1+u)k2n-k
1
1
(2 + u(1 + u))n
1
1
k=0
=
du =
du =
n+1 2πi
ub+1
n+1 2πi
ub+1
|u|=ρ
|u|=ρ
∮
∑
∑
1
1
uk(1 + u)k
1
=
Ckn2n-k
du =
CknCb-kk2n-k,
n+1
2πi
ub+1
n+1
k=0
k=0
|u|=ρ
где b/2 ≤ k ≤ b.
Утверждение 2 доказано.
Пример 12. Пусть N = 2, n = 3. Из (12) имеем
∑
∑
1
1
tb =
CknCb-kk2n-k =
Ck3Cb-kk23-k.
n+1
4
k=0
k=0
Отсюда получаем
1
1
t1 =
(2 + 3 + 1 + 0) = 3/2, t2 =
(2 + 3 + 2 + 3) = 5/2,
4
4
1
1
1
1
t3 =
(2 + 1 + 2 + 0) = 5/4, t4 =
(1 + 0 + 1 + 3) = 5/4, t5 =
,
t6 =
4
4
4
4
Видно, что максимальное значение достигается при b = 2.
3. О некоторых свойствах множества L∗
3.1. Структура множества L∗
Следуя обозначениям и определениям, введенным ранее, напомним, что
∑n
множество значений линейной формы L(x1, . . . , xn) =
aixi (сама эта
i=1
форма, если это не вызывает неопределенности, обозначается через L(x) или
даже через L) обозначено через L∗(a1, . . . , an) (или просто через L∗).
Уравнение L(x) = b разрешимо тогда и только тогда, когда b ∈ L∗. В свя-
зи с этим актуальной задачей является исследование структуры и свойств
множества L∗.
Очевидно следующее утверждение.
Утверждение 3. Справедливо соотношение
{
}
∑
|L∗| ≤ min
2n
,1+
ai
i=1
163
Следствие 4. Если ai ≤ N, i = 1,...,n, то |L∗| ≤ min{2n,1 + nN}.
∑n
[
]
Лемма 6. Если L(x) =
ixi, то L∗ =
0, C2n+1
i=1
Эта лемма следует из того факта, доказанного в [12], что при L(x) =
∑n
=
ixi форма L(x) принимает на булевом кубе все значения от нуля до
∑n
i=1
i=C2n+1.
i=1
3.2. Множества L∗ и сложение по Минковскому
Определение 2. Пусть M1 и M2 - два множества из натуральных
чисел. Их суммой по Минковскому называется множество M = M1 ⊕ M2 =
= {a + b, a ∈ M1, b ∈ M2}.
Пример 13. Если Z2n - множество всех четных чисел, а M = {0,1}, то
Z2n ⊕ M - весь натуральный ряд.
Пример 14. Сумма по Минковскому двух отрезков натурального ряда -
это отрезок натурального ряда: [a, b] ⊕ [c, d] = [a + b, c + d].
Обозначим через PL множество переменных формы L(x1, . . . , xn), т.е. PL =
= {x1, . . . , xn}.
Лемма 7. Если PL1 ∩ PL2 = ∅, то (L1 + L2)∗ = L∗1 ⊕ L∗2.
Доказательство. По определению
∗
∑
∑
(L1 + L2) ∗ = aixi +
aixi
= {ai + aj, 1 ≤ i ≤ p, p + 1 ≤ j ≤ q} .
i=1
i=p+1
Далее замечаем, что {ai + aj , 1 ≤ i ≤ p, p + 1 ≤ j ≤ q} = L∗1 ⊕ L∗2.
Лемма 7 доказана.
Приведем некоторые соотношения, связывающие обычное сложение ли-
нейных форм, сложение по Минковскому и стандартные теоретико-множе-
ственные операции.
∑
∑
1.
(L1 + L2) = (ai + ai)xi =
cixi.
i=1
i=1
{
}
∑
2. L∗ =
aixi,x∈Bn
i=1
3. A ⊕ B = {a + b, a ∈ A, b ∈ B} .
4.
(L1 + L2) ∗ = L∗1 ⊕ L∗2 при PL1 ∩ PL2 = ∅.
∑
∑
5. Если L1(x1, . . . , xn) =
aixi, L2 = an+1xn+1 и an+1 ≤
ai,
i=1
i=1
[
]
[
]
∑
∑
аL∗
= 0, ai , то (L1 + L2)∗
= 0, ai
1
i=1
i=1
164
3.3. Непрерывные линейные формы
Рассмотрим один специальный класс линейных форм.
∑n
Определение 3. Форма L(x1,...,xn) =
aixi называется непре-
∑n
i=1
рывной, если L∗ = [0,
ai].
i=1
Таким образом, непрерывная форма принимает все значения от минималь-
но возможного до максимального. (Напоминаем, что переменные булевы, а
коэффициенты - целые положительные числа.) Впервые данное определение
было введено в [14].
Пример 15. Следующие классы функций являются непрерывными:
∑
1. L(x) =
xi;
i=1
∑
2. L(x) =
ixi;
i=1
∑
3. L(x) =
xi2i-1;
i=1
∑
4. L(x) =
xi + nxn;
i=1
∑
5. L(x) =
2xi + x1.
i=2
При n = 2 существует всего две непрерывные формы: L1 = x1 + x2; L2 =
= x1 + 2x2.
При n = 3 существует пять непрерывных форм: L1 = x1 + x2 + x3, L2 =
= x1 + x2 + 2x3, L3 = x1 + 2x2 + 2x3, L4 = x1 + 2x2 + 3x3, L5 = x1 + 22 + 4x3.
Для n = 4 таких форм уже 13: L1 = x1 + x2 + x3 + x4, L2 = x1 + x2 +
+x3 + 2x4, L3 = x1 + x2 + 2x3 + 2x4, L4 = x1 + 2x2 + 2x3 + 2x4, L5 = x1 +
+ 2x2 + 2x3 + 3x4, L6 = x1 + x2 + x3 + 3x4, L7 = x1 + x2 + 3x3 + 3x4, L8 =
= x1 + 2x2 + 3x3 + 3x4, L9 = x1 + 2x2 + 3x3 + 4x4, L10 = x1 + 2x2 + 4x3 +
+ 4x4, L11 = x1 + x2 + 2x3 + 5x4, L12 = x1 + x2 + 3x3 + 5x4, L13 = x1 + 3x2 +
+ 3x3 + 5x4.
Важность и актуальность проверки линейной формы на непрерывность
объясняется следующим их свойством. Решение системы булевых уравнений,
левые части которых образованы непрерывными линейными формами, ста-
новится простой задачей. Достаточно для каждого уравнения взять правую
∑n
∑n
часть b и сравнить с
ai в правой части. Если b ≤
ai, то уравнение
i=1
∑1
n
разрешимо, например, на единичном векторе. А если b >
ai, то решения
i=1
оно не может иметь.
Замечание 1. Сумма непрерывных функций не обязана быть непрерыв-
ной.
165
Пример 16. Функции L1 = x1 + x2 и L2 = x1 + 2x2 являются непрерыв-
ными, а их сумма L3 = 2x1 + 3x2 не является непрерывной (она не принимает
значений 1 и 4).
Однако если это функции от разных переменных, то справедливо утверж-
дение.
Утверждение 4. Если L1 и L2 - две непрерывные линейные формы, за-
висящие от разных переменных, то форма L1 + L2 является непрерывной.
Доказательство. Так как L1 и L2 - непрерывны, то L∗1 = [0,a], L∗2 =
= [0, b] для некоторых a и b. Из леммы 7 следует: [L1 + L2]∗ = L∗1 ⊕ L∗2 =
= [0, a] ⊕ [0, b] = [0, a + b].
Утверждение 4 доказано.
∑n
Утверждение 5. Если форма L =
aixi является непрерывной и
∑
k-1
L = 0, то справедливы соотношения: ak ≤
ai + 1, k = 2,3,... ,n.
i=1
∑n
Доказательство. Так как выполняется (9), L = 0 и L∗ = [0,
ai],
i=1
то a1 = 1 в силу того, что 1 ∈ L∗. Далее берем минимальное k > 1 такое, что
∑n
ak = 0. Вновь в силу (9) имеем ak ≤ 2, так как L∗ = [0,
ai] и 2 ∈ L∗. И
i=1
так для всех k = 2, 3, . . . , n.
Утверждение 5 доказано.
∑n
Пусть теперь L =
aixi и все ai ≤ N, i = 1,... ,n. Обозначим множе-
i=1
ство таких форм через L(n, N) и пусть l(n, N) = maxL(n,N) |L∗|.
Значение l(n, N)и его оценки могут представлять интерес при оценке ка-
чества переборных алгоритмов.
Тогда справедливо следующее соотношение.
Теорема 2. Если N = n, то
l(n, N) ∼ n2.
Доказательство. Для доказательства получим верхнюю и нижнюю
границу этой асимптотики, а из их равенства установим утверждение теоре-
мы. Верхняя граница здесь очевидна и имеет вид
{
}
(19)
l(n, n) ≤ min
2n, n2
=n2.
Для получения нижней оценки рассмотрим линейную форму специального
вида
∑
∑
L = x1 + ix + n
xi.
i=2
i=m+1
Здесь m - некоторый параметр. Теперь выберем m из условия:
C2m+1 ≥ n.
166
∑m
[
]
Отсюда следует, что L∗ (x1 +
ix) =
0, C2m+1
, а с учетом вида вы-
i=2
бранной линейной формы начинаем добавлять слагаемые. При добавлении
первого слагаемого получаем:
(
)
∑
[
]
L∗
x1 + ix + nxm+1
=
0, n + C2m+1
i=1
И далее, продолжая добавлять слагаемые, имеем:
(
)
∑
∑
[
]
L∗
x1 + ixi + n
xi
=
0, n(n - m) + C2m+1
i=2
i=m+1
Из этого равенства видно, что для завершения доказательства теоремы 2
√
требуется выбрать параметр m ∼
2n. При таком выборе мощность множе-
ства значений линейной формы удовлетворяет соотношению:
(
)
∑
∑
(20)
L∗ x1 + ixi + n
xi
∼n2.
i=2
i=m+1
Из (19) и (20) следует утверждение теоремы.
Теорема 2 доказана.
Замечание 2. Для доказательства нижней оценки в теореме использо-
валась линейная форма достаточно специального вида, поэтому на практике,
видимо, следует ожидать для |L∗| значений существенно меньших. Вопрос же
о среднем значении этой величины - отдельная задача теории чисел.
4. Заключение
В статье рассмотрены вопросы, связанные с разрешимостью систем буле-
вых уравнений. Даны формулы и оценки числа допустимых решений систе-
мы в зависимости от значения правых частей уравнений. Эта часть работы
использует метод производящих функций и является продолжением преды-
дущих исследований авторов.
Рассмотрен один частный случай систем, когда уравнения ограничений
задаются так называемыми непрерывными линейными формами.
Результаты могут представлять интерес для конструирования приклад-
ных алгоритмов в различных областях дискретной оптимизации и исследо-
вания операций, а также в распознавании образов, криптографии и системах
защиты информации.
СПИСОК ЛИТЕРАТУРЫ
1. Пападимитриу Х., Стайглиц С. Комбинаторная оптимизация. М.: Мир, 1989.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:
Мир, 1982.
167
3.
Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир,
1991.
4.
Леонтьев В.К., Гордеев Э.Н. Производящие функции в задаче о ранце // ДАН.
5.
Леонтьев В.К., Гордеев Э.Н. О некоторых комбинаторных свойствах задачи о
рюкзаке // Журн. вычисл. матем. и матем. физ. 2019. Т. 59. № 8. С. 1439-1447.
6.
Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin: Springer, 2004.
7.
Леонтьев В.К., Тоноян Г.П. Приближенные решения систем булевых уравне-
ний // Журн. вычисл. матем. и матем. физ. 1993. Т. 33. № 9. С. 1383-1390.
8.
Леонтьев В.К., Тоноян Г.П. О системах булевых уравнений // Журн. вычисл.
матем. и матем. физ. 2013. Т. 53. № 5. С. 109-116.
9.
Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений.
М.: МФТИ, 2007.
10.
Леонтьев В.К., Гордеев Э.Н. Об алгебраической иммунности систем кодирова-
ния // Вопросы кибербезопасности. 2019. № 1. С. 59-89.
11.
Гордеев Э.Н., Леонтьев В.К., Медведев Н.В. О свойствах булевых полино-
мов, актуальных для криптосистем // Вопросы кибербезопасности. 2017. № 3.
12.
Мазуров И.Д., Хачай М.Ю. Комитеты систем линейных неравенств // АиТ.
2004. № 2. С. 43-54.
Mazurov V.D., Khachai M.Yu. Committees of Systems of Linear Inequalities //
Autom. Remote Control. 2004. V. 65. No. 2. P. 193-203.
13.
Береснев В.Л. Эффективный алгоритм решения задачи минимизации полино-
мов от булевых переменных, обладающих свойством связности // Дискретн.
анализ и исслед. операций. Сер. 2. 2005. Т. 12. № 1. С. 3-11.
14.
Леонтьев В.К. О псевдобулевых полиномах // Журн. вычисл. матем. и матем.
15.
Леонтьев В.К. Комбинаторика и информация. Ч. 1. Комбинаторный анализ.
М.: МФТИ, 2015.
16.
Леонтьев В.К. Комбинаторика и информация. Ч. 2. Информационные модели.
М.: МФТИ, 2015.
Статья представлена к публикации членом редколлегии Д.Е. Пальчуновым.
Поступила в редакцию 12.01.2021
После доработки 01.03.2021
Принята к публикации 16.03.2021
168
