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

УДК 519.1+519.7

Поттосин, Ю. В. Комбинаторные задачи в логическом проектировании 
дискретных устройств / Ю. В. Поттосин ; Нац. акад. наук Беларуси, Объед. 
ин-т проблем информатики. – Минск : Беларуская навука, 2021. – 175 с. : ил. 
ISBN 978-985-08-2725-8.

В монографии рассматриваются оптимизационные комбинаторные задачи дискретной 
математики, возникающие при логическом проектировании дискретных устройств и систем. 
Представлены методы решения таких задач, как поиск кратчайшего покрытия множества, 
раскраска графа и др. Описаны классические методы минимизации и декомпозиции булевых 
функций в терминах булевых и троичных векторов и матриц. Изложены методы проектирования дискретных устройств, использующие классические модели конечного автомата и параллельного автомата.
Адресуется специалистам в области автоматизации проектирования дискретных устройств, а также студентам, магистрантам и аспирантам, специализирующимся в данном направлении.
Табл. 56. Ил. 44. Библиогр. 34 назв.

Рекомендовано Ученым советом  
ГНУ «Объединенный институт проблем информатики  
Национальной академии наук Беларуси» 
(протокол от 18 апреля 2019 г. № 4)

Р е ц е н з е н т ы:

доктор технических наук, профессор П. Н. Бибило,
доктор технических наук, профессор В. В. Голенков

ISBN 978-985-08-2725-8 
© Поттосин Ю. В., 2021
© ГНУ «Объединенный институт проблем 
информатики НАН Беларуси», 2021
© Оформление. РУП «Издательский дом 
«Беларуская навука», 2021

СОДЕРЖАНИЕ

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
5

Глава 1. Комбинаторные задачи и методы комбинаторного поиска . . . . . . . . . . . . . .  
6

1.1. Особенности комбинаторных задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
6
1.2. Задача о кратчайшем покрытии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
9
1.3. Основные понятия теории графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
13
1.4. Доминирующие множества графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
17
1.5. Независимые множества графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
18
1.6. Раскраска графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
23
1.7. Разрез графа  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
27
1.8. Полные двудольные подграфы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
30

Глава 2. Булевы функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
37

2.1. Способы задания булевой функции  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
37
2.2. Элементарные булевы функции и алгебраические формы . . . . . . . . . . . . . . . . .  
39
2.3. Интерпретации булевой алгебры  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
42
2.4. Выполнение операций над булевыми функциями с помощью характеристических множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
45
2.5. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
45
2.6. Троичные векторы и матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
48
2.7. Ортогонализация дизъюнктивной нормальной формы . . . . . . . . . . . . . . . . . . . .  
50
2.8. Графическое представление булева пространства. Карта Карно . . . . . . . . . . . .  
55
2.9. Функциональная полнота . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
59
2.10. Минимизация дизъюнктивной нормальной формы . . . . . . . . . . . . . . . . . . . . . .  
60
2.11. Минимизация не полностью определенных булевых функций  . . . . . . . . . . . .  
70

Глава 3. Системы булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
75

3.1. Представления системы булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
75
3.2. Минимизация системы ДНФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
77

Глава 4. Декомпозиция булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
84

4.1. Двухблочная разделительная декомпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
84
4.2. Неразделительная декомпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
88
4.3. Декомпозиция систем булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
90
4.4. Многоблочная параллельная декомпозиция системы не полностью определенных булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
93

Глава 5. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
104

5.1. Типы автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
104
5.2. Минимизация полных автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
109
5.3. Минимизация частичных автоматов  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
114

Глава 6. Кодирование состояний синхронного автомата . . . . . . . . . . . . . . . . . . . . . . . .  
127

6.1. Задача кодирования состояний  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
127
6.2. Метод «желательных соседств»  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
129
6.3. Итеративный метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
136
6.4. Энергосберегающее кодирование состояний  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
141

Глава 7. Кодирование состояний асинхронного автомата . . . . . . . . . . . . . . . . . . . . . . .  
148

7.1. Явление состязаний элементов памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
148
7.2. Условие отсутствия опасных состязаний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
149
7.3. Минимизация длины кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
151
7.4. Энергосберегающее кодирование состояний. . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
154

Глава 8. Параллельные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
160

8.1. Описание модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
160
8.2. Установление параллельности частичных состояний . . . . . . . . . . . . . . . . . . . . .  
161
8.3. Кодирование частичных состояний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
163

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
168

Список использованных источников  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
169

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
171

ПРЕДИСЛОВИЕ

В предлагаемой монографии рассматриваются задачи дискретной математики, возникающие при логическом проектировании цифровых устройств 
и систем. Описываются методы решения этих задач. Данный этап проектирования охватывает наиболее широкий спектр задач, поддающихся строгой 
математической формулировке. Предполагается, что читатель знаком с основными понятиями множеств, графов и отношений. В терминах этих понятий 
ведется дальнейшее изложение, которое начинается с описания методов решения таких задач комбинаторной оптимизации, как поиск кратчайшего покрытия множества, раскраска графа и др.
Описаны классические методы минимизации булевых функций и систем 
булевых функций в терминах булевых и троичных векторов и матриц. Рассмотрены также задачи декомпозиции булевых функций.
Изложены методы проектирования цифровых устройств, использующие 
классические модели конечного автомата. Детально рассматривается задача 
минимизации числа состояний полных и частичных автоматов. Описаны методы кодирования состояний автомата при синхронной и асинхронной реализации, в том числе методы, обеспечивающие уменьшение энергопотребления 
проектируемого устройства.
Многие из описанных подходов разработаны в лаборатории логического 
проектирования Объединенного института проблем информатики Национальной академии наук Беларуси. Использованы материалы, изложенные 
в монографиях, список которых приведен в конце книги.

Глава 1

КОМБИНАТОРНЫЕ ЗАДАЧИ И МЕТОДЫ  
КОМБИНАТОРНОГО ПОИСКА

1.1. Особенности комбинаторных задач

Решением оптимизационной комбинаторной задачи является некоторый 
объект, обладающий оптимальным значением определенного параметра. Таким объектом может быть множество, матрица, определенного вида форма 
функции.
В отличие от задач традиционной математики, где решение получается 
с помощью целенаправленной вычислительной процедуры, однозначно ведущей к цели, решение комбинаторной задачи зачастую сводится к полному 
перебору различных вариантов. Перебираются и испытываются результаты 
построений определенного вида, среди которых должно находиться решение 
задачи. Как только выясняется, что очередной результат является решением, 
процесс поиска решения можно считать завершенным.
В традиционной математике трудоемкость задачи обычно не очень сильно 
зависит от размера области возможных решений, в то время как для комбинаторных задач эта зависимость весьма велика.
Комбинаторные задачи характерны еще тем, что множество, среди элементов которого отыскивается решение, всегда конечно. Реализовав полный перебор, либо найдем решение, либо убедимся в том, что его нет. Таким образом, 
всякая подобная задача может быть решена за конечное время. Однако это не 
значит, что она может быть решена за практически приемлемое время даже 
с помощью самой быстродействующей вычислительной машины.
Трудоемкость алгоритма, или временнáя сложность, т. е. время, затрачиваемое на выполнение алгоритма, оценивается числом условных элементарных 
операций, которые необходимо выполнить при решении задачи. Естественно, 
эта величина зависит от объема исходных данных, который оценивается некоторым параметром. Например, для графа это может быть число вершин или 
число ребер. Трудоемкость алгоритма, таким образом, можно оценить некоторой функцией f(n), где п – натуральное число, выражающее объем исходных 
данных. 
Принято писать ( )
(
)
 
( ) ,
 
f n
O g n
=
 где g(n) - некоторая конкретная функция 
от n, если найдется такая константа с, что f(n) ≤ сg(n) для любого n ≥ 0. При 
этом употребляют следующие выражения: «трудоемкость алгоритма есть 

(
)
( )
O g n » или «алгоритм решает задачу за время (
)
( )
O g n ». Если трудоемкость 

не зависит от объема исходных данных, то для ее обозначения используется символ О(1). Алгоритм трудоемкости О(п) называют линейным. Алгоритм 
трудоемкости О(пb), где b – константа (возможно, дробная), называется полиномиальным. Если g(n) является показательной функцией, например 2п, то 
говорят, что алгоритм обладает неполиномиальной, или экспоненциальной, 
сложностью.
Оценка трудоемкости алгоритма позволяет судить о том, как влияет быстродействие вычислительной машины на время выполнения алгоритма. Пусть 
имеется пять алгоритмов, трудоемкость которых соответственно п, n logn, п2, п3 
и 2п. Пусть условная элементарная операция, которая является единицей измерения трудоемкости алгоритма, выполняется за одну миллисекунду. В табл. 1.1  
(источник [4, с. 13]) показано, какого размера задачи могут быть решены каждым из этих алгоритмов за одну секунду, одну минуту и один час. Из этой 
таблицы видно, например, что за одну минуту алгоритм с трудоемкостью п2 
решает задачу в шесть раз большую, чем алгоритм с трудоемкостью п3.
Следует, однако, иметь в виду, что трудоемкость, выражаемая большей 
степенью полинома, может иметь меньший множитель с из приведенного выше неравенства f(n) ≤ сg(n). Точно так же сложность алгоритма, которая носит 
экспоненциальный характер, может иметь множитель, меньший, чем у полиномиальной сложности. При разработке компьютерных программ для решения практических задач важно знать, при каких значениях параметра п время 
выполнения экспоненциального алгоритма оказывается меньше, чем время 
выполнения полиномиального алгоритма, решающего ту же задачу.

Таблица 1.1. Связь трудоемкости алгоритма с максимальным  
размером задачи, решаемой за единицу времени

Временнáя
сложность
Максимальный размер задачи

1 с
1 мин
1 ч
п
1000
6 ⋅ 104
3,6 ⋅ 106

п logn
140
4893
2,0 ⋅ 105

n2
31
244
1897
n3
10
39
153
2n
9
15
21

Для очень многих практических комбинаторных задач существуют алгоритмы только экспоненциальной трудоемкости. Может показаться, что с совершенствованием вычислительной техники и ростом быстродействия вычислительных машин проблема трудоемкости ослабевает. Однако данные, приведенные в табл. 1.2 [4, с. 13], свидетельствуют, что это не так. Пусть следующее 
поколение вычислительных машин будет иметь быстродействие, в десять раз 
большее, чем у современных. В табл. 1.2 показано, как благодаря увеличению быстродействия возрастут размеры задач, которые могут быть решены 
за некоторую фиксированную единицу времени. Задачи достаточно большого размера, решаемые только алгоритмами экспоненциальной трудоемкости, 

вообще не могут быть решены за практически приемлемое время, даже если 
надеяться на существенное увеличение быстродействия вычислительных машин в будущем.
Иногда удается найти способы сокращения перебора благодаря некоторым 
особенностям конкретных исходных данных.
Другой путь выхода из такого положения – использование так называемых эвристических методов. Для практических задач не всегда требуется 
получать точное решение. Часто достаточно иметь решение, близкое к оптимальному. Эвристический метод не осуществляет полного перебора вариантов, а в многошаговом процессе решения задачи на каждом шаге выбирает 
вариант по каким-либо разумным соображениям.

Таблица 1.2. Связь размера задачи, решаемой за заданное время,  
с быстродействием вычислительной машины

Временнáя
сложность
Максимальный размер задачи

до ускорения
после ускорения
п
s1
10 s1
п logn
s2
≈10 s2
n2
s3
3,16 s3
n3
s4
2,15 s4
2n
s5
s5 + 3,3

Один из наиболее общих и плодотворных подходов к решению комбинаторных задач заключается в применении дерева поиска. В дереве выделяется 
вершина, которая называется корнем дерева и ставится в соответствие исходной ситуации в процессе решения задачи. Остальные вершины сопоставляются с ситуациями, которые можно достичь в данном процессе. Выделение 
корня придает дереву ориентацию, при которой все пути ведут из корня 
в остальные вершины. Движение по ветви дерева соответствует выполнению 
последовательности некоторых операций, переводящих процесс решения из 
одной ситуации в другую. Для ситуации характерно разнообразие вариантов 
выбора очередного шага, представленных ветвями, исходящими из соответствующей вершины. Некоторые ситуации соответствуют решениям.
Дерево поиска не задается априори, а строится в процессе поиска: когда 
возникает некоторая ситуация, тогда и определяются возможные направления 
процесса, которые представляются исходящими из вершины ветвями. Естественным является стремление сокращать число этих ветвей, чтобы быстрее 
найти решение. Способы этого сокращения строятся с учетом особенностей 
конкретных задач.
Довольно общим средством повышения эффективности процесса решения 
задачи является редуцирование, т. е. упрощение текущей ситуации, сокращающее объем вычислений, проводимых при анализе множества вытекающих 
из нее вариантов. Способы редуцирования определяются особенностями конкретной задачи и исходных данных.

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

1.2. Задача о кратчайшем покрытии

Многие комбинаторные оптимизационные задачи сводятся к задаче 
о кратчайшем покрытии, которая ставится следующим образом. Пусть даны некоторое множество А = {a1, a2, … , an} и совокупность его подмножеств 
В1, В2, … , Вт, т. е. Bi ⊆ A, i = 1, 2, … , m, причем В1 ∪ В2 ∪ … ∪ Вт = А. Требуется среди данных подмножеств выделить такую совокупность 
1
2
,
,... ,
k
i
i
i
B
B
B  
с минимальным k, чтобы каждый элемент из А попал хотя бы в одно из 
ji
B  
(j = 1, 2, …, k), т. е. 
1
2
...
.
k
i
i
i
B
B
B
A
∪
∪
∪
=

Одной из интерпретаций этой задачи является задача о переводчиках. Из 
некоторого коллектива переводчиков, число которых т и каждый из которых 
владеет несколькими определенными языками, требуется скомплектовать 
минимальную по числу членов группу, такую, чтобы она смогла обеспечить 
перевод с любого из заданного множества языков, число которых п. Здесь А – 
множество языков, перевод с которых требуется обеспечить, а Вi – множество 
языков, которыми владеет i-й переводчик.
Удобно рассматривать матричную формулировку данной задачи, при которой совокупность В1, В2, …, Вт задается в виде двоичной (булевой) матрицы, строки которой соответствуют подмножествам из данной совокупности, 
а столбцы – элементам множества А. Элемент i-й строки и j-го столбца имеет значение 1, если aj ∈ Bi, и значение 0, если aj ∉ Bi. В этом случае говорят, что i-я строка покрывает j-й столбец. Требуется найти такое множество 
строк данной матрицы, чтобы каждый ее столбец имел единицу хотя бы в одной строке из этого множества, и при этом мощность выбранного множества 
должна быть минимальной.
Существуют эвристические методы решения данной задачи. Например, 
ее можно решать с помощью «жадного» алгоритма, представляющего собой 
многошаговый процесс, где на каждом шаге выбирается и включается в покрытие строка заданной матрицы, покрывающая наибольшее число из еще не 
покрытых столбцов. Этот процесс заканчивается, когда все столбцы матрицы 
оказываются покрытыми. Применение жадного алгоритма иногда дает точное 
решение, но гарантии этому нет. Например, если задана матрица

1
2
3
4
5
6

1

2

3

1
1
1
1
0
0
,
1
1
0
0
1
0

0
0
1
1
0
1












а
а
а
а
а
а

В
В

В

первой для включения в формируемое решение жадный алгоритм выберет 
строку В1, после чего для покрытия оставшихся столбцов должны быть включены в решение обе строки В2 и В3. Кратчайшее же покрытие данной матрицы 
составляют только две строки – В2 и В3.
Более близкое к кратчайшему покрытие получается чаще всего с помощью 
«минимаксного» алгоритма. Он представляет собой многошаговый процесс, 
на каждом шаге которого выбирается столбец с минимальным числом единиц, и из покрывающих его строк для включения в решение выбирается та, 
которая покрывает максимальное число непокрытых столбцов. Пусть, например, задана матрица

1
2
3
4
5
6
7
8
9
10

1

2

3

4

5

6

7

8

9

1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0

0
1
1
0
1
0
0
1
0
0

0
0
1
1
0
0
0
1
0
1
.
0
0
0
1
0
0
1
0
0
0

1
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0

1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1






























а
а
а
а
а
а
а
а
а
а

В
В

В

В
В

В
В

В
В

Одним из столбцов с минимальным числом единиц является столбец а6. 
Из покрывающих его строк максимальное число столбцов покрывает строка В6. Включим эту строку в решение и удалим ее и столбцы, которые она 
покрывает, в результате чего получим

2
4
5
7
8
10

1

2

3

4

5

7

8

9

0
1
0
0
1
0
1
0
0
1
0
0

1
0
1
0
1
0
.
0
1
0
0
1
1

0
1
0
1
0
0
1
0
1
1
0
0

0
0
1
0
1
0
0
0
1
1
0
1




























а
а
а
а
а
а

В
В

В
В

В
В

В
В

Из оставшихся столбцов минимальное число единиц имеет столбец а10. 
Покрывающие его строки В4 и В9 имеют одинаковое число единиц, т. е. оди