КулЛиб - Классная библиотека! Скачать книги бесплатно
Всего книг - 706108 томов
Объем библиотеки - 1347 Гб.
Всего авторов - 272715
Пользователей - 124644

Новое на форуме

Новое в блогах

Впечатления

medicus про Федотов: Ну, привет, медведь! (Попаданцы)

По аннотации сложилось впечатление, что это очередная писанина про аристократа, написанная рукой дегенерата.

cit anno: "...офигевшая в край родня [...] не будь я барон Буровин!".

Барон. "Офигевшая" родня. Не охамевшая, не обнаглевшая, не осмелевшая, не распустившаяся... Они же там, поди, имения, фабрики и миллионы делят, а не полторашку "Жигулёвского" на кухне "хрущёвки". Но хочется, хочется глянуть внутрь, вдруг всё не так плохо.

Итак: главный

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
Dima1988 про Турчинов: Казка про Добромола (Юмористическая проза)

А продовження буде ?

Рейтинг: -1 ( 0 за, 1 против).
Colourban про Невзоров: Искусство оскорблять (Публицистика)

Автор просто восхитительная гнида. Даже слушая перлы Валерии Ильиничны Новодворской я такой мерзости и представить не мог. И дело, естественно, не в том, как автор определяет Путина, это личное мнение автора, на которое он, безусловно, имеет право. Дело в том, какие миазмы автор выдаёт о своей родине, то есть стране, где он родился, вырос, получил образование и благополучно прожил всё своё сытое, но, как вдруг выясняется, абсолютно

  подробнее ...

Рейтинг: +2 ( 3 за, 1 против).
DXBCKT про Гончарова: Тень за троном (Альтернативная история)

Обычно я стараюсь никогда не «копировать» одних впечатлений сразу о нескольких томах (ибо мелкие отличия все же не могут «не иметь место»), однако в отношении части четвертой (и пятой) я намерен поступить именно так))

По сути — что четвертая, что пятая часть, это некий «финал пьесы», в котором слелись как многочисленные дворцовые интриги (тайны, заговоры, перевороты и пр), так и вся «геополитика» в целом...

Сразу скажу — я

  подробнее ...

Рейтинг: +1 ( 1 за, 0 против).
DXBCKT про Гончарова: Азъ есмь Софья. Государыня (Героическая фантастика)

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

С одной стороны — о покупке данной части я все же не пожалел (ибо фактически) - это как раз была последняя часть, где «помимо всей пьесы А.И» раскрыта тема именно

  подробнее ...

Рейтинг: +1 ( 1 за, 0 против).

Дисконтная математика для программистов [Ф. А. Новиков] (pdf) читать онлайн

Книга в формате pdf! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]

УЧЕБНИК

й
ДЛЯ ВУЗОВ

Ф. А. Новиков

ДИСКРЕТНАЯ
МАТЕМАТИКА
ДЛЯ ПРОГРАММИСТОВ

3-е издание
Допущено Министерством образования и науки Российской Федерации
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по направлению подготовки дипломированных
специалистов «Информатика и вычислительная техника»

С^ППТЕР
Москва • Санкт-Петербург • Нижний Новгород • Воронеж
Ростов-на-Дону • Екатеринбург • Самара • Новосибирск
Киев • Харьков • Минск

2009

ББК 22.174я7
УДК 519.1(075) .
* Н73

Рецензенты:
Кафедра прикладной математики
Санкт-Петербургского государственного технического университета
С. С. Лавров], доктор технических наук, профессор,
член-корреспондент Российской академии наук

Новиков Ф. А.
Н 7 3 Д и с к р е т н а я м а т е м а т и к а д л я п р о г р а м м и с т о в : У ч е б н и к д л я вузов. 3 - е изд.
СПб.: Питер, 2009. —

3 8 4 е.: и л . —



(Серия «Учебник д л я вузов»),

ISBN 978-5-91180-759-7
В учебнике изложены основные разделы дискретной математики и описаны важнейшие алгоритмы
на дискретных структурах данных. Основу книги составляет материал лекционного курса, который автор
читает в Санкт-Петербургском государственном техническом университете последние полтора десятилетия. Третье издание имеет ту же структуру и последовательность изложения, что и второе. В книгу
внесено несколько десятков не очень объемных, но существенных добавлений, уточнений и определений.
Обновлены упражнения, библиография и комментарии к ней.
Для студентов вузов, практикующих программистов и всех желающих изучить дискретную
математику,
Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия
для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных
специалистов «Информатика и вычислительная техника»,

ББК 22,174я7
УДК 619,1(076)
Bee права защищены, Никакая чаоть данной книги на может быть воспроизведена в какой бы то ни было
форме без письменного разрешения владельцев авторских прав,
Информация, содержащаяся в данной книге, получена из источников, рассматриваемых издательством как
надежные, Тем не менее, имея в виду возможные человеческие или технические ошибки, иэдательотво не
может гарантировать абоолютную точнооть и полноту приводимых сведений и не неоет ответотвеннооти за
возможные ошибки, связанные с использованием книги,

ISBN078-B-91180-760-7

@ ООО «Питер Пресс», 2009

Краткое содержание
Предисловие к третьему изданию

12

Предисловие ко второму изданию

13

Вступительное слово к первому изданию

14

Введение

15

Глава 1 . Множества и отношения

23

Глава 2 . Алгебраические структуры

. \ . . 75

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

107

Глава 4 . Логические исчисления

142

Глава 5 . Комбинаторика

179

Глава 6 . Кодирование

208

Глава 7 . Графы

240

Глава 8 . Связность

265

Глава 9. Деревья

292

Глава 1 0 . Циклы, независимость и раскраска

333

Указатель основных обозначений

365

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

368

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

370

Содержание
Предисловие к третьему изданию

12

Предисловие ко второму изданию

13

Вступительное слово к первому изданию

14

Введение

15

Глава 1 . Множества и отношения

23

1.1. Множества
1.1.1. Элементы и множества
1.1.2. Задание множеств
1.1.3. Парадокс Рассела
1.1.4. Мультимножества
1.2. Алгебра подмножеств
1.2.1. Сравнение множеств
1.2.2. Равномощные множества
1.2.3. Конечные и бесконечные множества
1.2.4. Добавление и удаление элементов
1.2.5. Мощность конечного множества
1.2.6. Операции над множествами
1.2.7. Разбиения и покрытия
1.2.8. Булеан
1.2.9. Свойства операций над множествами
1.3. Представление множеств в программах
1.3.1. Битовые шкалы
1.3.2. Генерация всех подмножеств универсума
1.3.3. Алгоритм построения бинарного кода Грея
1.3.4. Представление множеств упорядоченными списками
1.3.5. Проверка включения слиянием
1.3.6. Вычисление объединения слиянием
1.3.7. Вычисление пересечения слиянием
1.3.8. Представление множеств итераторами
1.4. Отношения
1.4.1. Упорядоченные пары и наборы
1.4.2. Прямое произведение множеств
1.4.3. Бинарные отношения
1.4.4. Композиция отношений
1.4.5. Степень отношения
1.4.6. Свойства отношений

23
23
25
26
27
28
28
29
31
32
32
34
35
36
37
38
38
39
40
41
42
43
44
45
48
48
49
50
52
53
53

Содержание

5

1.4.7. Ядро отношения
1.4.8. Представление отношений в программах
1.5. Замыкание отношений
1.5.1. Транзитивное и рефлексивное замыкание
1.5.2. Алгоритм Уоршалла
1.6. Функции
1.6.1. Функциональные отношения
1.6.2. Инъекция, сюръекция и биекция
1.6.3. Образы и прообразы
1.6.4. Суперпозиция функций
1.6.5. Представление функций в программах
1.7. Отношения эквивалентности
1.7.1. Классы эквивалентности
1.7.2. Фактормножества
1.7.3. Ядро функционального отношения и множества уровня
1.8. Отношения порядка
1.8.1. Определения
1.8.2. Минимальные элементы
1.8.3. Алгоритм топологической сортировки
1.8.4. Верхние и нижние границы
1.8.5. Монотонные функции
1.8.6. Вполне упорядоченные множества
1.8.7. Индукция
1.8.8. Алфавит, слово и язык
Комментарии
Упражнения

55
56
57
57
58
59
59
61
62
63
63
64
64
66
66
67
67
68
69
70
70
71
72
73
73
74

Глава 2 . Алгебраические структуры
2.1. Алгебры и морфизмы
2.1.1. Операции и их носитель
2.1.2. Замыкания и подалгебры
2.1.3. Система образующих
2.1.4. Свойства операций
2.1.5. Гомоморфизмы
2.1.6. Изоморфизмы
2.2. Алгебры с одной операцией
2.2.1. Полугруппы
2.2.2. Определяющие соотношения
2.2.3. Моноиды
2.2.4. Группы
2.2.5. Группа перестановок
2.3. Алгебры с двумя операциями
2.3.1. Кольца
2.3.2. Области целостности
2.3.3. Поля
2.4. Векторные пространства и модули
2.4.1. Векторное пространство
2.4.2. Линейные комбинации
2.4.3. Базис и размерность
2.4.4. Модули
2.5. Решётки
2.5.1. Определения
2.5.2. Ограниченные решётки

75
75
75
76
77
78
79
80

81
81
82
84
85
87
88
88
89
90

91
91
93
94
95
96
96
97

6

Содержание

2.5.3. Решётка с дополнением
2.5.4. Частичный порядок в решётке
2.5.5. Булевы алгебры
2.6. Матроиды и жадные алгоритмы
2.6.1. Матроиды
2.6.2. Максимальные независимые подмножества
2.6.3. Базисы
2.6.4. Жадный алгоритм
2.6.5. Примеры матроидов
Комментарии
Упражнения

97
98
99
100
100
101
101
102
105
105
106

Глава 3 . Булевы функции
3.1. Элементарные булевы функции
3.1.1. Функции алгебры логики
3.1.2. Существенные и несущественные переменные
3.1.3. Булевы функции одной переменной
3.1.4. Булевы функции двух переменных
3.2. Формулы
3.2.1. Реализация функций формулами
3.2.2. Равносильные формулы
3.2.3. Подстановка и замена
3.2.4. Алгебра булевых функций
3.3. Двойственность
3.3.1. Двойственная функция
3.3.2. Реализация двойственной функции
3.3.3. Принцип двойственности
3.4. Нормальные формы
3.4.1. Разложение булевых функций по переменным
3.4.2. Совершенные нормальные формы
3.4.3. Эквивалентные преобразования
3.4.4. Минимальные дизъюнктивные формы
3.4.5. Геометрическая интерпретация
3.4.6. Сокращённые дизъюнктивные формы
3.5. Полнота
3.5.1. Замкнутые классы
3.5.2. Полные системы функций
3.5.3. Полнота двойственной системы
3.5.4. Теорема Поста
3.6. Представление булевых функций в программах
3.6.1. Табличные представления
3.6.2. Строковые представления
3.6.3. Алгоритм вычисления значения булевой функции
3.6.4. Деревья решений
Комментарии
Упражнения

107
107
107
109
110
110
111
111
114
115
116
118
118
118
119
120
120
121
123
124
125
126
128
128
130
131
131
133
133
135
136
137
140
140

Глава 4 . Логические исчисления
4.1. Логические связки
4.1.1. Высказывания
4.1.2. Формулы
4.1.3. Интерпретация
4.1.4. Логическое следование и логическая эквивалентность

142
143
143
144
144
145

Содержание

4.1.5. Подстановка и замена
4.2. Формальные теории
4.2.1. Определение формальной теории
4.2.2. Выводимость
4.2.3. Интерпретация
4.2.4. Общезначимость и непротиворечивость
4.2.5. Полнота, независимость и разрешимость
4.3. Исчисление высказываний
4.3.1. Классическое определение исчисления высказываний
4.3.2. Частный случай формулы
4.3.3. Алгоритм унификации
4.3.4. Конструктивное определение исчисления высказываний
4.3.5. Производные правила вывода
4.3.6. Дедукция
4.3.7. Некоторые теоремы исчисления высказываний
4.3.8. Множество теорем исчисления высказываний
4.3.9. Другие аксиоматизации исчисления высказываний
4.4. Исчисление предикатов
4.4.1. Определения
4.4.2. Интерпретация
4.4.3. Общезначимость
4.4.4. Непротиворечивость и полнота чистого исчисления предикатов
4.4.5. Логическое следование и логическая эквивалентность
4.4.6. Теория равенства
4.4.7. Формальная арифметика
4.4.8. Неаксиоматизируемые теории
4.4.9. Теоремы Гёделя о неполноте
4.5. Автоматическое доказательство теорем
4.5.1. Постановка задачи
4.5.2. Доказательство от противного
4.5.3. Сведёние к предложениям
4.5.4. Правило резолюции для исчисления высказываний
4.5.5. Правило резолюции для исчисления предикатов
4.5.6. Опровержение методом резолюций
4.5.7. Алгоритм метода резолюций
Комментарии
Упражнения
Глава 5 . Комбинаторика
5.1. Комбинаторные задачи
5.1.1. Комбинаторные конфигурации
5.1.2. Размещения
5.1.3. Размещения без повторений
5.1.4. Перестановки
5.1.5. Сочетания
5.1.6. Сочетания с повторениями
5.2. Перестановки
5.2.1. Графическое представление перестановок
5.2.2. Инверсии
5.2.3. Генерация перестановок
5.2.4. Двойные факториалы
5.3. Биномиальные коэффициенты
5.3.1. Элементарные тождества

7

147
147
147
148
149
149
150
150
150
151
152
153
153
154
156
159
160
161
161
163
164
165
166
167
168
168
170
171
171
172
173
174
175
175
176
177
178
179
180
180
180
181
182
182
183
184
184
•. .185
186
188
188
188

8

Содержание 8

5.3.2. Бином Ньютона
5.3.3. Свойства биномиальных коэффициентов
5.3.4. Треугольник Паскаля

189
190
191

5.3.5. Генерация подмножеств

192

5.3.6. Мультимножества и последовательности
193
5.3.7. Мультиномиальные коэффициенты
194
5.4. Разбиения
195
5.4.1. Определения
195
5.4.2. Числа Стирлинга второго рода
196
5.4.3. Числа Стирлинга первого рода
197
5.4.4. Число Белла
197
5.5. Включения и исключения
197
5.5.1. Объединение конфигураций
198
5.5.2. Формула включений и исключений
198
5.5.3. Число булевых функций, существенно зависящих от всех своих переменных . .200
5.6. Формулы обращения
200
5.6.1. Теорема обращения
200
5.6.2. Формулы обращения для биномиальных коэффициентов
201
5.6.3. Формулы для чисел Стирлинга
202
5.7. Производящие функции
203
5.7.1. Основная идея
203
5.7.2. Метод неопределённых коэффициентов
203
5.7.3. Числа Фибоначчи
204
5.7.4. Числа Каталана
205
Комментарии
207
Упражнения
207
Глава 6 . Кодирование
6.1. Алфавитное кодирование
6.1.1. Таблица кодов
6.1.2. Разделимые схемы
6.1.3. Префиксные схемы
6.1.4. Неравенство Макмиллана
6.2. Кодирование с минимальной избыточностью
6.2.1. Минимизация длины кода сообщения
6.2.2. Цена кодирования
6.2.3. Алгоритм Фано
6.2.4. Оптимальное кодирование
6.2.5. Алгоритм Хаффмена
6.3. Помехоустойчивое кодирование
6.3.1. Кодирование с исправлением ошибок
6.3.2. Возможность исправления всех ошибок
6.3.3. Кодовое расстояние
6.3.4. Код Хэмминга для исправления одного замещения
6.4. Сжатие данных
6.4.1. Сжатие текстов
6.4.2. Предварительное построение словаря
6.4.3. Алгоритм Лемпела-Зива
6.5. Шифрование
6.5.1. Криптография
6.5.2. Шифрование с помощью случайных чисел
6.5.3. Криптостойкость
6.5.4. Модулярная арифметика

208
210
210
210
211
211
214
214
215
216
217
219
221
221
223
224
225
227
227
228
229
231
231
232
233
233

Содержание

9

6.5.5. Шифрование с открытым ключом
6.5.6. Цифровая подпись
Комментарии
Упражнения

235
237
238
238

Глава 7 . Графы
7.1. Определения графов
7.1.1. История теории графов
7.1.2. Основное определение
7.1.3. Смежность
7.1.4. Диаграммы
7.1.5. Орграфы, псевдографы, мультиграфы и гиперграфы
7.1.6. Изоморфизм графов
7.2. Элементы графов
7.2.1. Подграфы
7.2.2. Валентность
7.2.3. Маршруты, цепи, циклы
7.2.4. Связность
7.2.5. Расстояние между вершинами, ярусы и диаметр графа
7.2.6. Эксцентриситет и центр
7.3. Виды графов и операции над графами
7.3.1. Виды графов
7.3.2. Двудольные графы
7.3.3. Направленные орграфы и сети
7.3.4. Операции над графами
7.4. Представление графов в программах
7.4.1. Требования к представлению графов
7.4.2. Матрица смежности
7.4.3. Матрица инциденций
7.4.4. Списки смежности
7.4.5. Массив дуг
7.4.6. Обходы графов
7.5. Орграфы и бинарные отношения
7.5.1. Графы и отношения
7.5.2. Достижимость и частичное упорядочение
7.5.3. Транзитивное замыкание
Комментарии
Упражнения

240
240
240
242
243
243
244
244
246
246
246
247
249
249
249
250
250
250
252
252
255
255
255
256
257
257
258
260
260
261
262
263
263

Глава 8 . Связность
8.1. Компоненты связности
8.1.1. Объединение графов и компоненты связности
8.1.2. Точки сочленения, мосты и блоки
8.1.3. Вершинная и рёберная связность
8.1.4. Оценка числа рёбер
8.2. Теорема Менгера
8.2.1. Непересекающиеся цепи и разделяющие множества
8.2.2. Теорема Менгера в «вершинной форме»
8.2.3. Варианты теоремы Менгера
8.3. Теорема Холла
8.3.1. Задача о свадьбах
8.3.2. Трансверсаль
8.3.3. Совершенное паросочетание

265
265
265
266
267
268
269
270
271
273
273
273
273
274

10

Содержание 10

8.3.4. Теорема Холла — формулировка и доказательство
8.4. Потоки в сетях
8.4.1. Определение потока
8.4.2. Разрезы
8.4.3. Теорема Форда-Фалкерсона
8.4.4. Алгоритм нахождения максимального потока
8.4.5. Связь между теоремой Менгера и теоремой Форда-Фалкерсона
8.5. Связность в орграфах
6.5.1. Сильная, односторонняя и слабая связность
8.5.2. Компоненты сильной связности
6.5.3. Выделение компонент сильной связности
8.6. Кратчайшие пути
6.6.1. Длина дуг
6.6.2. Алгоритм Флойда
6.6.3. Алгоритм Дейкстры
8.6.4. Дерево кратчайших путей
6.6.5. Кратчайшие пути в бесконтурном орграфе
Комментарии
Упражнения

274
275
276
277
277
279
281
281
282
282
283
284
264
285
286
286
289
291
291

Глава 9 . Деревья
9.1. Свободные деревья
9.1.1. Определения
9.1.2. Основные свойства деревьев
9.1.3. Центр дерева
9.2. Ориентированные, упорядоченные и бинарные деревья
9.2.1. Ориентированные деревья
9.2.2. Эквивалентное определение ордерева
9.2.3. Упорядоченные деревья
9.2.4. Бинарные деревья
9.3. Представление деревьев в программах
9.3.1. Представление свободных деревьев
9.3.2. Представление упорядоченных ориентированных деревьев
9.3.3. Число упорядоченных ориентированных деревьев
9.3.4. Проверка правильности скобочной структуры
9.3.5. Представление бинарных деревьев
9.3.6. Обходы бинарных деревьев
9.3.7. Алгоритм симметричного обхода бинарного дерева
9.4. Деревья сортировки
9.4.1. Ассоциативная память
9.4.2. Способы реализации ассоциативной памяти
9.4.3. Алгоритм бинарного (двоичного) поиска .
9.4.4. Алгоритм поиска в дереве сортировки
9.4.5. Алгоритм вставки в дерево сортировки
9.4.6. Алгоритм удаления из дерева сортировки
9.4.7. Вспомогательные алгоритмы для дерева сортировки
9.4.8. Сравнение представлений ассоциативной памяти
9.4.9. Выровненные и полные деревья
9.4.10. Сбалансированные деревья
9.4.11. Балансировка деревьев
9.5. Кратчайший остов
9.5.1. Определения
9.5.2. Схема алгоритма построения кратчайшего остова

292
292
292
293
297
297
297
299
300
302
303
303
305
307
306
309
312
313
313
314
314
315
316
317
316
320
321
322
323
325
327
327
328

Содержание

1

9.5.3. Алгоритм Краскала
9.5.4. Алгоритм Прима
Комментарии
Упражнения

329
330
331
332

Глава 1 0 . Циклы, независимость и раскраска

333

10.1. Фундаментальные циклы и разрезы

333

10.1.1. Циклы и разрезы
10.1.2. Фундаментальная система циклов и циклический ранг
10.1.3. Фундаментальная система разрезов и коциклический ранг
10.1.4. Подпространства циклов и коциклов
10.2. Эйлеровы циклы
10.2.1. Эйлеровы графы
10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе
10.2.3. Оценка числа эйлеровых графов
10.3. Гамильтоновы циклы
10.3.1. Гамильтоновы графы
10.3.2. Задача коммивояжёра

333
335
337
338
340
340
341
342
343
343
344

10.4. Независимые и покрывающие множества

345

10.4.1. Покрывающие множества вершин и рёбер
345
10.4.2. Независимые множества вершин и рёбер
346
10.4.3. Связь чисел независимости и покрытий
347
10.5. Построение независимых множеств вершин
348
10.5.1. Постановка задачи отыскания наибольшего независимого множества вершин 348
10.5.2. Поиск с возвратами
349
10.5.3. Улучшенный перебор
350
10.5.4. Алгоритм построения максимальных независимых множеств вершин
352
10.6. Доминирующие множества
353
10.6.1. Минимальное и наименьшее доминирующее множество
353
10.6.2. Доминирование и независимость
353
10.6.3. Задача о наименьшем покрытии
354
10.6.4. Связь задачи о наименьшем покрытии с другими задачами
355
10.7. Раскраска графов
355
10.7.1. Оценки хроматического числа
356
10.7.2. Хроматические числа графа и его дополнения
357
10.7.3. Точный алгоритм раскрашивания .
358
10.7.4. Приближённый алгоритм последовательного раскрашивания
359
10.7.5. Улучшенный алгоритм последовательного раскрашивания
360
10.8. Планарность
361
10.8.1, Укладка графов
361
10.8.2, Эйлерова характеристика
361
10.8.3, Теорема о пяти красках
363
Комментарии
364
Упражнения
364

Указатель основных обозначений

365

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

368

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

370

Предисловие к третьему
изданию
В 2000 году издательство «Питер» выпустило первое издание этого учебника.
В то время выбор учебной литературы по дискретной математике был небогат.
За последние годы ситуация резко изменилась. Переведено достаточное количество добротных американских учебников и несколько отличных книг написано
российскими авторами. Тем не менее предлагаемый учебник по-прежнему имеет
моральное право на существование, поскольку комбинация основных отличительных особенностей (компактность изложения, плюс широта охвата материала,
плюс внимание к деталям программной реализации), по мнению автора, остаётся
привлекательной для широкой категории читателей.
Третье издание книги имеет ту же структуру, последовательность изложения и
систему обозначений, что и второе издание. В книгу внесено несколько десятков не очень объёмных, по существенных добавлений, уточнений и определений.
Обновлены упражнения, библиография и комментарии к ней.
Кроме того, исправлено несколько сотен опечаток, упущений и ошибок. Общее
количество изменений значительно больше количества страниц. Если пользоваться жаргоном программистов, которым адресована эта книга, то можно сказать, что проведён «рефакторипг» всего материала.
Третье издание прошло профессиональное научное редактирование, за что автор
выражает глубокую благодарность научному редактору.
Ф. А. Новиков

Предисловие ко второму
изданию
В 2000 году издательство «Питер» выпустило в свет учебник Ф. А. Новикова
«Дискретная математика для программистов». Книга оказалась удачной, о чём
свидетельствуют тиражи и письма читателей. Резонно предположить, что объем,
стиль и содержание книги отвечают возрастающим потребностям практических
программистов. В то же время за прошедшие три года читатели и коллеги указали
на многочисленные огрехи в изложении материала.
Вниманию читателей предлагается второе издание, исправленное и дополненное,
в котором предпринята попытка устранить недостатки, сохранив достоинства
первого издания. Сохранена предельная лаконичность в изложении материала: по мнению автора, каждая страница, без которой можно обойтись, является
заметным недостатком. Сохранена мелкая рубрикация: раздел нижнего уровня
помещается на одной, редко на двух страницах и может быть прочтен за один
присест, не поднимая головы. Сохранена ориентация на программистов: описание объектов дискретной математики в большинстве случаев доводится до кода
алгоритмов работы с этими объектами. Устранены замеченные ошибки: за три
года автор, рецензенты, студенты и читатели заметили более 200 фактических
неточностей и опечаток в книге — все замеченные опечатки устранены. Изменена
система обозначений с целью устранения излишних вольностей.
В первом издании книги было 12 глав, во втором их десять. Сокращение количества глав по сравнению с первым изданием не означает сокращения объёма
рассматриваемого материала. Это продиктовано желанием автора сделать структуру книги более уравновешенной. Из книги действительно удалено несколько
второстепенных вопросов, которые в первом издании рассматривались довольно поверхностно. Хочется надеяться, что за счёт этого рассмотрение оставшихся
вопросов удалось сделать более подробным.
Обновлен и дополнен список литературы. Как и в первом издании, этот список не имеет цели отразить историю предмета или дать полное библиографическое описание. Это рекомендации для студентов по дополнительному чтению,
отражающие вкусы автора.
Ф. А. Новиков

Вступительное слово к первому
изданию
Автор этой книги Ф. А. Новиков имеет большой омыт практического программирования, чтения лекций по дискретной математике и написания книг, посвященных различным вопросам вычислительной техники и её программного
обеспечения. Все это позволило ему создать книгу, наполненную обширным и
интересным материалом. Она предназначена для студентов младших курсов, специализирующихся в области программирования, но будет полезна не только
им, по и всем тем, кто обучается или стремится повысить квалификацию в
направлениях, тесно связанных с программированием, вплоть до аспирантов.
Ф. А. Новиков охватывает ряд направлений дискретной математики: теорию множеств и алгебраические структуры, логику и булевы функции (причём затронута
даже нетрадиционная проблема автоматического доказательства теорем), комбинаторику и кодирование. Особое внимание уделено общей теории графов —
одному из важнейших инструментов программиста, и главным её приложениям.
Вся книга наполнена примерами конкретных алгоритмов от простых до достаточно сложных, особенно во второй половине книге. Это не только полезный
учебный материал, по и багаж, который не окажется излишним в будущей практической деятельности учащихся. Книг подобной направленности и с подобным
подбором материала в моём поле зрения почти не было.
Книга снабжена списком русскоязычной литературы, из которой читатель сможет извлечь дополнительные сведения по заинтересовавшим его вопросам. Каждый источник из этого списка кратко охарактеризован в конце главы, к которой
он относится.
Содержание книги во всех её разделах продуманно и конкретно. Решение автора не включать в книгу такие темы, как теория алгорифмов, надо считать
правильным — учебный курс не должен быть перегружен.
Книга написана хорошим языком и, можно надеяться, будет благосклонно принята читателем и окажется для него хорошим подспорьем, в частности, при построении математической модели возникшей перед человеком задачи и при выборе
подходящего представления данных. Тому и другому автор уделяет неизменное
внимание. Поучительно также краткое, но в большинстве случаев достаточно
убедительное, обоснование правильности предлагаемых алгоритмов.
Профессор, д.т.и., чл.-корр. РАН

С. С.Лавров

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

Назначение и особенности книги
Данная книга представляет собой учебник по дискретной математике, включающий в себя описания важнейших алгоритмов над объектами дискретной математики. Учебник ориентирован на студентов программистских специальностей и
практикующих программистов, которым по роду их занятий приходится иметь
дело с конструированием и анализом алгоритмов.
В настоящее время имеется масса доступной литературы, покрывающей обе эти
темы. С одной стороны, существуют десятки прекрасных книг по дискретной
математике, начиная с элементарных учебников для начинающих и заканчивая
исчерпывающими справочниками для специалистов. С другой стороны, большое число монографий, многие из которых стали классическими, посвящены
способам конструирования эффективных алгоритмов. Как правило, такие монографии содержат детальное описание и анализ важнейших и известнейших
алгоритмов. Однако книги, которые бы рассматривали обе эти темы одновременно и во взаимосвязи, практически отсутствуют. В качестве редких исключений
можно назвать книгу В. Липского «Комбинаторика для программистов» [8],
перевод которой выдержал уже дьа издания в России, и всеобъемлющую энциклопедию Д. Кнута «Искусство программирования для ЭВМ» [14]-[16]. Первая
из упомянутых книг очень невелика по объёму и в значительной степени пересекается по выбранному материалу с данным учебником. Вторая отличается

16

Введение

максимальной глубиной изложения и большим объёмом, но не затрагивает некоторых важных для программистов разделов дискретной математики. Данный
учебник принадлежит именно к такому жанру математической литературы, в
котором математическое изложение доводится до уровня практически исполнимых программ. Он отличается большей широтой, но, пожалуй, меньшей глубиной
охвата материала.
Учебник основан на лекционном курсе, который автор в течение многих лет читает студентам кафедры «Прикладная математика» Санкт-Петербургского государственного политехнического университета, что наложило определённый отпечаток на выбор материала. Учебник охватывает почти все основные разделы дискретной математики: теорию множеств, математическую логику, общую алгебру,
комбинаторику и теорию графов. Кроме того, представлены и некоторые более
специальные разделы, необходимые программистам, такие как теория кодирования и булевы функции. Данный список можно было бы продолжить, включив в
пего, например, вычислительную геометрию, линейное программирование и т. д.,
по основная цель состояла в том, чтобы написать именно краткий учебник, и,
ограничив себя в объёме, пришлось ограничить и набор рассматриваемых тем.
В целом учебник преследует три основные цели:
1. Познакомить читателя с максимально широким кругом понятий дискретной
математики. Количество определяемых и упоминаемых понятий и специальных терминов намного превышает количество понятий, обсуждаемых более
детально. Тем самым у студента формируется терминологический запас, необходимый для самостоятельного изучения специальной математической и теоретико-программистской литературы.
2. Сообщить читателю необходимые конкретные сведения из дискретной математики, предусматриваемые стандартной программой технических высших
учебных заведений. Разбор доказательств приведенных утверждений и выполнение упражнений позволят студенту овладеть методами дискретной математики, наиболее употребительными при решении практических задач.
3. Пополнить запас примеров нетривиальных алгоритмов. Изучение алгоритмов
решения типовых задач дискретной математики и способов представления математических объектов в программах абсолютно необходимо практикующему
программисту, поскольку позволяет уменьшить трудозатраты на «изобретение
велосипеда» и существенно обогащает навыки конструирования алгоритмов.

Структура книги
Книга содержит 10 глав, которые, фактически, делятся на три группы. Первая группа, несколько большая по объёму (главы 1, 2 и 5), содержит самые
общие сведения из основных разделов дискретной математики. Доля алгоритмов в главах первой группы несколько меньше, а доля определений несколько

Используемые обозначения

17

больше, чем во второй и третьей группах. В второй группе (главы 3, 4 и 6)
собраны различные специальные разделы, которые можно включать или не включать в учебный курс в зависимости от конкретных обстоятельств. Третья группа глав (главы 7-10) целиком посвящена теории графов, поскольку связанные с пей вопросы (в частности, алгоритмы над графами) являются разделами дискретной математики, наиболее широко применяющимися в практическом
программировании.
Главы делятся на разделы, которые, в свою очередь, делятся па подразделы. Каждый раздел посвящён одному конкретному вопросу темы главы и по объёму
соответствует экзаменационному вопросу. Подразделы нужны для внутренних
ссылок и более детальной структуризации материала. Как правило, в подразделе
рассматривается какое-нибудь одно понятие, теорема или алгоритм. Подразделы в пределах раздела упорядочены по сложности: сначала приводятся основные определения, а затем рассматриваются более сложные вопросы, которые,
в принципе, при первом чтении можно пропустить без ущерба для понимания
остального материала.
Главы книги более или менее независимы и могут изучаться в любом порядке, за исключением первой главы, которая содержит набор базисных определений для дальнейшего изложения, и главы 7, в которой вводится специфическая
терминология теории графов.
В конце каждой главы имеются два специальных раздела: «Комментарии» и
«Упражнения». В комментариях приводится очень краткий обзор литературы
по теме главы и даются ссылки на источники, содержащие более детальные
описания упомянутых алгоритмов. Эти разделы не претендуют па статус исчерпывающего библиографического обзора, скорее это рекомендации для студентов
по чтению для самообразования. Выбор источников, как правило, отражает вкусы автора. Упражнения немногочисленны — ровно по одному на каждый раздел — и очень просты. Как правило, в упражнения выносится дополнительный
материал, непосредственно связанный с темой раздела (например, опущенные
доказательства утверждений, аналогичных доказанным в основном тексте).

Используемые обозначения
Данная книга предназначена для программистов, то есть предполагается, что
читатель не испытывает затруднений в понимании текстов программ на языке высокого уровня. Именно поэтому в качестве нотации для записи алгоритмов
используется некоторый неспецифицированпый язык программирования {псевдокод), похожий по синтаксису на Паскаль (но, конечно, Паскалем пе являющийся).
Ключевые слова псевдокода выделены жирным шрифтом, идентификаторы обьектов записываются курсивом, как это принято для математических объектов,
примечания заключаются в фигурные скобки { }.

18

Введение

В языке используются общеупотребительные структуры управления: ветвления
в краткой (if... then ... end if) и полной (if... then ... else ... end if) формах, циклы
со счётчиком (for ... from ... to ... do ... end for), с постусловием ( repeat... until),
с предусловием (while ... do ... end while) и по множеству (for ... do ... end for),
а также переходы (go to ...)1.
Для обозначения присваивания используется традиционный знак : =, вызов процедуры или функции ключевыми словами не выделяется, выход из процедуры
имеете с возвратом значения обозначается ключевым словом return.
Подразумевается строгая статическая типизация, даже приведения не используются, за исключением разыменования, которое подразумевается везде, где оно
нужно по здравому программистскому смыслу. В то же время объявления локальных переменных почти всегда опускаются, если их тип ясен из контекста.
Из структур данных считаются доступными массивы (array [...] of...), структуры
(rccord ... end record) и указатели ( | ) .
В программах широко используются математические обозначения, которые являются самоочевидными в конкретном контексте. Например, конструкция
for х е Л/ do
РН
end for
означает применение процедуры Р ко всем элементам множества М.
«Лишние» разделители систематически опускаются, функции могут возвращать
несколько значений, и вообще, разрешаются любые вольности, которые позволяют сделать тексты программ более краткими и читабельными.
Особого упоминания заслуживают три «естественных» оператора, аналоги которых в явном виде редко встречаются в настоящих языках программирования.
Оператор
select m e M
означает выбор произвольного элемента тп из множества М. Этот оператор часто
необходим в «переборных» алгоритмах. Оператор
yield х
означает возврат значения х, но при этом выполнение функции не прекращается,
а продолжается со следующего оператора. Этот оператор позволяет очень просто
записать «генерирующие» алгоритмы, результатом которых является некоторое
заранее неизвестное множество значений. Оператор
next for х
означает прекращение выполнения текущего фрагмента программы и продолжение выполнения со следующего шага цикла по переменной х. Этот оператор
должен находиться в теле цикла по х (на любом уровне вложенности). Такого
1
«Структурных» программистов, сомневающихся в допустимости использования оператора goto в
учебнике, автор отсылает к статье Д. Кнута «Structured Programming with go to statements».

19

Используемые обозначения

рода «структурные переходы» позволяют описывать обработку исключительных
ситуаций в циклах непосредственно, без введения искусственных переменных,
отслеживающих состояние вычислений в цикле.
Операторы select, yield и next for не являются чем-то необычным и новым:
первый из них легко моделируется использованием датчика псевдослучайных
чисел, второй — присоединением элемента к результирующему множеству, а третий — переходом по метке. Однако указанные операторы сокращают запись и
повышают её наглядность.
Поскольку эта книга написана на «программно-математическом» языке, в ней ие
только математические обозначения используются в программах, но и некоторые
программистские обозначения используются в математическом тексте.
Прежде всего обсудим способы введения обозначений объектов и операций. Если
обозначение объекта или операции является глобальным (в пределах учебника),
то используется знак
который следует читать «по определению есть». При
этом слева от знака
может стоять обозначение объекта, а справа — выражение,
определяющее этот объект. Например,

1+ Г= {х € Ш | х > 0}.
В случае определения операции в левой части стоит выражение. В этом случае левую часть следует неформально понимать как заголовок процедуры выполнения
определяемой операции, а правую часть — как тело этой процедуры. Например,
формула
Л=

Ас

В к В с А

означает следующее: «чтобы вычислить значение выражения А = В, нужно вычислить значения выражений А с В w В с А, а затем вычислить конъюнкцию
этих значений».
Отметим широкое использование символа присваивания : =*, который в математическом контексте можно читать как «положим». Если в левой части такого
присваивания стоит простая переменная, а в правой части — выражение, определяющее конкретный объект, то это имеет очевидный смысл введения локального
(в пределах доказательства, определения и т. п.) обозначения. Например, запись
Z': = Zl)Zek \ {efc} означает: «положим, что Z' содержит все элементы Z и ZCk за
исключением е^». Наряду с обычным для математики «статическим» использованием знака : =, когда выражению в левой части придается постоянное в данном
контексте значение (определение константы), знак присваивания используется
и в «динамическом», программистском смысле. Например, пусть в графе G есть
вершина v. Тогда формулу G: = G — v следует читать и понимать таю «удалим в
графе G вершину v».
Некоторые обозначения являются глобальными, то есть означают одно и то же
в любом контексте (в этой книге). Например, буква М всегда обозначает поле
вещественных чисел, а пара вертикальных чёрточек слева и справа от объекта
\Х\ — количество элементов в объекте X. Таких стандартных обозначений не

20

Введение

так уж много. Они собраны в указателе обозначений в конце книги и используются в тексте учебника без дополнительных пояснений. Если смысл какого-то
обозначения не ясен и не определён в данном контексте, то следует посмотреть
это обозначение в указателе обозначений.
Одной из задач книги является выработка у студентов навыка чтения математических текстов. Поэтому, начиная с самой первой страницы, без дополнительных объяснений интенсивно используются язык исчисления предикатов
и другие общепринятые математические обозначения. При этом стиль записи
формул совершенно свободный и неформальный, но соответствующий общепринятой практике записи формул в математических текстах. Например, вместо
формулы
Vfc ((к < п) = • Р(к))
может быть написано
VA: < п (Р{к))
или даже
Vfc < п Р(к)
в предположении, что читатель знает или догадается, какие синтаксические упрощения используются. В первых главах книги основные утверждения (формулировки теорем) дублируются, то есть приводятся на естественном языке и па
языке формул. Тем самым на примерах объясняется используемый язык формул.
Но в последних частях книги и в доказательствах использование естественного
языка сведено к минимуму. Это существенно сокращает объём текста, но требует
внимания при чтении.
Для краткости в тексте книги иногда используются обороты, которые подразумевают восстановление читателем опущенных слов по контексту. Например,
если символ А означает множество, то вместо аккуратного, но длинного оборота
«где объект х является элементом множества А», может быть использована более
короткая фраза «где х — элемент А» или даже формула «где х е А».
В целом используемые обозначения строго следуют классическим образцам, принятым в учебной математической и программистской литературе. Непривычным может показаться только совместное использование этих обозначений в одном тексте. Но такое взаимопроникновение обозначений продиктовано основной
задачей книги.

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

Выделения в тексте

21

Все определяющие вхождения вынесены в предметный указатель, помещённый
в конце книги. Таким образом, если при чтении попадается незнакомый термин, следует найти его определение с помощью указателя (или убедиться, что
определения в книге нет). В третьем издании математические термины в предметном указателе переведены на английский язык. Автор надеется, что предметный указатель послужит читателю как краткий толковый математический
русско-аиглийский словарь.
Формулировки теорем, лемм и следствий в соответствии с общепринятой в математической литературе практикой выделены курсивом. При этом формулировке предшествует соответствующее ключевое слово: «теорема», «лемма» или
«следствие». Как правило, утверждения не нумеруются, за исключением случаев
вхождения нескольких однородных утверждений в один подраздел. Для ссылок на утверждения используются либо номера подразделов, в которых утверждения сформулированы, либо собственные имена утверждений. Дело в том, что в
данном учебнике теоремами оформлены как простые утверждения, являющиеся
непосредственными следствиями определений, так и глубокие факты, действительно заслуживающие статуса теоремы. В последнем случае приводится собственное имя (название теоремы), которое либо выносится в название подраздела
(или раздела), либо указывается в скобках после слова «теорема».
Доказательства относятся к предшествующим утверждениям, а обоснования — к
предшествующим алгоритмам. В учебнике практически нет недоказанных утверждений и приведенных без достаточного обоснования алгоритмов. Из этого правила имеется несколько исключений, то есть утверждений, доказательства которых
не приводятся, поскольку автор считает их технически слишком сложными для
выбранного уровня изложения. Отсутствие технически сложного доказательства
всегда явно отмечается в тексте. Иногда же доказательство опускается, потому что утверждение легко может быть обосновано читателем самостоятельно.
Такие случаи не отмечаются в тексте. Доказательства и обоснования начинаются с соответствующего ключевого слова («доказательство» или «обоснование»)
и заканчиваются специальным значком • . Если формулировка теоремы содержит несколько утверждений или если доказательство состоит из нескольких
шагов (частей), то оно делится на абзацы, а в начале каждого абзаца указывается
[в скобках], что именно в нем доказывается.
Замечания и отступления также начинаются с соответствующего ключевого слова: «замечание» или «отступление». Назначение этих абзацев различно. Замечание сообщает некоторые специальные или дополнительные сведения, прямо
относящиеся к основному материалу учебника. Отступление не связано непосредственно с основным материалом, его назначение — расширить кругозор читателя и показать связь основного материала с вопросами, лежащими за пределами
курса.

22

Введение

ЗАМЕЧАНИЕ
В очень редких случаях курсив используется не для выделения определяющих вхождений
терминов и формулировок утверждений, а для того, чтобы сделать эмфатическое удареиие
на каком-то слове в тексте.
ОТСТУПЛЕНИЕ
Использование отступлений необходимо, в противном случае у читателя может сложиться
ошибочное впечатление о замкнутости изучаемого предмета и его оторванности от других
областей знания.
Алгоритмы, как уже было сказано, записаны на псевдокоде, синтаксискоторого
кратко описан выше. Как правило, перед текстом алгоритма па естественном языке указываются его назначение, а также входные и выходные данные. Ключевые
слова в текстах алгоритмов выделяются полужирным шрифтом. Исполняемые
операторы, как правило, комментируются, чтобы облегчить их понимание. После
алгоритма приводятся его обоснование и иногда пример протокола выполнения.
Примеры, как правило, приводятся непосредственно вслед за определением понятия, поэтому не используется никаких связующих слов, поясняющих, к чему
относятся примеры. В самих примерах интенсивно используются факты, которые
должны быть известны читателю из курса математики средней школы, и понятия,
рассмотренные в предшествующем тексте книги.

Благодарности
Автор выражает благодарность члену-корреспонденту РАН Святославу Сергеевичу Лаврову за сотни ценных замечаний по тексту первого издания книги, многочисленным студентам, прослушавшим этот курс, за выявление ошибок в тексте,
и научному редактору, профессору Никите Юрьевичу Нецветаеву, за огромную
помощь в работе над третьим изданием.

От издательства
Ваши замечания, предложения, вопросы отправляйте по адресу электронной почты comp@plter.com (издательство «Питер», компьютерная редакция). Можно обратиться непосредственно к автору по адресу fedornovlkov@ramblar.ru Мы будем
рады узнать ваше мнение!
Подробную информацию о наших книгах вы найдете на веб-сайте издательства
http: //www. plter. com,

Глава 1

Множества
и отношения

Понятия «множество», «отношение», «функция» и близкие к ним составляют
основной словарь дискретной (равно как и «непрерывной») математики. Именно
эти базовые понятия рассматриваются в первой главе, тем самым закладывается
необходимая основа для дальнейших построений. Особенность изложения состоит в том, что здесь рассматриваются почти исключительно конечные множества, а
тонкие и сложные вопросы, связанные с рассмотрением бесконечных множеств,
излагаются с «программистской» точки зрения. С другой стороны, значительное внимание уделяется «представлению» множеств в программах. Эти вопросы
не имеют прямого отношения к собственно теории множеств в её классическом
виде, но очень важны для практикующего программиста.

1.1. Множества
При построении доступной для рационального анализа картины мира часто используется термин «объект» для обозначения некой сущности, отделимой от
остальных. Выделение объектов — это не более чем произвольный акт нашего
сознания. В одной и той же ситуации объекты могут быть выделены по-разному,
в зависимости от точки зрения, целей анализа и других обстоятельств. Но как
бы то ни было, выделение объектов и их совокупностей — естественный (или
даже единственно возможный) способ организации нашего мышления, поэтому
неудивительно, что он лежит в основе главного инструмента описания точного
знания - математики.

1.1.1. Элементы и множества
Понятие множества принадлежит к числу фундаментальных понятий математики. Можно сказать, что множество — это любая определённая совокупность
объектов. Объекты, из которых составлено множество, называются его элементами. Элементы множества различны и отличимы друг от друга. Как множествам,
так и элементам можно давать имена или присваивать символьные обозначения.

24

Глава 1. Множества и отношения

ЗАМЕЧАНИЕ
В современной математике основным способом определения фундаментальных понятий
является аксиоматический метод. В рамках этого метода группа понятий, образующих
основу некоторой теории, определяется путем постулирования набора аксиом (утверждений об этих понятиях, принимаемых без доказательства), так что остальные утверждения
выводятся из аксиом с помощью логических доказательств. Применение аксиоматического метода предполагает наличие развитого логического языка для формулировки утверждений, и, как правило, требует значительных усилий, времени и места для построения
строгих формальных доказательств. Теория множеств не является исключением — для
неё предложено несколько систем аксиом, весьма поучительных и оказавших значительное влияние на развитие математики в целом. Альтернативой аксиоматическому методу
является апелляция к интуиции, здравому смыслу и использование неопределяемых понятий. Применительно к теории множеств такой подход получил название «наивной теории
множеств», элементы которой излагаются в этом учебнике.

Примеры
Множество S страниц в данной книге. Множество N натуральных чисел {1, 2,
3, ...}. Множество Р простых чисел {2, 3, 5, 7, 11, ...}. Множество Z целых чисел {..., - 2 , - 1 , 0, 1, 2, ...}. Множество Ш вещественных чисел. Множество А
различных символов на этой странице.
Если объект х является элементом множества М, то говорят, что х принадлежит
М. Обозначение: х € М. В противном случае говорят, что х не принадлежит М.
Обозначение: х 0 (Vn > по (Дп) ^

сд(п))).

Если элементы в списках упорядочить, например, по возрастанию значения поля г, то трудоёмкость всех операций составит 0(п). Эффективная реализация
операций над множествами, представленными в виде упорядоченных списков,
основана па весьма общем алгоритме, известном как алгоритм слияния. Алгоритм
слияния параллельно просматривает два множества, представленных упорядоченными списками, причём на каждом шаге продвижение происходит в том
множестве, в котором текущий элемент меньше.

1.3.5. Проверка включения слиянием
Рассмотрим алгоритм слияния, который определяет, является ли множество А
подмножеством множества В.
Алгоритм 1.4 Проверка включения слиянием
Вход: проверяемые множества А и В, которые заданы указателями а и Ь.
Выход: true, если А с В, в противном случае false.
pa: = a\pb: = b { инициализация }
while pa ф nil к рЬф nil do
if pa л < pb.i then
return false { элемент множества А отсутствует в множестве В }
else if pa л > pb. i then
pb-.~pb.n
{ элемент множества А, может быть, присутствует
множестве В }
else
pa: — pa ль { здесь pa л = pb.i, то есть }
pb\ --pb.n { элемент множества А точно присутствует в множестве В }
end if
end while
return pa = nil {true, если А исчерпано, false — в противном случае }

в

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

ОБОСНОВАНИЕ

1.3. Представление множеств в программах

43

совпадающие элементы и происходит продвижение сразу в обоих множествах.
По завершении основного цикла возможны два варианта: либо pa = nil, либо
ра ф nil. Первый означает, что для всех элементов множества А удалось найти
совпадающие элементы в множестве В. Второй — что множество В закончилось
раньше, то есть не для всех элементов множества А удалось найти совпадающие
элементы в множестве В.


1.3.6. Вычисление объединения слиянием
Рассмотрим алгоритм слияния, который вычисляет объединение двух множеств,
представленных упорядоченными списками.
Алгоритм 1.5 Вычисление объединения слиянием
Вход: объединяемые множества А и В, которые заданы указателями а и Ь.
Выход: объединение С = A U В, заданное указателем с.
pa:=a-,pb: = b;c: =nil; е: =nil { инициализация }
while pa фт\ к pb фт\ do
if pa.i < pb.i then
d: = pa.i] pa: =pa.n { добавлению подлежит элемент множества А }
else if pa.i > pb.i then
d\ = pb.i\pb\ =pb.n { добавлению подлежит элемент множества В }
else
d\=pa.i { здесь pa.i = pb.i, и можно взять любой из элементов }
ра\ = pa.n\pb: =pb.n { продвижение в обоих множествах }
end if
Append(c,e,d) { добавление элемента d в конец списка с }
end while
р: =nil { указатель «хвоста» }
if pa Ф nil then
р \ ~ р а { нужно добавить в результат оставшиеся элементы множества А }
end if
if pb ф nil then
p\~pb { нужно добавить в результат оставшиеся элементы множества В }
end if
while р фп\\ do
Append(n,e,p.i) { добавление элемента pa.i в конец списка с }
р: = р.п { продвижение указателя «хвоста» }
end while
На каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В. В первом случае в результирующий список добавляется
текущий элемент множества А и происходит продвижение в этом множестве, во
ОБОСНОВАНИЕ

44

Глава 1. Множества и отношения

втором — аналогичная операция производится с множеством В, а в третьем случае найдены совпадающие элементы и происходит продвижение сразу в обоих
множествах. Таким образом, в результат попадают все элементы обоих множеств,
причём совпадающие элементы попадают ровно один раз. По завершении основного цикла один из указателей, ра и pb (но не оба вместе!), может быть пе равен
nil. В этом случае остаток соответствующего множества без проверки добавляется
в результат.

Вспомогательная процедура Append(c, е, d) присоединяет элемент d к хвосту е
списка с.
Алгоритм 1.6 Процедура Append — присоединение элемента в конец списка
Вход: указатель с на первый элемент списка, указатель е на последний элемент
списка, добавляемый элемент d.
Выход: указатель с на первый элемент списка, указатель е на последний элемент
списка.
q: = new(elem); q.i: = d; q.n: =nil { новый элемент списка }
if с =nil then
c:—q { пустой список }
else
e.n :—-q{ непустой список }
end if
e: = q
Д О первого вызова функции Append имеем: с = nil и е = nil. После
первого вызова указатель с указывает на первый элемент списка, а указатель е —
на последний элемент (который после первого вызова является тем же самым
элементом). Если указатели с и е не пусты и указывают иа первый и последний
элементы правильного списка, то после очередного вызова функции Append это
свойство сохраняется. Из текста основной программы видно, что, кроме инициализации, все остальные манипуляции с этими указателями выполняются только
с помощью функции Append.

ОБОСНОВАНИЕ

1.3.7. Вычисление пересечения слиянием
Рассмотрим алгоритм слияния, который вычисляет пересечение двух множеств,
представленных упорядоченными списками.
Алгоритм 1.7 Вычисление пересечения слиянием
Вход: пересекаемые множества А и В, заданные указателями а и Ь.
Выход: пересечение С = А П В, заданное указателем с.
ра: — а; pb\—b; с: = nil; е: =nil { инициализация }
while pa / n i l & pb / n i l do

1.3. Представление множеств в программах

45

if pa.i < pb.i then
p a : = pa.n { элемент множества А пе принадлежит пересечению }
else if pa.i > pb.i then
pb: —pb.n { элемент множества В не принадлежит пересечению }
else
{ здесь pa.i = pb.i — данный элемент принадлежит пересечению }
Append(c,е,pa.i)-,pa: = pa.n\pb: =pb.n { добавление элемента }
end if
end while
На каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В. В первом случае текущий элемент множества А пе принадлежит
пересечению, оп пропускается и происходит продвижение в этом множестве, во
втором то же самое производится с множеством В. В третьем случае найдены совпадающие элементы, один экземпляр элемента добавляется в результат
и происходит продвижение сразу в обоих множествах. Таким образом, в результат попадают все совпадающие элементы обоих множеств, причём ровно
один раз.

ОБОСНОВАНИЕ

1.3.8. Представление множеств итераторами
В предыдущих подразделах рассмотрены представления, в которых структуры
данных предполагаются известными и используются при программировании операций. Иногда это бывает неудобно, поскольку, во-первых, возникают затруднения при совместном использовании нескольких альтернативных представлений
для одного типа объектов, и, во-вторых, необходимо заранее определять набор
операций, которым открыт доступ к внутренней структуре данных объектов.
(Такие операции часто называют первичными.)
ОТСТУПЛЕНИЕ
Парадигма объектио-ориеитироваипого программирования предполагает совместное согласованное определение структур данных и процедур доступа к ним (типов как множеств
значений и первичных операций над значениями из этих множеств). Мы хотим напомнить читателю, что парадигма объектно-ориентированного программирования — весьма
полезная, по отнюдь не универсальная и пе единственная парадигма программирования.

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

46

Глава 1. Множества и отношения

не зависящий от представления множеств. Видимо, можно считать, что с программистской точки зрения для представления множества достаточно итератора — процедуры, которая перебирает элементы множества и делает с ними то,
что нужно. Синтаксически понятие итератора может быть реализовано самыми различными способами в зависимости от традиций, стиля и используемого
языка программирования. Например, следующая программа выполняет процедуру S для всех элементов множества X (см. также доказательство теоремы 1 в
подразделе 1.2.5):
while X ф 0 do
select х € X { выбор произвольного элемента х из множества X }
S(x) { применение процедуры S к элементу х }
X : = X - х {удаление элемента х с целыо исключить его повторный выбор}
end while
В этом варианте реализации итератора исходное множество «исчезает», что не
всегда желательно. Очевидно, что для всякого конкретного представления множества можно придумать такую реализацию итератора, которая обеспечивает
перебор элементов ровно по одному разу и пе портит исходного множества.
Мы полагаем (здесь и >далее во всей книге), что наличие итератора позволяет
написать цикл
for х € X do
S(x) { где S — любой оператор или процедура, зависящие от х }
end for
и этот цикл означает применение оператора S ко всем элементам множества X
по одному разу в некотором неопределённом порядке.
ЗАМЕЧАНИЕ
В доказательствах цикл for х € X do S(x) end for используется и в том случае, когда
=
= оо. Это не означает реального процесса исполнения тела цикла в дискретные моменты
времени, а означает всего лишь мысленную возможность применить оператор S ко всем
элементам множества X независимо от его мощности.

В таких обозначениях итератор пересечения множеств X П У может быть задан
алгоритмом 1.8.
Алгоритм 1.8 Итератор пересечения множеств
for х € X do
for у £ Y do
if x — у then
S(x) { тело цикла }
next for x { следующий x }
end if
end for
end for

47

1.3. Представление множеств в программах

Аналогично итератор разиости множеств X\Y

может быть задан алгоритмом 1.9.

Алгоритм 1.9 Итератор разности множеств
for х £ X do
for у eY do
if x = у then
next for x { следующий x }
end if
end for
S(x) { тело цикла }
end for
ЗАМЕЧАНИЕ
Оператор next for x — это оператор структурного перехода, выполнение которого в данном случае означает прерывание выполнения цикла по у и переход к следующему шагу
в цикле по х.
Заметим, что A U В = {А \ В) U В и (А \ В) П В - 0 . Поэтому достаточно рассмотреть итератор объединения дизъюнктных множеств X UK (алгоритм 1.10),
где X П Y = 0 .
Алгоритм 1.10 Итератор объединения дизъюнктных множеств
for х € X do
S(x) { тело цикла }
end for
for у eY do
S(y) { тело цикла }
end for
Стоит обратить внимание на то, что итератор пересечения реализуется вложенными циклами, а итератор дизъюнктного объединения — последовательностью
циклов.
Нетрудно видеть, что сложность алгоритмов для операций с множествами при
использовании предложенного представления, не зависящего от реализации, составляет в худшем случае 0(пт), где тип
— мощности участвующих множеств, в то время как для представления упорядоченными списками сложность
в худшем случае равна 0(п + т).
ЗАМЕЧАНИЕ
На практике почти всегда оказывается так, что самая изощрённая реализация операции,
не зависящая от представления, оказывается менее эффективной по сравнению с самой
прямолинейной реализацией, ориентированной на конкретное представление.

48

Глава 1. Множества и отношения

ОТСТУПЛЕНИЕ
При современном состоянии аппаратной базы вычислительной техники оказывается, что
во многих задачах можно пренебречь некоторым выигрышем в эффективности, например, различием между 0(птп) и 0(п + т). Другими словами, нынешние компьютеры
настолько быстры, что часто можно не гнаться за самым эффективным представлением,
ограничившись «достаточно эффективным».

1.4. Отношения
Обычное широко используемое понятие «отношение» имеет вполне точное математическое значение, которое вводится в этом разделе.

1.4.1. Упорядоченные пары и наборы
Если а и b — объекты, то через (а, Ь) обозначим упорядоченную пару. Равенство
упорядоченных пар определяется следующим образом:
(а, Ъ) = (с, d) = f а = с & b = d.
Вообще говоря, (а, Ь) ф (Ь, а).
ЗАМЕЧАНИЕ
Формально упорядоченные пары можно определить как множества, если определить их
так: (а,Ь) = {а, {а, Ь}}. Таким образом, введённое понятие упорядоченной пары пе выводит рассмотрение за пределы теории множеств.

Аналогично упорядоченным парам можно рассматривать упорядоченные тройки,
четвёрки и т. д. В общем случае подобные объекты называются n-ками, кортежами, наборами или (конечными) последовательностями. Упорядоченный набор
из п элементов обозначается ( a i , . . . , а п ). Набор ( a i , . . . , а п ) можно определить
рекурсивно, используя понятие упорядоченной пары:
( а ь . . . , а п ) =f ( ( a i , . . . , a n _ i ) , а п ) .
Количество элементов в наборе называется его длиной и обозначается следующим образом: | ( a i , . . . , а п )\.
ТЕОРЕМА

Два набора одной длины равны, если равны их соответствующие эле-

менты:
Vn ^ ( a b . . . , a n ) = ( 6 i , . . . , b n )

Да» = ^



49

1.4. Отношения

Индукция по п. База: при п = 2 по определению равенства
упорядоченных пар. Пусть теперь

ДОКАЗАТЕЛЬСТВО

71 — 1

( а ь . . . , a n _ i ) = (bi,... ,b n _i)

Д а, = bi.
г= 1

Тогда
( а ь . . . ,а„) = ( 6 i , . . . ,ЬП)

-Ф=>

( ( a i , . . . , a n _ i ) , a n ) = ( ( b i , . . . ,6„_i) ,Ь„)
( а ь . . . , a n _ i ) = ( b i , . . . , 6 n _ i ) к ап = bn

n-1
Д ai = 6».



г=1

Отсюда следует, что порядок «отщепления» элементов в рекурсивном определении кортежа не имеет значения.
ЗАМЕЧАНИЕ
Наиболее естественным представлением в программе n-ки с элементами из множества А
является массив array [l..n] of А.

1.4.2. Прямое произведение множеств
Пусть А и В — два множества. Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которых первый
элемент принадлежит А, а второй принадлежит В:
Ах

В = f {(а,Ь) | а G А & be

В}.

ЗАМЕЧАНИЕ
Точка на плоскости может быть задана упорядоченной парой координат, то есть двумя
точками на координатных осях. Таким образом, R 2 = 1 х К. Своим появлением метод
координат обязан Декарту1, отсюда и название «декартово произведение».

ТЕОРЕМА

Для конечных множеств А и В \А х В\ = \А\ \В\.

Первый компонент упорядоченной пары можно выбрать \А\
способами, второй — | £ | способами, причём независимо от выбора первого элемента. Таким образом, всего имеется
различных упорядоченных пар.


ДОКАЗАТЕЛЬСТВО

1

Реле Декарт ( 1 5 9 6 - 1 6 5 0 ) .

50

ЛЕММА

Глава 1. Множества и отношения



х В)

х С ~ А х (В

х

С).

ДОКАЗАТЕЛЬСТВО

(Ах В) х С =

{((а,

Ь)с) |

(а, Ь) G

А х В к с 6 С} =

= {(а, Ь, с) \ а е. А к b € В к с £ С}
~ {(а, (6, с)) | а е А к{Ь,с) € 5 х С} = Л х [В х С).



Понятие прямого произведения допускает обобщение. Прямое произведение множеств А1у..., Ап — это множество наборов (кортежей):
Ai х • • • х Ап = f { ( a i , . . . ,ап) | ai в A\ k ... k aTl € An) .
Множества Л/ не обязательно различны.
Степенью множества А называется его n-кратпое прямое произведение самого
на себя. Обозначение:
Ап =' А х ••• х А.
п рпа
Соответственно, А[ =' А, А'2 =' Ах А и вообще Ап = f А х А п ~ 1 .
СЛЕДСТВИЕ

|ЛП| =

|Л|П.

1.4.3. Бинарные отношения
Пусть А и В — два множества. Бинарным отношением между множествами А и
В называется тройка (A,B,R), где R — подмножество прямого произведения А
и В:
RcAxB.
R называется графиком отношения, А называется областью отправления, а. В —
областью прибытия. Если множества А и В определены контекстом, то часто
просто говорят, что задано отношение R. При этом для краткости отношение
обозначают тем же символом, что и график.
ЗАМЕЧАНИЕ
Принято говорить «отношение между множествами», хотя порядок множеств имеет значение, и отношение между А и В совсем не то же самое, что отношение между В я А.
Поэтому иногда, чтобы подчеркнуть это обстоятельство, употребляют оборот «отношение
R из множества А в множество В».

51

1.4. Отношения

Среди элементов множеств А и В могут быть такие, которые пе входят ии в одну
из пар, определяющих отношение R. Множество элементов области отправления,
которые присутствуют в парах отношения, называется областью определения
отношения R и обозначается БошЛ, а множество элементов области прибытия, которые присутствуют в парах отношения, называется областью значений
отношения R и обозначается Im R\
DomR = {абЛ\3beB
1тД =({ЬеВ\Зае

((а,6) £ Д)} ,
А ((a,b)eR)}.

Если А = В (то есть R с Л 2 ), то говорят, что R есть отношение на множестве А.
Для бинарных отношений обычно используется инфиксная форма записи:
aRb = f (а,Ь)€ R c Ах

В.

Инфиксная форма позволяет более кратко записывать некоторые формы утверждений относительно отношений:
aRbRc s1 (а, Ь) € R k {Ь} с) € R.
Примеры
Пусть задано множество U. Тогда 6 (принадлежность) - отношение между элементами множества U и элементами булсапа 2' ; , а с (включение) и - (равенство) — отношения на 2й. Хорошо известны отношения
определённые на множестве вещественных чисел.
Пусть R есть отношение между А и В: R с А х В. Введём следующие понятия:
Обратное отношение:

я-1 = { М ) I

Дополнение отношения:

R = {(a, b) | (а, b) £ R} с А х В.

Тождественное отношение:

I = f {(а, а) | а € А} с А2.

Универсальное отношение:

U — {(а, b) | а е А к b € В} = А х В.

а) G R} С В х А.

Def

ЗАМЕЧАНИЕ
График тождественного отношения на множестве А иногда называют диагональю в Ах А.

Введем обобщённое понятие отношения: п-местное (п-арное) отношение R —
это подмножество прямого произведения п множеств, то есть множество упорядоченных наборов (кортежей):
Def

R С Ах х • • • х Ап = { ( а ь ..., ап) \ аг Я = R-\
[ 3.

] VA,FT,с G A (aRb k bRc =• aRc) аЯс)
Я о Я С Я.

[ 4.

] От противпого. ЯП Я - 1 ^ / =>• За ^ ft (аЯй & о/2~16)
З а ^ ft (aRb k

[ 4.

] Я П Я"

1

bRa).
= / = • (aRb к a,R~lb

а =

ft)

(аЯЬ & ЬЯа

а = ft).

[ 5. =>. ] От противпого. Я П / ^ 0 = >
З а G Л (аЯа & а / а )
[ 5.

З а G Л (аЯа)

^ V a G Л (-паЯа).

] Я П / = 0 ==> S a £ А (аЯа) = Ф Va G Л (-.аДа).

[ 6. ] Va, ft G Л (а = ft V aRb V ЬЯа)
Va, ft G Л ((a, b) £ I V (a,b) £ R V (a, ft) G Я - 1 )
с/ с / и я и я - 1
С/ = Я и / и Я " 1 .



55

1.4. Отношения

1.4.7. Ядро отношения
Если Л с А х В — отношение между множествами А и В, то композиция
называется ядром отношения R и обозначается ker R. Другими словами,
aiker Ra2

ЗЬ е В (aiRb к

RoR-1

a2Rb).

Ядро отношения R между А и В является отношением на А:
R С А х В => ker R с А2.
Примеры
1. Пусть отношение N\ «находиться на расстоянии не более 1» на множестве
целых чисел определено следующим образом:
N i : = { ( n , т ) | \п — га| ^ 1} .

Тогда ядром этого отношения является отношение N2 «находиться на расстоянии не более 2»:
N2: = {(n,m) | \п - m\ ^ 2} .
2. Ядром отношения «быть знакомыми» является отношение «быть знакомыми
или иметь общего знакомого».
3. Ядро отношения е между U и 2и универсально: Va,Ъ е U ({а, Ь] е 2и).
4. Ядро отношения С на 2и также универсально.
5. Рассмотрим отношение «тесного включения» на 2и\
X c Y =

f

X c Y k \X\ + 1 = \Y\.

Ядром отношения с1 является отношение «отличаться не более чем одним
элементом»:
ker С = {X,Y

€ 2и \ \Х\ = |У| к \Х П Y\ > |Х| - l } .

ЗАМЕЧАНИЕ
Термин «ядро» и обозначение ker используются также и для других объектов. Их пе
следует путать — из контекста обычно ясно, в каком смысле используется термин «ядро».

ТЕОРЕМА

Ядро любого отношения рефлексивно и симметрично на области опре-

деления:
VЛ С Л х Б (Va G DomR ( a k e r R a ) k Va,6 G D o m R ( a k e r R b =>

bkerRa)).

ДОКАЗАТЕЛЬСТВО

[ Рефлексивность ] Пусть a e DomR. Тогда 3b £ В (aRb)
=> 3b e В (aRb k bR~1a) => (a,a) € RoR'1
aker Л a.
[ Симметричность ] Пусть a, be Dom Л k a ker Л b. Тогда Зс e В (aRc k
=>3ceB
(bRc k cR~la) =>• (b, a) e Ro Л - 1 ==>• 6 ker Л a.

cR~lb)


56

Глава 1. Множества и отношения

1.4.8. Представление отношений в программах
Пусть R отношение па A, R с А2 и \А\ = п. Перенумеруем элементы множества А, А = { a i , . . . ,ап}. Тогда отношение R можно представить булевой матри[г, j] = cuRaj^j.
цеи R : array [l..n, 1 ..п] of 0..1, где Vг, j е 1 ..п
ЗАМЕЧАНИЕ
Термин «булева матрица» означает, что элементы матрицы — булевские значения и операции над ними выполняются по соответствующим правилам (глава 3). В частности, если
I А | и | В | — булевы матрицы, то операции па ними определяются следующим образом:
| А \ [i,j] = f |~л] [?, г];

транспонирование:
вычитание-.

- |~в|) [i, j] ==0

[®> Jl &

~

0

инвертирование-. \ А | [г, j] =' 1 — А [г, j];
А | х В ^ [i,j] = f \/

умножение:

| Й1 V R2 ^ [i,j] = f Ri

дизъюнкция:

[г, к] &; В_
[ i , j ] V R2 [i,j].

В следующих утверждениях предполагается, что все рассматриваемые отношения определены на множестве А, причём \А\ = п.
ТЕОРЕМА

1

R -1

ДОКАЗАТЕЛЬСТВО

R

(6, a ) e R

1

( a , b) е R

R

[a, b] = 1

R

[6, a] = 1.



В универсальное отношение U входят все пары элементов, поэтому все элементы
матрицы универсального отношения U равны 1.
и

R

-

Ь) е R


СЛЕДСТВИЕ

R



R

-

.

R ) м

(a, b) £ R
= 1.

R

[а, Ь] = 0

и



57

1.5. Замыкание отношений

ТЕОРЕМА 3

о Д2

ДОКАЗАТЕЛЬСТВО

(A,B)

Д2

.

е R\ о R2

4

Зс е А (aRxc к cR2b)

[с, 6] = l ) Ф ^ З с е А ( ( И f '

Rk

&

И

ЗС
c ь

f' 0

=

1

)

Е

А
^

(]~йГ[ х [д7[) [а, 6] = 1.



R

R\ U Д2

ДОКАЗАТЕЛЬСТВО

= 1

х

[a,fc]& [йТ] [А;, Ь]^ = 1

СЛЕДСТВИЕ

ТЕОРЕМА

Дх

a

([ДП [а, с] = 1 & Щ
^ V

=

(A,

b)

-

Ri

V

Е ДХИД2

д2
aR\b\JaR2b

Д1 [а,ft]= 1 V Д 2 [а, ^ =

V |~йГ[) [а,ft]= 1.

П

ЗАМЕЧАНИЕ
Представление отношений с помощью булевых матриц — это только один из возможных
способов представления отношений. Другие варианты рассматриваются при обсуждении
представления графов в главе 7.

1.5. Замыкание отношений
Замыкание является весьма общим математическим понятием, рассмотрение конкретных вариантов которого начинается в этом разделе и продолжается в других
главах книги. Неформально говоря, замкнутость означает, что многократное выполнение допустимых шагов не выводит за определённые границы. Например,
предел сходящейся последовательности чисел из замкнутого интервала [a,ft]обязательно принадлежит этому интервалу, а предел сходящейся последовательности чисел из открытого (то есть не замкнутого) интервала (a, ft) может лежать вне
этого интервала. В некоторых случаях можно «расширить» незамкнутый объект
так, чтобы он оказался замкнутым.

1.5.1. Транзитивное и рефлексивное замыкание
Пусть Д и R' — отношения па множестве М. Отношение R' называется замыканием R относительно свойства С, если:
1) Д' обладает свойством С:

С(Д');

2) R' является надмножеством Д:

Д С Д';

3) Д' является наименьшим таким объектом:

C(R") & Д с R"

Д' с R".

58

Глава 1. Множества и отношения

Пусть R+ — объединение положительных степеней R, a R* — объединение неотрицательных степеней R:
оо

ТЕОРЕМА

i= 1
R+ — транзитивное замыкание R.

оо

г=0

Проверим выполнение свойств замыкания при условии, что
свойство С — это транзитивность.

ДОКАЗАТЕЛЬСТВО

[С(Я+) ] Пусть aR+b & bR+c. Тогда З п (aR n b) & 3 m (bRmc). Следовательно,
3 c i , . . . , c n _ i (aRc\R... Rcn-\Rb) и 3 d i , . . . , d m _ i (bRd\R... Rdm-\Rc).
Таким
образом, aRc\R... Rcn-\RbRdiR...
Rdm_iRc ==> aRn+m+1c
aR+c.
oo

[ R с R+ ] R — R1 ==>• R с U R l ^ R c R + .
i=i
[ C(R") & R с R" ==• Я + с Л" ] аД+Ь
ЗА; (аД*Ь) =Ф
3 c i , . . . , c f c _ i (aRc\R... Rck-iRb); R С R" =>• aR"ciR"
=>• аЯ"Ь. Таким образом, i? + с Д".

ТЕОРЕМА

Я* —

ДОКАЗАТЕЛЬСТВО

... R"ck-iR"b

=>


рефлексивное транзитивное замыкание R.
Упражнение 1.5.



Вычислить транзитивное замыкание заданного отношения можно следующим
образом:
Т1 — 1

д+ = [_|д« = I ]
г=1

г=1

п— 1

71 — 1

у[дМ = V [яГ-

г=1

г=1

Такое вычисление будет иметь сложность 0 ( п 4 ) .

1.5.2. Алгоритм Уоршалла
Рассмотрим алгоритм Уоршалла1 вычисления транзитивного замыкания отношения R на множестве М, \М\ = п, имеющий сложность 0 ( п 3 ) .
Алгоритм 1.11 Вычисление транзитивного замыкания отношения
Вход: отношение, заданное матрицей R: array[1..n, l..n] of 0..1.
Выход: транзитивное замыкание отношения, заданное матрицей
Т: array[l..n, l..n] of 0..1.
S: = R
for i from 1 to n do
for j from 1 to n do
1

Стсфап Уоршалл (p. 1935).

for к from 1 to n do
T{j,k]: = S\j,k] V S[j,i] к S[i,k]
end for
end for
S: = T

end for
На каждом шаге основного цикла (по г) в транзитивное замыкание добавляются такие пары элементов с номерами j и к (то есть T[j, к]: = 1), для
которых существует последовательность промежуточных элементов с номерами
в диапазоне 1 . . . г, связанных отношением R. Действительно, последовательность
промежуточных элементов с номерами в диапазоне 1 . . . г, связанных отношением R, для элементов с номерами j и к существует в одном из двух случаев:
либо уже существует последовательность промежуточных элементов с номерами
в диапазоне от 1 . . . (г — 1) для пары элементов с номерами j и к, либо существуют две последовательности элементов с номерами в диапазоне от 1 . . . (г — 1) —
одна для пары элементов с номерами j и г и вторая для пары элементов с номерами i и к. Именно это отражено в операторе T\j,k]:=S\j,k]
V S[j, г] к 5[г,/с].
После окончания основного цикла в качестве промежуточных рассмотрены все
элементы, и, таким образом, построено транзитивное замыкание.

ОБОСНОВАНИЕ

1.6. Функции
Понятие «функция» является одним из основополагающих в математике. В данном случае подразумеваются прежде всего функции, отображающие одно конечное множество объектов в другое конечное множество. Термин «отображение» мы считаем синонимом термина «функция», но различаем контексты употребления. Термин «функция» используется в общем случае и в тех случаях,
когда элементы отображаемых множеств не имеют структуры или она ни важна. Термин «отображение» применяется, напротив, только в тех случаях, когда структура отображаемого множества имеет первостепенное значение. Например, мы говорим «булева функция», по «отображение групп». Такое предпочтение слову «функция» оказывается в расчёте па постоянное сопоставление
читателем математического понятия функции с понятием функции в языках
программирования.

1.6.1. Функциональные отношения
Пусть / — отношение между А и В, такое, что
Va ((a, b) € f к (а, с) е f => b = с).
Такое свойство отношения называется однозначностью, или функциональностью,
а само отношение называется функцией из А в В, причём для записи используется одна из следующих форм:
f: А

В

или

А

В.

60

Глава 1. Множества и отношения

Если b = /(а), то а называют аргументом, a b — значением функции. Если из
контекста ясно, о какой функции идет речь, то иногда используется обозначение а ^ Ь. Поскольку функция является отношением, для функции / : А —> В
можно использовать уже введенные понятия: множество А называется областью
отправления, множество В — областью прибытия и
область определения функции:
область значений функции:

Def

Dom / = {а £ A\3b
Def

I m / = {ЬеВ\ЗаеА

£ В (6 = /(а))};
(b = f(a))}.

Область определения является подмножеством области отправления, Dom / с А,
а область значений является подмножеством области прибытия, Im / с В. Если
Dom / = А, то функция называется тотальной, а если Dom / ф А — частичной.
Сужением функции / : А —> В па множество М с А называется функция / | м .
определяемая следующим образом:
Def

/ | м = {(а, 6) | (а, 6) € / & а € М } = / П ( М х В).

Функция / называется продолжением д, если д является сужением / .
ОТСТУПЛЕНИЕ
И математике, как правило, рассматриваются тотальные функции, а частичные функции объявлены «ущербными». Программисты же имеют дело с частичными функциями,
которые определены не для всех допустимых значений. Например, математическая функция х2 определена для всех х, а стандартная функция языка программирования sqr даёт
правильный результат отнюдь не для всех возможных значений аргумента.

Далее, если явно не оговорено противное, речь идёт о тотальных функциях, поэтому области отправления и определения совпадают. Тотальная функция
/ : М —> М называется преобразованием над М. Функция f \ А\ х • • • х Ап
В
называется функцией п аргументов, или п-местной функцией. Такая функция
отображает кортеж ( a i , . . . , ап) Е А\ х • • • х Ап в элемент Ь е B,b — / ( ( a i , . . . , ап)).
При записи лишние скобки обычно опускают: b = f(a\,... ,a n ). Понятие функции удобно использовать для построения самых разнообразных математических
моделей.
Примеры
1. Всякому подмножеству А универсума U можно взаимно-однозначно сопоставить тотальную функцию 1д: U —> 0..1. Эта функция называется характеристической функцией подмножества и определяется следующим образом:
если а е А,
если а А.

61

1.6. Функции

Характеристическая функция результата операции над множествами легко
выражается через характеристические функции операндов:
1 лив = f max (1л, 1в),

1лпв = f min (1л, 1 в),
1А\в

min(U,l-lB).

Всякому отношению R между А и В (R с А х В) можно взаимпо-одпозпачио
сопоставить тотальную функцию 1д: А х В —> 0..1 (эта функция называется
характеристической функцией отношения), полагая
Def J1, если aRb,
R{a,b) = <
_
10, если aRb.
Характеристическая функция результата операции над отношениями легко
выражается через характеристические функции операндов:
lR-l(a,b)

= f 1я(6,а),

1д=*1-1д.

1.6.2. Инъекция, сюръекция и биекция
Пусть / : А —> В. Тогда функция / называется:
инъективной,
сюръективной,
биективной,

или инъекцией,
или сюръекцией,
или биещией,

если b — f(a\) & b — /(аг) => ai = а,2~,
е с л и У б е В (ЗаеА
(Ь — /(а)));
если она ииъективная и сюръективная.

ЗАМЕЧАНИЕ
Биективную функцию также называют взаимно-однозначной. Введенное в подразделе 1.2.2
взаимно-однозначное соответствие есть биекция.

Рисунок 1.3 иллюстрирует понятия отношения, функции, инъекции, сюръекции
и биекции.
Понятия инъективиости, сюръективности и тотальности применимы к любым
отношениям, а не только к функциям. Таким образом, получаем четыре парных
свойства отношения / с А х В, которые для удобства запоминания можно свести
в следующую таблицу.
А

в

Функциональность
Va £ A ((a, b) 6 f & (а, с) G / = > Ь = с)

Инъективность
V6 G В ((a, Ь) G / к (с, Ь) € /

Тотальность

Сюръективность

Vae А (3be в ((а,ь) е /))

Vbe в ( 3 а е А ((а,ь) е /))

а = с)

62

Глава 1. Множества и отношения

Отношение, но не функция


в

4

А


о0"
4

О

—'

Инъекция, но не сюръекция

4D
/—\

—X

Сюръекция, но не инъекция

Биекция

Рис. 1.3. Различные виды функций

Если f : А —> В — тотальная биекция, то отношение /
(обратная функция) является биекцией.

ТЕОРЕМА

1

с В х А

Поскольку / — биекция, имеем (b\ = f (а) k b2 = f{a) =>• Ь\ =
= f(ai) k b = f(a2) =>fl! = a2) k(Vb e В (За 6 A (b = /(a)))).

ДОКАЗАТЕЛЬСТВО

= Ь2) k(b

Покажем, что f~l — функция. Имеем f~l =f {(b, a) \ aeAkbeBkb
= /(a)} .
Пусть ai = / _ 1 (Ь) k a2 = f~l{b). Тогда b = / ( a i) kb = f(a2) = > ai = a 2 .
Покажем, что / - 1 — инъекция. Пусть a = / _ 1 (61) k а = / _ 1 (6г)- Тогда bi =
= /(a) k b2 = f ( a )
bi = b2. Покажем от противного, что / - 1 — сюръекция.
Пусть З а 6 А ( - 3 6 е В (а = /~ 1 (Ь))). Тогда З а € A (VbeB
(а^/"1^)))-1
Обозначим этот элемент ао. Имеем V6 ( а о т ^ / ( Ь ) ) =>• V6 (6 ф /(ао)) =>•
а0 & fA С А
а0 & А.


.Если / : А —• В — инъективная функция, то отношение f
является функцией (возможно, частичной), /-1: В —> А.
СЛЕДСТВИЕ

1.6.3. Образы и прообразы
Пусть / : А —• В и пусть А\ с А, В\ С 5 . Тогда множество
^ ( Л 1 ) ^ { б € В | З а е Ai (6 = /(а))}

1

сВ х А

63

1.6. Функции

называется образом множества А\ (при отображении / ) , а множество
F-^Bi)

=f{ae

A\3beBl

(b = f(a))}

называется прообразом множества В\ (при отображении / ) . Введём обозначения
/А •' = Dom / , /в : = Im / . Заметим, что F является отношением между множестваfA
ми 2 и 2 / в :
F = f { ( Л ь 5 i ) | Л1 С Л к Вх С В к S i = F ( A i ) } .
ТЕОРЕМА
l
в

и F~ : 2^

Если f : А —» В — функция, то F: 2fA —• 2?в (переход к образам)
(переход к прообразам) — тоже функции.

ДОКАЗАТЕЛЬСТВО

Упражнение 1.6.



ЗАМЕЧАНИЕ
Фактически, это означает, что функцию можно применять не только к элементам области
определения, а и к любым её подмножествам. На практике в целях упрощения записи для
обозначения применения функции к подмножеству используют ту же самую букву, что и
для применения функции к отдельному элементу.

1.6.4. Суперпозиция функций
Поскольку функции являются частным случаем отношений, для них определена
композиция. Композиция функций называется суперпозицией. Для обозначения
суперпозиции применяют тот же знак о, но операнды записывают в обратном
порядке: если f : А ^ В и g\ В
С, то суперпозиция функций / и g записывается так: g о f . Такой способ записи суперпозиции функций объясняется тем,
что обозначение функции принято писать слева от списка аргументов:
(fog)(x)^f(g(x)).
ТЕОРЕМА

Суперпозиция функций является функцией:
/: А ^ В k д: В

С => до / : А -> С.

Пусть b = (д о /)(а) и с = (до /)(а). Тогда b = g(f{a)) и с =
= g(f(a)). Но / и д функции, поэтому b = с.


ДОКАЗАТЕЛЬСТВО

1.6.5. Представление функций в программах
Пусть / : А —• В, множество А конечно и не очень велико, |Л| = п. Наиболее общим представлением такой функции является массив array [A] of В, где
А — тип данных, значения которого представляют элементы множества Л, а В —
тип данных, значения которого представляют элементы множества В. Если среда программирования допускает массивы только с натуральными индексами, то
элементы множества Л нумеруются (то есть Л = { a i , . . . , a n } ) и функция представляется с помощью массива array [l..n] of В. Функция нескольких аргументов
представляется многомерным массивом.

64

Глава 1. Множества и отношения

ОТСТУПЛЕНИЕ
Представление функции с помощью массива является эффективным по времени, поскольку реализация массивов в большинстве случаев обеспечивает вычисление значения
функции для заданного значения аргумента (индекса) за постоянное время, пе зависящее
от размера массива и значения индекса.

Если множество А велико или бесконечно, то использование массивов для представления функций является неэффективным с точки зрения экономии памяти.
В таком случае для представления функций используется особый вид процедур, возвращающих единственное значение для заданного значения аргумента.
Обычно такие процедуры также называются «функциями». В некоторых языках
программирования определения функций вводятся ключевым словом function.
Многоместные функции представляются с помощью нескольких формальных
параметров в определении функции. Свойство функциональности обеспечивается оператором возврата, часто обозначаемым ключевым словом return, который
прекращает выполнение тела функции и одновременно возвращает значение.
ОТСТУПЛЕНИЕ
В языке программирования Фортран и в некоторых других языках вызов функции и
обращение к массиву синтаксически неразличимы, что подчеркивает родственность этих
понятий.

1.7. Отношения эквивалентности
Различные встречающиеся на практике отношения могут обладать (или не обладать) теми или иными свойствами. Свойства, введенные в подразделе 1.4.6,
встречаются особенно часто (потому им и даны специальные названия). Более
того, оказывается, что некоторые устойчивые комбинации этих свойств встречаются настолько часто, что заслуживают отдельного названия и специального изучения. Здесь рассматриваются классы отношений, обладающих определённым
набором свойств. Такое «абстрактное» изучение классов отношений обладает тем
преимуществом, что, один раз установив некоторые следствия из наличия у отношения определённого набора свойств, далее эти следствия можно автоматически
распространить па все конкретные отношения, которые обладают данным набором свойств. Рассмотрение начинается отношениями эквивалентности (в этом
разделе) и продолжается отношениями порядка (в следующем разделе).

1.7.1. Классы эквивалентности
Рефлексивное симметричное транзитивное отношение называется отношением
эквивалентности. Обычно отношение эквивалентности обозначают знаком =.
Примеры
Отношения равенства чисел, равенства множеств являются отношениями эквивалентности. Отношение равномощности множеств также является отношением
эквивалентное™. Другие, более интересные примеры отношений эквивалентности, приведены в последующих главах книги.

65

1.7. Отношения эквивалентности

Пусть = — отношение эквивалентности на множестве М и х G М. Подмножество
элементов множества М, эквивалентных х, называется классом эквивалентности
для х:
[х]= =f {у G М \ у = х} .
Если отношение подразумевается, то нижний индекс у обозначения класса эквивалентности (знак отношения) обычно опускают.
ЛЕММА

1

\/а

ДОКАЗАТЕЛЬСТВО

ЛЕММА 2

([а] ф

а = а

а = b ==>• [А] =

ДОКАЗАТЕЛЬСТВО

ЛЕММА 3

е М

0).
а G [а].



[6].

Пусть а = Ь. Тогда х е [а]

а ф Ь ==> [А] П [6] =

х= а

х= Ь

х е[Ь].



0.

О Т противного: [а] П [Ь] Ф 0
Зс е М (с е [о] П [6]) = >
= > c G [a] &cG [Ъ] = > c = akc = b => a = cSzc = b => a = b, противоречие.

ДОКАЗАТЕЛЬСТВО



Если = — отношение эквивалентности на множестве М, то классы эквивалентности по этому отношению образуют разбиение множества М, причём
среди элементов разбиения нет пустых; и обратно, всякое разбиение Ъ = {Bi} множества М, не содержащее пустых элементов, определяет отношение эквивалентности на множестве М, классами эквивалентности которого являются элементы
разбиения.
ТЕОРЕМА

ДОКАЗАТЕЛЬСТВО

[ = > ] Построение требуемого разбиения обеспечивается следующим алгоритмом.
Вход: множество М, отношение эквивалентности = на М.
Выход: разбиение Ъ множества М наклассы эквивалентности.
Ъ : = 0 { вначале разбиение пусто }
for a G М do
for В G Ъ do
select b G В { берём представителя из В )
if a = b then
В \ = В + а { пополняем существующий класс эквивалентности }
next for а { переходим к рассмотрению следующего элемента из М }
end if
end for
Ъ: = Ъ и {{a}} { вводим новый класс эквивалентности }
end for

66

Глава 1. Множества и отношения

Def

[
] Положим а = Ь = Зг (а € Bi к Ь е Bi). Тогда отношение = рефлексивно,
поскольку М = U B i
Va е М (3г (a € Bi)) и а е В{
а е Bi к а е Bi
= • а = а. Отношение = симметрично, поскольку а = Ь = > 3 г ( a e B i k b e B i )
=>• Зг (b е Bi к а е Bi) =>• Ъ = а. Отношение = транзитивно, поскольку a =
= Ь к Ь = с = • [а] = [Ь] к [Ь] = [с] =>• [а] = [с] = • а = с.


1.7.2. Фактормножества
Если R — отношение эквивалентности на множестве М, то множество классов
эквивалентности называется фактормножеством множества М относительно эквивалентности R и обозначается M/R:
M/R

D

={[x)R}xeM.

Фактормножество является подмножеством булеана: M / R С 2 м . Функция
nat R: М
M/R называется отождествлением и определяется следующим образом:
nat R(x) =f [х] R.

1.7.3. Ядро функционального отношения
и множества уровня
Всякая функция / , будучи отношением, имеет ядро / о / _ 1 , которое является
отношением на области определения функции.
ЗАМЕЧАНИЕ
Даже если / — функция, / _ 1 отнюдь не обязательно функция, поэтому здесь о — знак
композиции отношений, а не суперпозиции функций.
Термин «ядро» применительно к функции / и обозначение ker / обычно резервируются для других целей, поэтому в формулировке следующей теоремы вместо
слова «функция» употреблен несколько тяжеловесный оборот «функциональное
отношение».
ТЕОРЕМА

Ядро функциональною отношения делятся
ности на множестве определения.

ДОКАЗАТЕЛЬСТВО

Пусть / : А
Dom / = А и 1 т / = В.

отношением эквивалент-

В. Достаточно рассматривать случай, когда

[Рефлексивность] Пусть а € А, Тогда 3Ь Ш В (Ь = / ( e ) )
(а, Ь) 6 ! к (Ь, а) S / ' U (а, а) 6 / о Г К

а 6 f=x{b)

[Симметричность] Пусть (а^вя) € / о / " 1 . Т о г д а З й (Ь = / ( щ ) к ag 6 / = 1 ( 6 ) )
^ € Г[(Ь) к b - / ( а а )
Ь - / Ы & «1 € Г 1 ( Ь ) ^
(a3,ai) 6 / о / " 1 .

^
^

67

1.8. Отношения порядка

Пусть (ai,a2) G / ° / 1 и (а2,аз) G / ° /
Это означает,
что ЗЬ! е В (bi = / ( a i ) к а 2 е Г Ч М ) и З Ь 2 е В (b2 = f ( a 2 ) к а 3 Е f ' 1 ^ ) ) .
Тогда bi = / ( a i ) к bi = f(a2) к b2 = f(a2) к b2 = /(03)
61 = b2. Положим
Ь\ — Ъ\ (или b: = 62). Тогда b = / ( a 1) & 6 = / ( a 3 )
b = / ( a i ) & a 3 € f'^b)
=•
[Транзитивность]

(ai,a3) G / o /

- 1

.



Пусть f : A
В — функция и / о / _ 1 — отношение эквивалентиости па Dom / .
Рассмотрим фактормножество D o m / / ( / о / - 1 ) . Класс эквивалентности (элемент
фактормножества) — это подмножество элементов А, которые отображаются в
один и тот же элемент b е В. Такие множества называются множествами уровня функции / . Ясно, что | D o m / / ( / о / - 1 ) | = | I m / | . Неформально множество
уровня функции / , соответствующее значению с, — это множество решений
уравнения f(x) = с.
Пример

Множество уровня 0 для функции sin(;r) — это 7rZ.

ОТСТУПЛЕНИЕ
Термин «множество уровня» опирается на очевидные геометрические ассоциации. Если
нарисовать график функции одной переменной в обычной декартовой системе координат и провести горизонтальную прямую на определённом уровне, то абсциссы точек
пересечения с графиком функции дадут множество уровня функции.
Пример Пусть задано множество М, \М\ = п. Рассмотрим функциональное
отношение Р между булеаиом 2м и множеством неотрицательных целых чисел
(мощность):
Р С 2м х 0..п,

где

Р: = {(X, к) \ X С М к к G 0..п к \Х\ = к} .

Тогда ядром такого функционального отношения является отношение равиомощности, а множествами уровня — семейства равномощных подмножеств.

1.8. Отношения порядка
В атом разделе определяются различные варианты отношений порядка. Отношение порядка позволяет сравнивать между собой различные элементы одного множества. Фактически, интуитивные представления об отношениях порядка уже были использованы при описании работы с упорядоченными списками
в подразделах 1.3.4=1.3.7.
1.8.1. Определения
Антисимметричное транзитивное отношение называется отношением порядка.
Отношение порядка может быть рефлексивным, и тогда оно называется отноше=
иием нестрото порядка. Отношение порядка может быть аптирефлексивпым, и
тогда оно называется отношением строюю порядка. Отношение порядка может
быть линейным, и тогда оно называется отношением линейною порядка, Отпоше-

68

Глава 1. Множества и отношения

иие порядка может не обладать свойством линейности, и тогда оно называется
отношением частичного порядка. Обычно отношение строгого порядка (линейного или частичного) обозначается знаком 3у е М (у -< х к у Ф х))).
Тогда Vx е М [Зу € М (у ^ х)) => 3 (и»)~ х (Vi (щ+1 -< щ) к ui+1 ф щ). Поскольку \М\ < оо, имеем Зг, j (г < j к щ = Uj). Но по транзитивности

ДОКАЗАТЕЛЬСТВО

Щ >- Щ+1 У • • • У Uj =>• Щ+1 >- Uj = щ.
Таким образом, щ+\ -< щ к щ+i У щ => щ+i = щ — противоречие.



69

1.8. Отношения порядка

ЗАМЕЧАНИЕ

Линейно упорядоченное конечное множество содержит ровно один минимальный элемент, а в произвольном конечном частично упорядоченном множестве их может быть
несколько.

ТЕОРЕМА 2 Всякий частичный порядок на конечном множестве может быть дополнен до линейного.
ДОКАЗАТЕЛЬСТВО

СМ.

следующий подраздел.



ЗАМЕЧАНИЕ

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

1.8.3. Алгоритм топологической сортировки
Рассмотрим алгоритм дополнения частичного порядка до линейного на конечном
множестве.
Алгоритм 1.12 Алгоритм топологической сортировки
Вход: конечное частично упорядоченное множество U.
Выход: линейно упорядоченное множество W.
while U Ф 0 do
га: = min(U) { функция min возвращает минимальный элемент }
yield т { включаем элемент т в множество W }
U : = U - т { элемент т более не рассматривается }
end while
Всякая процедура, генерирующая объекты с помощью оператора yield, определяет линейный порядок на множестве своих результатов. Действительно, линейный порядок — это последовательность, в которой объекты
генерируются во время работы процедуры.

ОБОСНОВАНИЕ

Функция min возвращает минимальный элемент, существование которого гарантируется теоремой 1 подраздела 1.8.2.
Вход: конечное частично упорядоченное множество U.
Выход: минимальный элемент га.
select га е U { выбираем любой элемент в качестве кандидата в минимальные}
for и £ U do
if и -< га then
т : = и { меняем кандидата в минимальные }
end if
end for
return m { элемент га минимальный }

70

Глава 1. Множества и отношения

ОБОСНОВАНИЕ
Рассмотрим последовательность элементов, которые присваивались т во время работы min. Эта последовательность не может быть бесконечной,
и она линейно упорядочена. Рассмотрим последний элемент этой последовательности. Этот элемент т — минимальный. Действительно, от противного, пусть
существует и^ткифтииие
входит в последовательность. Тогда по транзитивности и меньше любого члена последовательности, и он был бы включен в
последовательность в момент своего рассмотрения.


ЗАМЕЧАНИЕ
Если отношение порядка представлено матрицей, то функцию min можно реализовать,
например, так — найти в матрице отношения первую строку, содержащую только нули.

1.8.4. Верхние и нижние границы
Пусть X с М — подмножество упорядоченного множества М с отношением порядка
Элемент т е М называется нижней границей для подмножества X,
если Wx е X (т -< х). Элемент т е М называется верхней границей для подмножества X, если Vx е X (х -< т). Верхние и нижние границы не обязаны
существовать для любого множества и если существуют, то не всегда единственны. Если существует наибольшая нижняя граница, то она называется инфимумом
и обозначается inf(X). Если существует наименьшая верхняя граница, то она
называется супремумом и обозначается sup(X).
Пример Рассмотрим множество рациональных чисел Q с обычным отношением порядка < и его подмножество X: = {х е Q | х > 0 к х2 > 2}. Тогда
е X,
а ^ является одной из нижних границ множества X. Инфимума это множество
пе имеет.

1.8.5. Монотонные функции
Пусть А и В — упорядоченные множества и / : А —> В. Тогда если
ai -< a 2 к ai ф а2 ==• f{ai)

-< / ( a 2 ) V / ( a i ) = / ( a 2 ) ,

то функция / называется монотонно возрастающей. Если
ai -< a 2 к ai Ф а2 ==• / ( a 2 ) -< / ( a i ) V f(ai)

= /(а2),

то функция / называется монотонно убывающей. Если
ai -< а2 к а\ Ф а,2 =•

f(m)

•< / ( a 2 ) к f(ai)

Ф /(a2),

то функция / называется строго монотонно возрастающей. Если
а{ ~< а2 к ai ф а2 = • / ( a 2 ) -< / ( a i ) к / ( a i ) ф / ( а 2 ) ,

то функция / называется строго монотонно убывающей. Монотонно возрастающие и убывающие функции называются монотонными, а строго монотонно возрастающие и убывающие функции называются строго монотонными соответственно. Очевидно, что строго монотонная функция монотонна, но обратное
неверно.

71

1.8. Отношения порядка

Примеры
1. Тождественная функция у = х для чисел является строго монотонно возрастающей, а функция знака числа sign(x) = f if х < 0 then - 1 elseif х > 0 then
1 else 0 end if является монотонно возрастающей.
2. Пусть 2м — булеан над линейно упорядоченным конечным множеством М,
а частичный порядок на булеапе — это включение. Тогда функция min(X),
X с М из алгоритма 1.12, доставляющая минимальный элемент, является
монотонно убывающей, но не строго монотонной.
3. Пусть порядок на булеапе 2м — это собственное включение. Тогда функция,
которая сопоставляет подмножеству X с М его мощность, X
\Х\, является
строго монотонно возрастающей.

1.8.6. Вполне упорядоченные множества
Частично упорядоченное множество X называется вполне упорядоченным, если
любое его непустое подмножество имеет минимальный элемент. В частности,
для любых двух элементов a,b е X один из них обязан быть минимальным
в подмножестве {а, 6}, а значит, вполне упорядоченное множество упорядочено
линейно.
ЗАМЕЧАНИЕ
Не надо путать вполне упорядоченные множества и множества, на которых определён линейный (или полный) порядок. Линейно упорядоченное множество может не быть вполне
упорядоченным.

Примеры
1. Всякое конечное линейно упорядоченное множество вполне упорядочено.
2. Множество натуральных чисел N с обычным отношением порядка вполне
упорядочено.
3. Множество рациональных чисел Q с обычным отношением порядка не является вполне упорядоченным, так как множество X : = { z e ( Q ) | x 2 > 2 } , равно
как и само множество Q, не имеет минимального элемента.
4. Множество вещественных чисел М с обычным отношением порядка не является вполне упорядоченным, так как множество X : = {х £ К | х > 0}, равно как
и само множество Е, не имеет минимального элемента.
Говорят, что два линейно упорядоченных множества А и В изоморфны (обозначение А ~ В), если между ними существует взаимио-одпозпачное соответствие,
сохраняющее порядок:
А ~ В =Г \А\ = |Я| &(Vai,a 2 Е А (аг -< а2 к ах

bi к а2

Ь2 ==> Ьх -< Ь2)).

Другими словами, два линейно упорядоченных множества Aw В изоморфны, если между ними существует строго монотонно возрастающее взаимно-однозначное
соответствие.

72

Глава 1. Множества и отношения

ЗАМЕЧАНИЕ
Поскольку вполне упорядоченные множества упорядочены линейно, понятие изоморфизма применимо и к вполне упорядоченным множествам.

Пример Множества натуральных чисел и чётных чисел с обычным порядком < изоморфны, поскольку соответствие п у-> 2п является строго монотонно
возрастающим.

1.8.7. Индукция
Важность вполне упорядоченных множеств определяется тем, что для них можно
обобщить принцип индукции, применяемый обычно для множества натуральных
чисел.
Т Е О Р Е М А (Индукция по вполне упорядоченному множеству) Пусть X — вполне
упорядоченное множество их о — его минимальный элемент, а Р — некоторый предикат, зависящий от элементов X. Тогда если

Р(х 0 ) k Vxi е X ((Vx е X (х •< xi

Р(х)))

Р(хО),

то
WxeX

(Р(х)).

Обозначим Р: = {х е X \ Р(х)}, Р с X. Далее от противиого.
Пусть Р Ф 0 . Поскольку X вполне упорядочение, Р имеет минимальный элемент, обозначим его х\. Тогда Vx € X (х -< х\ =$> Р{х)) по выбору х\ и значит
Р{хi) по условию теоремы, что противоречит выбору х\.


ДОКАЗАТЕЛЬСТВО

ЗАМЕЧАНИЕ
Обычная математическая индукция соответствует индукции по вполне упорядоченному
множеству натуральных чисел N.

Индукция по вполне упорядоченному множеству сильнее обычного принципа
математической индукции в силу следующей замечательной теоремы.
ТЕОРЕМА

Любое множество может быть вполне упорядочено.

Данное утверждение эквивалентно так называемой аксиоме выбора в теории множеств и само может быть принято за аксиому. Мы опускаем доказательство
эквивалентности этой теоремы аксиоме выбора.

73

Комментарии

Пример

Рассмотрим множество положительных рациональных чисел

где т и п взаимно просты.
Определим отношение -< на множестве Q+ следующим образом:
Ш1

Ш

2

Def

^

. . ,

р

х

— -< — = mi < т2 V (mi = т2 & п\ < п2),
п1
п2
где < — обычное отношение порядка на N. Нетрудно видеть, что множество Q+
с отношением -< является вполне упорядоченным, в то время как с обычным
отношением порядка < оно таковым пе является, см. 1.8.6.

1.8.8. Алфавит, слово и язык
В этом подразделе вводятся некоторые термины, которые пе имеют прямого отношения к теории множеств, но часто используются в различных приложениях
и в следующих главах, а потому рассматриваются в первой главе. Пусть задано
конечное множество А = { a i , . . . , ап}, которое называется алфавитом. Элементы алфавита называются буквами, или символами. Обычно отдельные символы
обозначаются начальными буквами латинского алфавита. Конечная последовательность букв называется словом (в данном алфавите), или цепочкой. Буквы в
слове линейно упорядочены (слева направо) и могут быть перенумерованы. Одна буква может входить в слово несколько раз, каждый отдельный экземпляр
буквы в слове называется вхождением буквы в слово. Вхождения могут быть
идентифицированы, например, номером буквы в слове. Обычно слова обозначаются начальными буквами греческого алфавита. Множество слов в алфавите А.
обозначается А*. Если слово а =
... ak G А*, то количество букв в слове называется длиной слова: |а| = \а\... ак\ = к. Пустое слово обозначается е, |е| = f О,
е А, но е 6 А*. Если пустое слово исключается из рассмотрения, то множество
слов в алфавите А обозначается А+. Таким образом, А* =
А+ = А* -£. Для
слов определена операция конкатенации, или сцепления. Конкатенацией слов с* и
/3 является слово а(3, полученное выписыванием подряд сначала всех букв слова
а, а потом всех букв слова (3. Обычно операция сцепления никак не обозначается. Если а = aict2, то a i называется началом, или префиксом, слова а, а а2 —
окончанием, или постфиксом, слова а. Если при этом а.\ Ф £ (соответственно,
а2 ф е), то a i (соответственно, а2) называется собственным началом (соответственно, собственным окончанием) слова а. Произвольное множество L слов в
некотором алфавите называется языком в этом алфавите, L с А*.

Комментарии
Основные сведения, изложенные в этой главе, можно найти в любом учебнике по (дискретной) математике. Алгоритм 1.1 тривиален. Алгоритмы 1.2 и 1.3
описаны в [8]. Алгоритмы 1.4-1.7 — общеизвестный программистский фольклор. Автору неизвестны другие публикации алгоритмов 1.8-1.10, несмотря на

74

Глава 1. Множества и отношения

их очевидность. Алгоритм 1.11 описан во многих источниках, например, в [2].
Алгоритм 1.12 описан в фундаментальной книге [14], которая входит в «золотой
список» обязательного чтения любого программиста.

Упражнения
1.1. Существует ли множество всех множеств?
1.2. Доказать, что A U В = (А П В) U (А П В) U (А П В).
1.3. Доказать, что Q(2k + га) = Q(2к - тп) для 0 < га < 2к - 1, где Q — функция
из алгоритма 1.3.
1.4. Пусть Q = f {(га, п) | m, п е N к га = п 2 }. Какими свойствами обладает отношение Q?
1.5. Доказать вторую теорему из подраздела 1.5.1.
1.6. Доказать теорему из подраздела 1.6.3.
1.7. Доказать, что если = — отношение эквивалентности на конечном множестве
М и \М\ = IМ/ = |, то Vx е М (|[х] = | = 1).
1.8. Пусть А — линейно упорядоченное множество с отношением порядка R.
Введем отношение R на множестве кортежей элементов из А следующим
образом:
(ах,... ,am)R(bi,...

Def

,bn) = (т^п

kVi

6 1 ..га (а* =

V (Зг G l..m ((aiRbi к V j € 1..г - 1 (а* = bj)))).
Такое отношение называется лексикографическим, или алфавитным, порядком. Доказать, что алфавитный порядок есть линейный порядок на множестве кортежей А + = f U S i ^ •

Глава 2

Алгебраические
структуры

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

2.1. Алгебры и морфизмы
Словом «алгебра» называют, вообще говоря, не только раздел математики, но и
один из конкретных объектов, изучаемых в этом разделе. Поскольку «алгебры» в
узком смысле здесь не рассматриваются, для краткости и без риска возникновения недоразумений слово «алгебра» в этом учебнике используется как родовое
понятие для обозначения разнообразных алгебраических структур.

2.1.1. Операции и их носитель
Всюду определённая (тотальная) функция М называется п-арной
(п-местной) операцией на М. Если операция Вf — изоморфизм, то алгебры А и 23 называют изоморфными и обозначают так: А ~ Ъ. Если / ясно из контекста или просто неважно в конкретном
рассуждении, то пишут А ~ Ъ.
Отношение изоморфизма на множестве однотипных алгебр являет ся эквивалентностью.

ТЕОРЕМА 2

ДОКАЗАТЕЛЬСТВО

[ Рефлексивность ]

А

г

~

А, где / — тождественное отображение.

/
[ Симметричность ] А ~ Ъ

Ъ

/_1
~
А.

[ Транзитивность ] А ~ Ъ к Ъ ~ 9 = $ > А

9

~ 5 .



Примеры
1. Пусть А = (N; +), Ъ = ({n | п = 2k, к е N} ; +) — чётные числа. Тогда А х ~2 Ъ.
2. А = ( 2 м ; П, U) ~ Ъ = ( 2 м ; U, П>, f ( X ) = X.

3. А — (К+; •)

Ъ = (М; +).

81

2.3. Алгебры сдвумяоперациями

Понятие изоморфизма является одним из центральных понятий, оправдывающих применимость алгебраических методов в различных областях. Действительг
но, пусть Л = (А;£ М],
замкнутое относительно суперпозиции, является полугруппой.
Если в полугруппе существует система образующих, состоящая из одного элемента, то такая полугруппа называется циклической.

82

Глава 2. Алгебраические структуры

Пример (N;+) является циклической полугруппой, поскольку {1} является
системой образующих.

2.2.2. Определяющие соотношения
Пусть Р = (М; *) — полугруппа с конечной системой образующих А,АеМ,А
= { а ь . . . ,о„}. Тогда
\Лт G М (3yi,...,yk

€ А {х =

=

у1*...*ук)).

Если опустит!» обозначение операции *, то всякий элемент а € М можно представить как слово о; в алфавите А, то есть М с А+. Обозначим через а элемент,
определяемый словом а. Слова а и (3 могут быть различными, но соответствующие им элементы fv и j3 могут быть равны: а = (3, а,(3 е А+, а,(3 е М. Такие
равенства называются определяющими соотношениями. Если в полугруппе нет
определяющих соотношений и все различные слова, составленные из образующих, суть различные элементы носителя, то полугруппа называется свободной.
Всякая конечно-порождённая полугруппа может быть получена из свободной
введением определяющих соотношений. Пусть в конечно-порождённой полугруппе некоторый элемент а определяется словом а, причём а =
и задано
определяющее соотношение 7 = а. Тогда вхождение слова 7 в слово а можно заменить словом а, причём полученное слово (Заб будет определять тот же
самый элемент а. Такое преобразование слова будем называть применением определяющего соотношения. Два слова в алфавите А считаются равными, если одно
из другого получается применением определяющих соотношений, то есть слова
равны, если равны определяемые ими элементы. Отношение равенства слов в полугруппе с определяющими соотношениями является отношением эквивалентности. Классы эквивалентности по этому отношению соответствуют элементам
полугруппы.
Примеры
1. В полугруппе (N; +) имеется конечная система образующих {1}. Другими словами, каждое натуральное число можно представить как последовательность
знаков 1. Очевидно, что различные слова в алфавите {1} суть различные
элементы носителя, то есть эта полугруппа свободна.
2. Пусть полугруппа У задана системой двух образующих {а, 6} и двумя определяющими соотношениями, аа = а и ЬЪ = Ь. Следующий элементарный алгоритм определяет, равны ли два слова, а и /3, в полугруппе Т.
Вход: входные слова а : array [l..s] of {a,b} и (3 : array [1 ..t] of {a, 6};
Выход: значение выражения a = (3 в полугруппе У.
if a[l] Ф (3[ 1] then
return false { первые буквы не совпадают }
end if
Na := 0 { счётчик изменений буквы в а }
for i from 2 to з do
if a[i] Ф a[i - 1] then

83

2.3. Алгебры сдвумяоперациями

Na := Na + 1 { буква изменилась }
e n d if
end for
N/з : = 0 { счётчик и з м е н е н и й буквы в @ }
for г from 2 to t do
if fi[i) ф p\i - 1] t h e n
Np := Np + 1 { буква изменилась }
e n d if
end for
r e t u r n Nn = Np { слова равны, если з н а ч е н и я счётчиков одинаковы }
В предыдущем примере о п р е д е л я ю щ и е соотношения таковы, что равенство любых слов как элементов легко проверяется. О д н а к о это не всегда так.
(Марков 1 -Пост 2 ) Существует
равенства слов алгоритмически

ТЕОРЕМА

знавания

ДОКАЗАТЕЛЬСТВО

полугруппа, в которой проблема
неразрешима.

распо-

( Б е з доказательства).



ЗАМЕЧАНИЕ
Термин «алгоритмическая неразрешимость» принадлежит теории алгоритмов, которая не
рассматривается в этом учебнике, а потому строгое определение этого термина здесь
не приводится. Неформально можно сказать, что проблема называется алгоритмически
неразрешимой, если не существует программы (алгоритма) её решеиия. Здесь словосочетание «не существует» означает не то, что программа ещё не составлена, а то, что
требуемая программа не может быть составлена в принципе. В теории алгоритмов строго
установлено, что алгоритмически неразрешимые проблемы существуют. Приведём простое наблюдение, которое не является строгим доказательством последнего утверждения,
но может служить косвенным намёком на причины существования алгоритмически неразрешимых проблем. Пусть в конечном алфавите А задано слово А, А 6 А* и язык L, L С А*.
Проблема: определить, принадлежит ли слово А языку L? Обозначим через PL{OL) программу, которая для заданного слова А € А* выдаёт 1, если А € L, и выдаёт 0 в противном
случае. Множество всех программ не более чем счётно (просто потому, что всякая программа — это слово в конечном алфавите). В то же время множество всех языков несчётно,
потому что это множество всех подмножеств счётного множества. Таким образом, заведомо существуют языки, для которых не существует программы, распознающей все слова
этого языка. Приведённое наблюдение не является доказательством, потому что мы не
определили, как именно задаются объекты a, L и PL(Q:).
П р и м е р Г. С. Ц е й т и н 3 нашел легко о п и с ы в а е м ы й п р и м е р полугруппы, в которой проблема равенства слов алгоритмически неразрешима. В этой полугруппе
всего пять образующих {а, 6, с, d, е} и семь о п р е д е л я ю щ и х соотношений:
ас = са;

ad = da;

be = cb\

bd = db\

1

Андрей Андреевич Марков (1903-1979).

2

Эмиль Леон Пост (1897-1954).

3

Григорий Самуилович Цейтип (р. 1937).

abac = abace;

eca — ae\

edb = be.

84

Глава 2. Алгебраические структуры

Тем не менее невозможно составить программу, которая бы для любых заданных
слов в алфавите {а,6, с, d, е} проверяла, можно ли преобразовать одно слово в
другое применением указанных определяющих соотношений.
ОТСТУПЛЕНИЕ
Некоторые программисты полагают, что если в условиях задачи всё дискретно и конечно,
то для решения такой задачи программу можно составить в любом случае (используя метод «полного перебора»). Предшествующие теорема и пример показывают, что это мнение
ошибочно.

2.2.3. Моноиды
Моноид — это полугруппа с единицей:
З е (Va (а * е = е * а = а)).

ЗАМЕЧАНИЕ
Единицу также называют нейтральным элементом.

Примеры
1. Множество слов А* в алфавите А вместе с пустым словом е образует моноид.
2. Пусть Т — множество термов над множеством переменных V и сигнатурой Е.
Подстановкой, или заменой переменных, называется множество пар
Ст =

{ti//Vi}i£j,

где U — термы, а Vi — переменные. Результатом применения подстановки а
к терму t (обозначается ta) называется терм, который получается заменой
всех вхождений переменных Vi соответствующими термами U. Композицией подстановок а\ = {U//vi}i£i
и
= {tj//vj}jGj
называется подстановка
(7i о а2

{tk//vk}keK,

где К = IU J , а
{исг2,
tj,

если к е / ,
если к £ I.

Множество подстановок образует моноид относительно композиции, причём
тождественная подстановка {vi//vi} является единицей.
ТЕОРЕМА 1

Единица моноида единственна.
Пусть существуют две единицы: ei,e2- Тогда е\ * е2 = е\ к, е\ *
е\ = е2.


ДОКАЗАТЕЛЬСТВО

* е2 = е2

2.3. Алгебры сдвумяоперациями

85

ТЕОРЕМА 2 Всякий моноид над М изоморфен некоторому моноиду преобразований над М.
Пусть М = (М; *) — моноид над М = {е, а, Ь, с, . . . } . Построим
Э' = (F; о) — моноид преобразований над М, где
F: = {fm: Af-> М | fm(x): = х * т}теМ ,

ДОКАЗАТЕЛЬСТВО

а о — суперпозиция функций, h: М —»• F, /г(га): = / т . Тогда — моноид, поскольку суперпозиция функций ассоциативна, / е — тождественная функция (так как
f e ( x ) = х * е = х ) и F замкнуто относительно о, так как f a ° f b =
fa*bfa*b(x)
= х * (а * b) = (х * а) * b = f a ( x ) * 6 = f b ( f a { x ) ) . Далее, /г — гомоморфизм,
так как /г(а * Ь) = /а*ъ — fa ° fb — h(a) о /г(Ь). И наконец, h — биекция, поскольку h — сюръекция по построению, и h — инъекция (так как (/ а (е) = е * а =
- а & /ь(е) = е * Ь = Ь ) ^ { а ф Ь = > / а ф / ь )).


2.2.4. Группы
Теория групп, некоторые положения которой рассматриваются в этом подразделе, является ярчайшим примером мощи алгебраических методов, позволяющих получить из немногих базовых понятий и аксиом множество важнейших
следствий. Группа — это моноид, в котором
Va ( З а - 1 (а * а - 1 = а - 1 * а — е)) .
Элемент а"1 называется обратным, а операция * называется умножением.
ЗАМЕЧАНИЕ

Так как операция умножения в группе пе обязательно коммутативна, то, вообще говоря,
свойства a - 1 * а = е и а * а - 1 = е пе равносильны. Можно было бы различать обратные
слева и обратные справа элементы. Введенная аксиома требует существования двустороннего обратного элемента. Можно показать, что она следует из более слабых аксиом
существования левой единицы и левого обратного элемента.

Мощность носителя G группы S называется порядком группы и обозначается |G|.
Примеры
1. Множество невырожденных квадратных матриц порядка п образует группу
относительно операции умножения матриц. Единицей группы является единичная матрица (единицы на главной диагонали, остальные элементы равны
нулю). Обратным элементом является обратная матрица.
2. Множество перестановок на множестве М, то есть множество взаимно однозначных функций / : М —у М, является группой относительно операции суперпозиции. Единицей группы является тождественная функция, а обратным
элементом — обратная функция.

86

Глава 2. Алгебраические структуры

ТЕОРЕМА 1

Обратный элемент единственен.
Пусть а * а - 1 = а - 1 *a = e&ca*b

ДОКАЗАТЕЛЬСТВО
= а

- 1

* е = а

ТЕОРЕМА 2

- 1

= b*a = е. Тогда а - 1 =

* ( а * Ь) = ( а - 1 * а ) * Ь = е * 6 = 6.



В любой группе выполняются следующие соотношения:

1. (а * б) - 1

•а"1.

2. а * Ь = а * с => Ь = с.
3. b * а = с * а
1

b — с.

1

4. (а" )" = а.
ДОКАЗАТЕЛЬСТВО

[ 1 ] (а * b) * (lrl * сГ 1 ) = а * (b *

* а " 1 = а * е * а""1 = а * а " 1 = е.

[ 2 ] 6 = е * Ь ~ ( а ' 1 * а) к b — а~ 1 * (а * 6) = а~1 * (а * с) = (а" 1 * а ) * с = е * с — с.
[ 3 ] Ь = Ь*е = 6 * ( а * о" 1 ) ~ (Ь * о) * а " 1 = (с * а) * а " 1 = с * (а * а" 1 ) = с * е — с.
[ 4 ]

а~1 * а = е.



В группе можно однозначно решить уравнение
а * х = b {решение: х = а - 1 * 6).

ТЕОРЕМА 3

ДОКАЗАТЕЛЬСТВО

==i> е * ж = а

-1

а*х

= b =Ф- а

- 1

* ( а * Я) = а

- 1

* 6



- 1

* а) * ж = а

- 1

* Ь = >

1

* 6 ==> х = а~ * Ь.



Коммутативная группа, то есть группа, в которой
Va, b (a * b = b * a),
называется абелевойВ абелевых группах обычно приняты следующие обозначения: групповая операция обозначается +, обратный элемент к а обозначается -а,
единица группы обозначается 0 и называется нулем или нейтральным элементом.
Примеры
1. (Z; +) — множество целых чисел образует абелеву группу относительно сложения. Нейтральным элементом группы является число 0. Обратным элементом
_ 1 Def
является число с противоположным знаком: х 1 = —х.
2. (Q+;-) — множество положительных рациональных чисел образует абелеву
группу относительно умножения. Нейтральным элементом группы является
число 1. Обратным элементом является обратное число: (га/п) - 1 =
1

Нильс Хеирик Абель (1802-1829).

п/т.

87

2.3. Алгебры сдвумяоперациями

3. ( 2 м ; А) — булеан образует абелеву группу относительно симметрической разности. Нейтральным элементом группы является пустое множество 0 . Обрат_1

пым элементом к элементу х является оп сам: х

Def

= х.

2 . 2 . 5 . Группа п е р е с т а н о в о к
В этом подразделе рассматривается одна из важнейших групп, называемая группой перестановок, или симметрической группой. Биективная функция / : X —• X
называется перестановкой множества X.

ЗАМЕЧАНИЕ

Если множество X конечно (|Л"| = п), то, не ограничивая общности, можно считать,
что X = 1 ..71, В этом случае перестановку / : 1.лг —• 1..п удобно задавать таблицей из
двух строк. В первой строке — значения аргументов, во второй — соответствующие значения функции. Такая таблица называется подстановкой. В сущности, перестановка и
подстановка — синонимы.

Пример

/=

1
5

2
2

3 4
1 4

Произведением перестановок fug
< •

1

5
3

2 3
1 2

9 = 4

4
3

5
5

(обозначается f g ) называется их суперпозиция

Пример
1

fg = 5

2 3
1 4

4
3

5
2

ТЬждественная перестановка — это перестановка е, такая, что е(х) = х.

Пример
е =

1
1

2
2

3
3

4
4

5
5

Обратная перестановка — это обратная функция, которая всегда существует,
поскольку перестановка является биекцией.

ЗАМЕЧАНИЕ
Таблицу обратной подстановки можно получить, если просто поменять местами строки
таблицы исходной подстановки.
Пример

/ =

1
3

2
4

3
2

4
1

5
5

3
1

4
2

2
3

1
4

5
5

1
4

2
3

3 4
1 2

5
5

88

Глава 2. Алгебраические структуры

Таким образом, поскольку суперпозиция функций ассоциативна, а единичный и
обратный элементы существуют, множество перестановок n-элементиого множества образует группу относительно операции суперпозиции. Эта группа называется симметрической степени п и обозначается Sn.

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

2.3.1. Кольца
Кольцо — это множество М с двумя бинарными операциями + и * (они называются сложением и умножением соответственно), в котором:
1.
2.
3.
4.

(а + Ь) + С=: а + {Ь + с)
30 ем (V а (а + 0 = 0 + а = а))
Va (3 - а ( а + ( - а ) = 0))
а + b — b +а

5. а * (b * с) = (а*Ь) * с
6. a* (b + с) == (а * Ъ) + (а * с)
(а + Ь) * с = (а * с) + (6 * с)

сложение ассоциативно.
существует нуль.
существует обратный элемент.
сложение коммутативно, то есть
кольцо — абелева группа по сложению.
умножение ассоциативно, то есть
кольцо — полугруппа по умножению.
умножение дистрибутивно относительно
сложения слева и справа.

Кольцо называется коммутативным, если
7. а*Ь = 6 * а
умножение коммутативно.
Кольцо называется кольцом с единицей, если
8. 31 е М (а*1 = 1*а = а)
существует единица, то есть кольцо
с единицей — моноид по умножению.
ТЕОРЕМА

В кольце выполняются следующие соотношения:

1. 0 * а = а * 0 = 0.
2. а * (—Ь) = (—а) * Ъ = —(а * Ь).

3. (—а) * (—Ь) = а*Ь.
4. (—а) = а * (—1).

5. - ( а + 6) = (—а) + (—Ь).
6. а ф 0

( а " 1 ) - 1 = а.

89

2.3. Алгебры с двумя операциями

ДОКАЗАТЕЛЬСТВО

[ 1 ] 0 * а = (0 + 0) * а = (0 * а) + (0 * а)
- ( 0 * а) + (0 * а) = - ( 0 * а) + ((0 * а) +
+ (0 * а)) = ( - ( 0 * а) + (0 * а)) + (0 * а)
0 = 0 + (0 * а) = 0 * а.
[ 2 ] (а * ( - 6 ) ) + (а * Ь) = А * ( - 6 + Ъ) = А * 0 = О,
(а * Ь) + ( ( - а ) * Ь) = (а + ( - а ) ) *6 = 0*Ь = 0.
[ 3 ] (-а) * (-6) = - ( а * (-6)) = - ( - ( а

*Ь))=А*Ь.

[ 4 ] (а * ( - 1 ) ) + а = (а * ( - 1 ) ) + (а * 1) = а * ( - 1 + 1) = а * 0 = 0.
[ 5 ] (а + 6) + ( ( - а ) + ( - 6 ) ) = (а + Ь) + ((-6) + ( - а ) ) = а + (Ъ + ( - 6 ) ) + ( - а ) =
= а + 0 + ( - а ) = а + ( - а ) - 0.
[ 6 ] а - 1 *а = 1.



Пример (Z;+,*) — коммутативное кольцо с единицей. Кроме того, V?i
( ( Z n ; + , *)) — коммутативное кольцо с единицей. В частности, машинная арифметика целых чисел (Z 2 is; +, *) — коммутативное кольцо с единицей.

2.3.2. Области целостности
Если в кольце для некоторых ненулевых элементов х, у выполняется равенство
х * у = 0, то х называется левым, а у — правым делителем нуля.
Пример

В машинной арифметике (Z2ie; +, *) имеем 256*128 = 2 8 *2 7 = 21Г) = 0.

Заметим, что если в кольце нет делителей нуля, то Vz Ф 0,у Ф 0 ( х * у фО).
В группе V а, 6, с ((а * Ь = а * с => b = с) & ( б * а = с * а
Ь = с)), однако в произвольном кольце это не так.
Пример В машинной арифметике (Z 2 is; +, *) имеем 2 8 * 2 7 = 0 и 0 * 2 7 = 0, но
0 ф 2 8 = 256.
ТЕОРЕМА

Va ф 0,6, с ((а* 6 = a * с

b = с) &(ft*a = c * a =4> b = с)) «$=•

ДОКАЗАТЕЛЬСТВО

[
] От противного. Пусть За; ^
/ 0 (ж * у = 0). Тогда
= 0 & ж * 0 = 0 = * г / = 0.
[
] 0 = (а*Ь) + (—(а*Ь)) = (а*Ь)+(-(а*с)) = {а*Ь) +(а*(-с))
а* (b+ (—с)) = 0 &: а Ф 0 = > b + (—с) = 0
b = с.

=
= а*(Ь+(-с)),


Коммутативное кольцо с единицей, не имеющее делителей нуля, называется
областью целостности.
Пример Целые числа (Z; +, *) являются областью целостности, а машинная
арифметика (Z 2 is;+,*) — не является.

90

Глава 2. Алгебраические структуры

2.3.3. Поля
Поле — это множество М с двумя бинарными операциями + и *, такими, что:
1.
2.
3.
4.
5.
6.
7.
8.

(а + Ь) + с = а + (Ь + с)
сложение ассоциативно.
30 е М (а + 0 = 0 + а = а) существует нуль.
Va (3 - а (а 4- - а = 0))
существует обратный элемент по сложению.
а+ b= Ь+а
сложение коммутативно, то есть поле — абелева
группа по сложению.
а* (Ь* с) = (а*Ь) * с
умножение ассоциативно.
31 е М ( a * l = l * a = a) существует единица.
Va ф 0 ( З а - 1 ( а - 1 * а = 1)) существует обратный элемент по умножению.
a *6 = 6*а
умножение коммутативно, то есть ненулевые элементы образуют абелеву группу по умножению.

9. а * (6 + с) = (a * Ь) + (а * с)

умножение дистрибутивно
относительно сложения.

Таким образом, поле — это коммутативное кольцо с единицей, в котором каждый
элемент, кроме нейтрального элемента по сложению, имеет обратный элемент по
умножению.
Примеры
1. (IR; +, *) — поле вещественных чисел.
2. (Q; +, *) — поле рациональных чисел.
Def

3. Пусть Е2 = {0,1}. Определим операции +, •: Е2 х Е2 -+ Е2 следующим образом: 0 0 = 0 1 = 1 0 = 0, 1 1 = 1 (конъюнкция), 0 + 0 = 1 + 1 = 0,
Def
0 + 1 = 1 + 0 = 1 (сложение по модулю 2). Тогда Ъ2 = (Е2-,+,-) является
полем и называется двоичной арифметикой. В двоичной арифметике нуль —
это 0, единица — это 1, - 1 = 1 _ 1 = 1 , а 0 - 1 — как всегда, не определён.
4. Если в условиях предыдущего примера взять в качестве сложения дизъюнкцию, то есть определить операции следующим образом: 0 0 = 0 1 = 1 0 = 0,
1 - 1 = 1 (конъюнкция), 0 + 0 = 0, 0 + 1 = 1 + 0 = 1 + 1 = 1 (дизъюнкция), то
структура (Е2] V, •) не является полем, поскольку у элемента 1 нет обратного
по сложению.
ТЕОРЕМА 1

Поле является областью целостности: а * b =

а*Ь = 0&саф0
= а ~ * 0 = 0, а*Ь = 0кЬф0=>а
= б - 1 * (а * 6) = б - 1 * 0 = 0.

ДОКАЗАТЕЛЬСТВО
1

0

=> а =

0 V

Ъ

=

0.

==> 6 = 1 * 6 = ( a - 1 * а) * b = а - 1 * (а * Ь) =
= 1 * а = (Ь - 1 * b) * а = Ъ~1 * (Ь * а) =


91

2.4. Векторные пространства и модули

ТЕОРЕМА 2

Если а Ф 0, то в поле единственным образом разрешимо
а * х + b = 0 (решение: х = - (а~1) * 6).

ДОКАЗАТЕЛЬСТВО

а*х+Ь = 0 = > а*х+6+(-6)

= 0 + (-6)

уравнение

А * х 4- (b + ( - 6 ) )

=

= —Ъ => а*х+О = —6 = > а*ж — —Ь = > а - 1 * ( а * х ) = а - 1 *(—6) =>• ( а - 1 * а) * х =
= — ( а - 1 * 6) =>• 1 * х = — ( а - 1 * Ь) ==*• х = — ( а - 1 * Ь).



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

2.4.1. Векторное пространство
Пусть 7 = (F; +, •) — поле с операцией сложения +, операцией умножения •,
аддитивным нейтральным элементом (нулем) 0 и мультипликативным
(единицей) 1. Пусть V = (V; +) — абелева группа с операцией + и нейтральным
элементом 0. Если существует операция F х V —> V (знак этой операции опускается), такая, что для любых a,b е F и для любых х , у е У выполняются
соотношения:
1) (а + 6)х = ах + 6х,
2) а(х + у) = ах + ау,
3) (а • Ь)х = а(Ьх),
4) 1х = х,
то V называется векторным пространством над полем З7, элементы F называются скалярами, элементы V называются векторами, нейтральный элемент группы V называется нуль-вектором и обозначается 0, а пеобозначеппая операция
F х V —> V называется умножением вектора на скаляр.
Примеры
1. Пусть J = ( F ; + , •) — некоторое поле. Рассмотрим множество кортежей FN.
Тогда У1 = (Fn\ +), где
Def

( a i , . . . , a n ) + (&i,..., bn) = (ai + 6 Ь ... , a n + bn)
является абелевой группой, в которой
-(ab...,an) =f(-ab...,-an)

и

0 = f ( 0 , . . . , 0).

92

Глава 2. Алгебраические структуры

Положим
а(а 1 , . . . , а п ) = f (а • а ь . . . , а • а„).
Тогда "Зп является векторным пространством над 7 для любого (конечного) п.
В частности, Мп является векторным пространством для любого п. Векторное
пространство М2 (и R 3 ) имеет естественную геометрическую интерпретацию
(рис. 2.1).
2. Двоичная арифметика Z2 = (£2;+2,-) является полем, а булеан ( 2 м ; д ) с
симметрической разностью является абелевой группой. Положим IX

=f X,

OX = f 0 . Таким образом, булеан с симметрической разностью является векторным пространством над двоичной арифметикой.
3. Пусть X = { : r i , . . . , хп} — произвольное конечное множество, а 7 = (F; +, •) —
поле. Рассмотрим множество Vx всех формальных сумм вида

хех
где Хх е F.
Положим

£



Кх

хЕХ

х£Х

a ^

[ixX

^хХ

=f

J2 fix + Их)х,

=

J2 (а • \х)х,
ХЕХ

хЕХ

где а,\х,[1х

хЕХ

е F.

Ясно, что Vx является векторным пространством, а X является его множеством образующих или базисом (см. 2.4.3). В таком случае говорят, что Vx —
это векторное пространство, «натянутое» на множество X.
4. В условиях предыдущего примера ( X = { x i , . . . , х п ) — произвольное конечное
множество, а = (F; +, •) — поле) рассмотрим множество Ф : = { / | / : X —> F}.
Положим
( / + flO(z) = f / ( s ) + 0(z)>
(af)(x)

f

= а • f{x),

где

где
aeFJe

f,ge

Ф,
Ф.

Нетрудно видеть, что Ф является векторным пространством.
ТЕОРЕМА

1. V x е V

(Ох =

0).

2. Va е F (аО = 0).
ДОКАЗАТЕЛЬСТВО

[ 1 ] Ох = (1 - 1)х = 1х - 1х = х - х = 0.
[ 2 ] аО = а(0 - 0) = аО - аО = (а - а)0 = 00 = 0.



93

2.4. Векторные пространства и модули

JL
У

(*1+*2. г/1+1/2)

(*2. 2/2)
/

/

/ /
(x2-xv г/2-г/i)

^^
,

У

/

W
X

~Г\ ^ ^ /
^ ^ 1_ /

^J

(-V2, -уг/2)
Рис. 2.1. Операции над векторами в М2

2.4.2. Линейные комбинации
Если V — векторное пространство над полем 7, S — некоторое множество векторов, S с V, то конечная сумма вида
п
^aiXi,

a» G F,

х* G S,

i—1

называется линейной комбинацией векторов из S. Пусть X = {xi,...,xfc} —
конечное множество векторов. Если
к
^агХг = 0

У г G l . . k (ai = 0 ) ,

г=1
то множество X называется линейно независимым. В противном случае, то есть
если
( к

к

\ j ai ф 0 &
г=1
г=1
множество X называется линейно зависимым.
ТЕОРЕМА

\
= 0

)'
/

Линейно независимое множество векторов не содержит нуль-вектора.

О Т противного. Пусть линейно независимое множество S =
= { x i , x 2 , . . . ,Xfc} содержит нуль-вектор и пусть для определённости xi = 0.

ДОКАЗАТЕЛЬСТВО

94

Глава 2. Алгебраические структуры

Положим a i : = 1, а 2 : = 0 , . . . , ак : = 0. Имеем 53 а г х г = 10 + 0х 2 + • • • + Ох/с =
г= 1
= 0 + 0 + . .. + 0 = 0, что противоречит линейной независимости S.


2.4.3. Базис и размерность
Подмножество векторов S е V, такое, что любой элемент V может быть представлен в виде линейной комбинаций элементов S, называется порождающим
множеством пространства V или множеством образующих. Линейно независимое
порождающее множество называется базисом векторного пространства.
1
Пусть векторное пространство V имеет базис В = { E I , . . . , E N } .
Тогда каждый элемент векторного пространства имеет единственное представление в данном базисе.
ТЕОРЕМА

ДОКАЗАТЕЛЬСТВО

11
~

г=1

Т1
=

г=1

п
Пусть х = 53
t=l

(«г _

п
0 = х - х = 53
V« G 1..ГО (rtj -

= 0 =>• V'/ («* =

~


Коэффициенты разложения вектора в данном базисе называются его координатами.
2
Пусть В = { E I , . . . , Е П } — базис, а X = { X I , . . . , Х Ш } — линейно
независимое множество векторного пространства V. Тогда n ^ га.

ТЕОРЕМА

ДОКАЗАТЕЛЬСТВО

ОТ

противного. Пусть п < т и В — базис. Тогда

3oi,...

,Оп 6 F (xi = oiei + ... +

anen).

П
Имеем xi ф 0 ==> \J п,томножество Y —

линейнозависимое.

Рассмотрим подпространство VA векторного пространства V,
порождаемое векторами множества А. В подпространстве VA множество А — базис, а векторы множества Y — элементы. Далее от противного. Пусть множество
Y линейно независимое, тогда по теореме п ^ га, что противоречит условию.


ДОКАЗАТЕЛЬСТВО

ТЕОРЕМА 3

Если В\ и В2 — базисы векторного пространства V, то \В\| = |В2|.

B I — базис и В2 —линейно независимое множество. Следовательно, |Bi| > |В 2 |. С другой стороны, В 2 — базис, и В\ — линейно независимое
множество. Следовательно, |В 2 | ^ |Bi|. Имеем |Bi| = |В 2 |.


ДОКАЗАТЕЛЬСТВО

Если векторное пространство V имеет базис В, то количество элементов в базисе
называется размерностью векторного пространства и обозначается dimV. Векторное пространство, имеющее конечный базис, называется конечномерным. Векторное пространство, не имеющее базиса (в смысле приведенного определения),
называется бесконечномерным.
Примеры
1. Одноэлементные подмножества образуют базис булеана, d i m I м = \М\.
2. Кортежи вида ( 0 , . . . , 1 , 0 , . . . , 0) образуют базис пространства

dim Т1 = п.

ЗАМЕЧАНИЕ
Если определить базис как максимальное линейно независимое множество (то есть множество, которое нельзя расширить, не нарушив свойства линейной независимости), то
понятие базиса можно распространить и im бесконечномерные пространств!!.

2.4.4. Модули
Понятие модуля во многом аналогично понятию векторного пространства, с той
лишь разницей, что векторы умножаются не на элементы из поля, а па элементы
из произвольного кольца. Пусть $ = (/?;+,#) = некоторое кольцо с операцией сложения +, операцией умножения *, нулевым элементом 0 и единичным
элементом 1, Абелева группа М = (М;+) называется модулам над кольцом
Я если задана операция умножения на скаляр Я х М => М (здесь никак пе
обозначаемая), такая что:

96

Глава 2. Алгебраические структуры

1) (а + Ь)х = ах + 6х;
2) а(х + у) = ах + ау;
3) (а * 6)х = а(Ьх);
4) 1х = х,
где а, b е Я, а х, у £ М. Как и в случае векторных пространств, элементы кольца
Л называются скалярами, а элементы группы М — векторами.
Примеры
1. Векторное пространство V над полем J является модулем над J , так как поле,
по определению, является кольцом.
2. Множество векторов с целочисленными координатами в Мп является модулем
над кольцом Z.
3. Любая абелева группа есть модуль над кольцом Z, если операцию умножения
на скаляр п е 1>,п > 0 определить следующим образом:
Def

nv

=

I

V + V + •• •+ V .
v

'

п раз

2.5. Решётки
Решётки иногда называют «структурами», но слово «структура» перегружено, и
мы не будем использовать его в этом значении. Решётки сами по себе часто встречаются в разных программистских задачах, но еще важнее то, что понятие решётки непосредственно подводит нас к понятию булевой алгебры, значение которой
для основ современной двоичной компьютерной техники трудно переоценить.

2.5.1. Определения
Решётка — это множество М с двумя бинарными операциями П и и , такими, что
выполнены следующие условия (аксиомы решётки):
1. Идемпотентность:
а Па = а, а U а =

Й.

2. Коммутативность:
аГ)Ь = b(la, aU b — bU а.
3. Ассоциативность:
(аПЬ)Пс = аП(6Пс),
4. Поглощение:
(а П b) U а = а,

(а U Ь) U с = а U (6 U с).

(а U Ь) П а = а.

5. Решётка называется дистрибутивной, если
a U (Ь П с) = (a U Ь) П (а U с), а П (b U с) = (а П b) U (а П с).

97

2.5. Решётки

2.5.2. Ограниченные решётки
Если в решётке 3 0 е М (Va (0 Da = 0)), то 0 называется нулем (или нижней
гранью) решётки. Если в решётке 3 1 е М (Va ( l U a = l ) ) , то 1 называется
единицей (или верхней гранью) решётки. Решётка с верхней и нижней гранями
называется ограниченной.
ТЕОРЕМА 1

Если

ДОКАЗАТЕЛЬСТВО

ТЕОРЕМА 2

(верхняя) грань существует, то она единственна.

Пусть 0' —ещё один пуль решётки. Тогда 0' = 0П0'= 0'П0 = 0.

а П b = Ъ a U b =



а.

ДОКАЗАТЕЛЬСТВО

[ = > ] a U 6 = a U (а П 6) = (а П Ь) U а = а.
[ a' U а = 1, а П а ' = 0 = > а ' П а = 0 ) = ^ а = а".
[ 3 ] (1 П 0 = 0,0' П 0 = 0) =>> 1 = 0', (1 U 0 = 1,1 и 1' = 1)

0 = 1'.

[ 4 ] (а П Ь) П (a' U Ь') = (а П Ъ П a') U (а П Ь П Ь') = (0 П Ъ) U (а П 0) = 0 U 0 = 0,
(а П b) U (a' U Ь') = (a U a! U Ъ') П (6 U a' U Ъ') = (1 U Ь') П (1 U а') = 1 П 1 = 1,
(a U Ь) П (а' П Ь') = (аПа'П Ь') U (6 П а' П У) = (0 П Ъ') U (а' П 0) = 0 U 0 = 0,
(a U Ь) U (а' П Ь') = (a U b U а') П (a U b U 6') = (1 U Ъ) П (1 U а) = 1 П 1 = 1.



98

Глава 2. Алгебраические структуры

2.5.4. Частичный порядок в решётке
В любой решётке можно естественным образом ввести частичный порядок, а именL

Def

^ ,

но: а -< b = а П о = а.
ТЕОРЕМА 1

Отношение -< является отношением частичного порядка.

ДОКАЗАТЕЛЬСТВО

[ Рефлексивность ] а Па — а ==> а -< а.
[ Антисимметричность ] а

b Sz b -< а ==> а = аГ\Ь

[ Транзитивность ] а -< b & b -< с

= ЬПа

= Ь.

аПс — ( а П Ь ) П с = а П ( Ь П с ) = аПЬ = а =>•

а - у -< x & x -< у

x = y.



Если в частично упорядоченном множестве для любых двух элементов существуют нижняя и верхняя грани, то это множество образует решётку
относительно inf и sup.

ТЕОРЕМА 3

Положим х П у = f i n f ( х , у ) , х U у = f sup(x,y)
полнение аксиом решётки.

ДОКАЗАТЕЛЬСТВО

и проверим вы-

[ 1 ] inf (х, х) = х ==> х П х = х, sup(X, х) = х ==> X U I = I .

[ 2 ] inf (х, у) = inf (у, х) => х Пу = у П х, sup(x, у) = sup(7/, х) ==> х U у = у U х.
[ 3 ] inf(a;, inf(y, г)) = inf(inf(cc, у), z)

х П (у П z) = (х П у) П г,

sup(x, sup (у, z)) = sup(sup(x, у), z) =$> х U (у U z) = (х U у) U z.
[ 4 ] sup(inf(a, b), а) =а = > (afl6)Ua = a, inf (sup(a, b), a) = a =>• (aUb)Da = a.



99

2.5. Решётки

2.5.5. Булевы алгебры
Дистрибутивная ограниченная решётка, в которой для каждого элемента существует дополнение, называется булевой алгеброй. Свойства булевой алгебры:
1. aU а = а, аГ\ а = а
по определению решётки.
2. a U 6 = bU а, аГ\Ь = ЬПа
по определению решётки.
3. а U [Ъ U с) = (а U b) U с, а П (Ъ П с) = (а П Ь) П с
по определению решётки.
4. (а П Ъ) U а = а, (а U 6) П а = а
по определению решётки.
5. а U (6 П с) = (а U 6) П (а U с), а П (6 U с) = (а П 6) U (а П с)
по дистрибутивности.
6. а и 1 = 1, а П 0 = 0
по ограниченности.
7. a U 0 = а, а П 1 = а
по следствию из теоремы 2 подраздела 2.5.2.
8. а" = а
по теореме подраздела 2.5.3.
9. (а П Ь)' = а' U 6', (а U Ь)' = а'ПЬ'
по теореме подраздела 2.5.3.
10. a U а' = 1, а П а ' = 0
по определению.
Примеры
1. ( 2 м ; П , и , ~ ) — булева алгебра, причём М — верхняя грань, 0 — нижняя грань,
С — естественный частичный порядок.
2. (£ 2 ; &, V, -•) — булева алгебра, где к — конъюнкция, V — дизъюнкция, —
отрицание, причём 1 — верхняя грань, 0 — нижняя грань, а импликация

естественный частичный порядок.
3. Пусть Т — некоторое конечное множество взаимно простых чисел. Пусть Р —
множество всех возможных произведений различных чисел из Т, включая
пустое произведение, по определению равное 1. (Заметим, что Р ~ 2 Т ). Тогда (Р; НОД, НОК, ДОП) — булева алгебра, где НОД — наибольший общий
делитель, Н О К — наименьшее общее кратное, а
ДОП(п) = f — — естественный частичный порядок.

100

Глава 2. Алгебраические структуры

2.6. Матроиды и жадные алгоритмы
В этом разделе рассматривается следующая простая и часто встречающаяся экстремальная задача. Задано конечное множество Е, элементам которого приписаны положительные веса, и семейство £ с 2Е подмножеств множества Е. Требуется пайти в семействе £ элемент (подмножество Е ) максимального суммарного
веса. Оказывается, что если семейство £ обладает особой структурой (является
матроидом), то для решения задачи достаточно применить очень простой и эффективный алгоритм (жадный алгоритм). Ясное понимание природы и области
применимости жадных алгоритмов совершенно необходимо каждому программисту. Матроиды, рассматриваемые в этом разделе, вообще говоря, не являются
алгебраическими структурами в том смысле, который придан этому понятию в
первом разделе данной главы. Однако матроиды имеют много общего с рассмотренными алгебраическими структурами (в частности, с линейно независимыми
множествами в векторных пространствах и модулях) и изучаются сходными
методами.

2.6.1. Матроиды
Матроидом М — (Е, £) называется пара, состоящая из конечного множества Е,
\Е\ = п, и семейства его подмножеств £ с 2Е, таких, что выполняются следующие
три аксиомы:
Mi:

0 G £;

М3:

А, В Е £ к \В\ = \А\ + 1 => Зе Е В\ А (А + е Е £).

Элементы множества £ называются независимыми, а остальные подмножества Е
(то есть элементы множества 2е \ £) — зависимыми множествами.
ЗАМЕЧАНИЕ
Аксиома М1 исключает из рассмотрения вырожденный случай £ = 0.

Пример Семейство линейно независимых множеств векторов любого векторного пространства является матроидом. Действительно, по определению можно
считать, что пустое множество векторов линейно независимо. Всякое подмножество линейно независимого множества векторов линейно независимо. Пусть
A: = { a i , . . . , a m } и В : = { b i , . . . , b m + i } — линейно независимые множества векторов. Если бы все векторы из множества В выражались в виде линейной комбинации векторов из множества А, то множество В было бы линейно зависимым по
следствию к теореме 2 подраздела 2.4.3. Стало быть, среди векторов множества
В есть по крайней мере один вектор Ь, который пе входит в множество А и пе
выражается в виде линейной комбинации векторов из множества А. Добавление
вектора b к множеству А образует линейно независимое множество.
ЗАМЕЧАНИЕ
Само понятие матроида возникло в результате исследования линейной независимости
в векторных пространствах.

101

2.6. Матроиды и жадные алгоритмы

2.6.2. Максимальные независимые подмножества
Пусть М = (Е, £) — матроид и ! с £ - произвольное множество. Максимальным независимым подмножеством множества X называется множество У, такое,
что
rcX&rZ
= Y).
Множество максимальных независимых подмножеств множества X обозначим X'.
XD={YcE\YcXkYeikVZe£

(Y С Z С X => Z = Y)} .

Рассмотрим следующее утверждение:
М4:

VX

(Y G Xk

Z G X =$> \Y\ = \Z\),

то есть все максимальные независимые подмножества данного множества равномощны.
ТЕОРЕМА
Пусть М = (Е, £) и выполнены аксиомы М\ и М 2 . Тогда аксиома
утверждение М4 эквивалентны, то есть

А, В • ] Пусть выполнены утверждения М ь М 2 , М 3 (то есть М — матроид). Покажем от противного, что выполняется и М 4 . Пусть У, Z € X, |У| Ф \Z\ и для
определённости |У| > \Z\. Возьмем Y' С У, так что |У'| = \Z\ + 1. Тогда по
свойству Мз имеем Зе е Y' \ Z (W: = Z + е е £). Таким образом, имеем
Z с W, W С X, Z ф W, что противоречит предположению Z е Х_.
[
] Пусть выполнены утверждения М ь М 2 , М 4 . Покажем от противного, что
выполняется и М 3 . Возьмем Л, Б е £, так что |Б| = |Л| + 1. Допустим, что
->3е е В\А (А + е е £), то есть Ve 6 В\А {А + е $ £). Рассмотрим С : = A U В.
Имеем А е С. Но В е £, поэтому ЗВ' (В с В' к В' е £ к В' е С). По условию
М 4 имеем \В'\ = \А\. Но \А\ = \В'\ ^ \В\ = \А\ + 1 — противоречие.


ЗАМЕЧАНИЕ
Таким образом, М\, М 2 , М4 — эквивалентная система аксиом матроида.

2.6.3. Базисы
Максимальные независимые подмножества множества Е называются базисами
матроида М = (£,£). Всякий матроид имеет базисы, что видно из следующего
алгоритма.

102

Глава 2. Алгебраические структуры

Алгоритм 2.1 Построение базиса матроида
Вход: Матроид М = (Е,£).
Выход: Множество В с Е элементов, образующих базис.
В : = 0 { вначале базис пуст }
for е е Е do
if В + е е 8. then
В : — В + е { расширяем базис допустимым образом }
end if
end for
Пусть ВО = 0, В\,..., В к = В — последовательность значений переменной В в процессе работы алгоритма. По построению Vг (Bi е £). Пусть В #
£ Е, то есть В не является максимальным. Тогда 3 В' (В с В' к В' ф В & В' е £)
Возьмем В" с В' так что \В"\ = \В\ +1, В с В" и В" е £. Рассмотрим ее
В'\В.
Элемент е не попал в множество В, но алгоритм просматривает все элементы,
значит, элемент е был отвергнут на некотором шаге г, то есть (Bi-1 + е) ^ £. Но
ее В" к Bi-1 с В"
(В^ 1 + е) € £. По аксиоме М 2 имеем (Вг-i + е) е £ —
противоречие.

ОБОСНОВАНИЕ

СЛЕДСТВИЕ

Все базисы матроида равномощны.

2.6.4. Жадный алгоритм
Сформулируем более точно рассматриваемую экстремальную задачу. Пусть имеются конечное множество Е, \Е\ = п, весовая функция w: Е —* R+ и семейство
£ с 2е. Требуется найти X е £, такое, что
w(X) = тахги(У),

где w(Z) =f

^
w(e).
eeZCE

Другими словами, необходимо выбрать в указанном семействе подмножество
наибольшего веса. Не ограничивая общности, можно считать, что w(e\) ^ ... ^
^ w(eTl) > 0. Рассмотрим следующий алгоритм.
Алгоритм 2.2 Жадный алгоритм
Вход: множество Е = { e i , . . . , e n } , семейство его подмножеств £ и весовая
функция w. Множество Е линейно упорядочено в порядке убывания весов
элементов.
Выход: подмножество X, такое, что X е £ и w(X) = m a x w ( Y ) .
X : = 0 { вначале множество X пусто }
for i from 1 to n do
if X + e{ e £ then
X : = X + a { добавляем в X первый подходящий элемент }
end if
end for

2.6. Матроиды и жадные алгоритмы

103

Алгоритм такого типа называется жадным. Совершенно очевидно, что по построению окончательное множество X £ £. Также очевидно, что жадный алгоритм
является чрезвычайно эффективным: количество шагов составляет 0(п), то есть
жадный алгоритм является линейным. (Не считая затрат па сортировку множества Е и проверку независимости X + е* £ £.) Возникает вопрос: в каких
случаях жадный алгоритм действительно решает задачу, поставленную в начале
подраздела? Другими словами: когда выгодно быть жадным?
Пример

Пусть дана матрица
7
3
2

5 1
4 3
3 1

Рассмотрим следующие задачи:
1. Выбрать по одному элементу из каждого столбца так, чтобы их сумма была максимальна. Нетрудно видеть, что жадный алгоритм выберет следующие
элементы:

0 0

1

3
4 [3j
2
3
1
которые действительно являются решением задачи.
2. Выбрать по одному элементу из каждого столбца и из каждой строки так,
чтобы их сумма была максимальна. Нетрудно видеть, что жадный алгоритм
выберет следующие элементы:
0

5

1

3 Щ

з

2



3

которые не являются решением задачи,
ние:
0
5
3
4
2 [3]

поскольку существует лучшее реше1

1

ТЕОРЕМА
Если М = (Е, £) — матроид, то для любой функции w жадный алгоритм находит независимое множество X с наибольшим весом; обратно, если же
М = (Е, £) не является матроидом, то существует такая функция w, что множество X, найденное жадным алгоритмом, не будет подмножеством наибольшего
веса.
ДОКАЗАТЕЛЬСТВО

[ = > ] Пусть М = (Е,Е) — матроид и пусть X = {ал,...,®*.} — множество,
построенное жадным алгоритмом. По построению u>(a?i) ^ . . . ^ w(x k ) > 0.
Согласно алгоритму 2.1, множество X — базис матроида М. Пусть теперь Y =
= {г/ь • • ч У т } € £ — некоторое независимое множество. Имеем m < к, так как

104

Глава 2. Алгебраические структуры

X — базис. Покажем от противного, что У г е 1 ..га (w(yi) < w(xi)). Пусть
З г е 1..га (гу(уг) > гу(^г))- Рассмотрим независимые множества А = {х\,... ,£*_].}
и В = {г/1,..., Vi-I,yi}. Имеем 3j ^ г ( { x i , . . . ,Xi-I,yj})
— независимое множество. Тогда w(yj) ^ w(yi) > it;(rci), откуда следует, что
Зр ^ i (w(xi) ^ ... ^ w(xp~\) ^ Цг/j) ^

w(xp)),

что противоречит тому, что х р — элемент с наибольшим весом, добавление которого к множеству { x i , . . . , xv-i) не нарушает независимости. Следовательно,
Уг (ги(уг)) ^ w(xi) и, значит, w(Y) <
[ Е2}.
Булеву функцию от п переменных можно задать таблицей истинности:

1

Джордж Буль (1815-1864).

108

XI
0
0
0
1

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

. •
.

ХП — 1 ХП

0
0
1

0
1
0

/С® 1» • • , Х П )
ДО,. .,0,0)
Д о , . .,0,1)
До,- .,1,0)

1

1

Д1,- • ,1,1)

Если число переменных равно п, то в таблице истинности имеется 2 П строк,
соответствующих всем различным комбинациям значений переменных. Следовательно, существует 2 2 " различных столбцов, каждый из которых определяет
булеву ф у н к ц и ю от п переменных. Таким образом, число булевых ф у н к ц и й от п
переменных с ростом п растет весьма быстро:
|Рп|=22".

ЗАМЕЧАНИЕ
Если нужно задать несколько (например, к) булевых функций от п переменных, то это
удобно сделать с помощью одной таблицы, использовав несколько столбцов:
Х\
0

...
...

Хп
0

1

...

1

fi(xi,...

,хп)

/ 1 ( 0 , . . . , 0)

fk(xi,..., хп)
Л ( о,...,о)

/l(l,...,1)

Такая таблица будет иметь 2п строк, ть столбцов для значений переменных и ещё к столбцов для значений функций. Вообще говоря, значения переменных можно пе хранить,
если принять соглашение о перечислении наборов переменных в определённом порядке. Во всех таблицах истинности в этом учебнике переменные всегда перечисляются
в лексикографическом порядке, а кортежи булевых значений — в порядке возрастания
целых чисел, задаваемых кортежами как двоичными шкалами (см. алгоритм 1.1), что
совпадает с лексикографическим порядком на кортежах. Такой порядок мы называем
установленным.
Если к > 2п (что, как показывает предыдущая формула, не редкость), то таблицу истинности можно «транспонировать», выписывая наборы значений в столбцах, а значения
функций — в строках:
XI

0

1

Хп

0

1

h

/ i ( 0 , . . .,0)

.

fk

Л ( о , . . .,0)

. •

• ,1)
Л ( 1...• ,1)

Именно такой способ записи таблицы истинности использовал в подразделах 3.1.3 и 3.1.4.

3.1. Элементарные булевы функции

109

3.1.2. Существенные и несущественные переменные
Булева функция / е Рп существенно зависит, от переменной xi, если существует
такой набор значений a i , . . . , a j - i , a , + i , . . . , а п , что
/ ( a i , . . . , a j _ i , 0, aj+i? • • • > а п

,

1, О-г+1, • • • J «тг)-

В этом случае Хг называют существенной переменной, в противном случае Xi
называют несущественной (фиктивной) переменной.
Пример
ности:
XI
0
0
1
1

Пусть булевы функции / i ( x i , x 2 ) и / 2 ( x i , x 2 ) заданы таблицей истинХ2
0
1
0
1

/1
0
0
1
1

/2
1
1
0
0

Для этих функций переменная х\ — существенная, а переменная х 2 — несущественная.
Пусть заданы две булевы функции / i ( x i , . . . , x n _ i ) и / 2 ( х i , . . . , x n _ i , x n ) и пусть
переменная х п — несущественная для функции / 2 , а при одинаковых значениях
остальных переменных значения функций совпадают:
Vai,... ,a„_i,an (/i(ai,... ,on_i) = /2(ai,... ,an_i,an)).
В таком случае говорят, что / 2 получается из / i введением несущественной переменной хп, а fi получается из / 2 удалением несущественной переменной хп.
ЗАМЕЧАНИЕ
Процедурно введение и удаление несущественных переменных выполняются достаточно просто. Чтобы ввести несущественную переменную, нужно продублировать каждую
строку таблицы истинности, добавить новый столбец и заполнить этот столбец чередующимися значениями 0 и 1 (или 1 и 0, что несущественно). Удаление несущественной переменной выполняется аналогично: нужно отсортировать таблицу истинности так, чтобы
она состояла из пар строк, различающихся только в разряде несущественной переменной,
после чего удалить столбец несущественной переменной и удалить каждую вторую строку
таблицы.

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

110

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

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

Отрицание

1

0

0

Обозначение

Нуль
Тождественная

0

0

Несущественные

X

X 0 1
—IX, х, х', ~ X 1 0

Единица

1

1

1

X

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

Название

Переменная х

0

0

1

1

Переменная у

0

1

0

1

0

0

0

0

0

Л

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

Обозначение

Нуль
Конъюнкция

Сложение по модулю 2

•,

+ . +2. ф,

А

Несущественные

Стрелка Пирса 1

V 0 1 1 1
1 1 0 0 0

Эквивалентность

=

Дизъюнкция

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

0

1

Ш т р и х Шеффера 2

э 1
1 1

1

1

0

Единица

1

1

1

1

Импликация

—,

1

х, у

У
X

X
У

х, у

ЗАМЕЧАНИЕ
Пустоты в столбцах «Название» и «Обозначение» в предыдущей таблице означают, что
булева функция редко используется, а потому не имеет специального названия и обозначения.
1
2

Чарльз Сандерс Пирс (1839-1914).
Генри М. Шеффер (1882-1964).

111

3.2. Формулы

3.2. Формулы
В этом разделе обсуждается целый ряд важных понятий, которые часто считаются самоочевидными, а потому их объяснение опускается. Такими понятиями
являются, в частности, реализация функций формулами, интерпретация формул для вычисления значений функций, равносильность формул, подстановка и
замена в формулах. Между тем программная реализация работы с формулами
требует учёта некоторых тонкостей, связанных с данными понятиями, которые
целесообразно явно указать и обсудить.

3.2.1. Реализация функций формулами
Начнём обсуждение с привычного понятия формулы. Вообще говоря, формула —
это цепочка символов, имеющих заранее оговорённый смысл. Обычно формулы строятся по определённым правилам из обозначений объектов и вспомогательных символов — разделителей. Применительно к рассматриваемому случаю
объектами являются переменные и булевы функции, перечисленные в таблицах подразделов 3.1.3 и 3.1.4, а разделителями — скобки «(», «)» и запятая «,».
Мы считаем, что обозначения всех объектов заранее определены и синтаксически отличимы друг от друга и от разделителей, а правила составления формул
общеизвестны.
ЗАМЕЧАНИЕ
Для обозначения объектов используются как отдельные символы, так и группы символов,
в том числе со специальным начертанием: верхние и нижние индексы, наклон шрифта и т. п. Допущение о синтаксической различимости остаётся в силе для всех таких
особенностей.

Пример Операцию сложения вещественных чисел принято обозначать знаком
«+», 4 - : l x R - > l , a функцию «синус» — словом «sin», которое записывается
прямым шрифтом и считается одним символом, sin: М —• R.

ОТСТУПЛЕНИЕ
В математических текстах часто используется нелинейная форма записи формул, при
которой формула не является цепочкой символов. Примерами могут служить дроби, радикалы, суммы, интегралы. Подобные нелинейные формы записи формул привычны и
удобны. Использование нелинейной записи формул не является принципиальным расширением языка формул. Можно ограничиться только линейными цепочками символов,
что блестяще подтверждает система Т^Х, с помощью которой подготовлена эта книга.
Пусть F = { Д , . . . , fm} — некоторое множество булевых функций от п переменных. Формулой 7 над F называется выражение (цепочка символов) вида
= / ( < ! , . . . , tn),

112

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

где / е F nti — либо переменная, либо формула над F. Множество F называется
базисом, функция / называется главной (внешней) операцией (функцией), a U
называются подформулами. Если базис F ясен из контекста, то его обозначение
опускают.
ЗАМЕЧАНИЕ
Обычно при записи формул, составленных из элементарных булевых функций, обозначения бинарных булевых функций записываются как знаки операций в инфиксной форме,
отрицание записывается как знак унарной операции в префиксной форме, тождественные функции записываются как константы 0 и 1. Кроме того, устанавливается приоритет
операций (->, &, V, —•) и лишние скобки опускаются.

Всякой формуле 7 однозначно соответствует некоторая функция / . Это соответствие задается алгоритмом интерпретации, который позволяет вычислить
значение формулы J при заданных значениях переменных.
Алгоритм 3.1 Интерпретация формул — рекурсивная функция Eval
Вход: формула
множество F функций базиса,
значения переменных х\,...,
хп.
Выход: значение формулы 7 на значениях xi,...,xn
или значение fail, если
значение формулы не может быть определено,
if J = 'х^ then
return xi { значение переменной задано }
end if
if J = ' f{t\,...,
tn)' then
if / g F then
return fail { функция не входит в базис }
end if
for t e {ti,..., tn} do
Ui: = Eval (U, F, x\,..., xn) { значение г-го аргумента }
if yi = fail then return fail end if
end for
return f(yi,... ,yn) { вычисленное значение главной операции }
end if
return fail { это не формула }
ОТСТУПЛЕНИЕ
Некоторые программистские замечания по поводу процедуры Eval.
1. При программной реализации алгоритма интерпретации формул важно учитывать, что
в общем случае результат вычисления значения формулы может быть не определён
(fail). Это имеет место, если формула построена синтаксически неправильно или если в пей используются функции (операции), способ вычисления которых не задан,
то есть они пе входят в базис. Таким образом, необходимо либо проверять правильность формулы до начала работы алгоритма интерпретации, либо предусматривать
невозможность вычисления значения в самом алгоритме.

113

3.2. Формулы

2. Это не единственный возможный алгоритм вычисления значения формулы, более того,
он не самый лучший. Для конкретных классов формул, например, для некоторых классов формул, реализующих булевы функции, известны более эффективные алгоритмы
(например, алгоритм 3.4).
3. Сама идея этого алгоритма: «сначала вычисляются значения аргументов, а потом значение функции»,— не является догмой. Например, можно построить такой алгоритм
интерпретации, который вычисляет значения только некоторых аргументов, а потом
вычисляет значение формулы, в результате чего получается новая формула, реализующая функцию, которая зависит от меньшего числа аргументов. Такой алгоритм
интерпретации называется смешанными вычислениями.
А. Порядок вычислеиия аргументов считается неопределённым, то есть предполагается,
что базисные функции не имеют побочных эффектов. Если же базисные функции имеют побочные эффекты, то результат вычисления значения функции может зависеть от
порядка вычисления значений аргументов. Побочные эффекты могут иметь различные
причины. Наиболее частая: использование глобальных переменных. Например, если
f(x) = f а: — а + 1; return х + а,
д(х) = f а: = а * 2; return х * а,
причём переменная а глобальна, то (если а Ф 6)
/(2) +^(3) фд(3) + /(2).

Если формула 7 и базис F заданы (причём 7 является правильно построенной
формулой над базисом F), то процедура E v a l ( J , F, х\,...,
хп) является некоторой
булевой функцией / переменных х\,... ,хп. В этом случае говорят, что формула
7 реализует ф у н к ц и ю / :
func 3 = f .
ЗАМЕЧАНИЕ
Для обозначения реализуемости применяют и другие приёмы. Выбранное обозначение
обладает тем достоинством, что согласовано с другими обозначениями в книге.

З н а я таблицы истинности для ф у н к ц и й базиса, можно вычислить таблицу истинности той функции, которую реализует данная формула.
Примеры
1. Fi : = ( x i A х2) V ( ( ц A x2) V
Х\
0
0
1
1

Х2
0
1
0
1

х\ Лх2
0
0
1
0

х\Лх2
0
1
0
0

A x2))
(xi A х2) V (xi А х2)
0
1
1
0

Таким образом, формула F\ реализует дизъюнкцию.

х\ Лх2
0
0
0
1

Fi
0
1
1
1

114

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

2. F2 : =(х\ А х2) —• х\
XI

х2

Х\Лх2

F2

0
0
1
1

0
1
0
1

0
0
0
1

1
1
1
1

Таким образом, формула F2 реализует константу 1.
3. F3 : =((xi

Л х2) + х\) + х2

Х\
0
0
1

х2
0
1
0

х\ Л х2
0
0
0

1

1

1

(zi Л х2) + х\
0
0

((zi Л х2) + xi)

1
0

+

х2

0
1

1
1

Таким образом, формула F3 также реализует дизъюнкцию.

3.2.2. Равносильные формулы
Одна функция может иметь множество реализаций (над данным базисом). Формулы, реализующие одну и ту же функцию, называются равносильными:
^

=

^ 3 / ( f u n c J i = / к funcJz = / ) •

Отношение равносильности формул является эквивалентностью. Имеют место,
в частности, следующие равносильности:
1. а V а = а, а Л а = а.
2. а V b = b V а, а Л б = бАа.
3. а V (6 V с) = (а V b) V с, а Л (Ь Л с) = (а Л 6) Л с.
4. (а Л 6) V а = а, (а V Ь) Л а = а.
5. а V (6 Л с) = (а V 6) Л (а V с), а Л (b V с) = (а Л Ь) V (а Л с).
6. а V 1 = 1, а Л 0 = 0.
7. а V 0 = а, а Л 1 = а.
8. ——
| <
i2 = а.
9. ->(а Л Ь) = ->а V

->(а V 6) = ->а Л ->Ь.

10. а V ->а = 1, а Л ->а = 0.
Все они могут быть проверены построением соответствующих таблиц истинности. Таким образом, (£ 2 ; V, Л, ->) — булева алгебра (см. 2.5.5).

3.2. Формулы

115

ЗАМЕЧАНИЕ
Ввиду выполнения равносилыюстей 2 и 3 для кратных дизъюнкций и конъюнкций используются следующие обозначения:

п

\у /

п
/\XiA
i-1

Def

V / . . . Vw Хп,
= xi V

г=1

Def

= Xi Л ••• Л xTL.

3.2.3. Подстановка и замена
Если в формулу 3 входит переменная х, то это обстоятельство обозначается
так: Э г (... х . . . ) . Соответственно, запись Э г (... S • • •) обозначает, что в формулу
Э входит подформула S- Вместо подформулы (в частности, вместо переменной) в формулу можно подставить другую формулу (в частности, переменную),
в результате чего получится новая правильно построенная формула. Наряду с
оборотом «подставить подформулу в формулу» используется оборот «заменить
подформулу формулой». Если подстановка формулы 9 производится вместо всех
вхождений заменяемой переменной х (или подформулы), то результат подстановки обозначается следующим образом: Э г (... х . . . ){3//х}. Если же подстановка
производится вместо некоторых вхождений (в том числе вместо одного), то
результат подстановки обозначается следующим образом: Э г (... Si • • • HS2/S1}.
Примеры
1. Замена всех вхождений переменной: х V ~>х{у А г / / х } = (у A z) V ->(у A z).
2. Замена всех вхождений подформулы: х V у V z{->x//y

V zj — х V ->х.

3. Замена первого вхождения переменной: х V ->х{у/х} = у V -*х.
4. Замена первого вхождения подформулы: х V у V z{-^x/y V zj = х V ->х.
Известны два правила: правило подстановки и правило замены,— которые позволяют преобразовывать формулы с сохранением равносильности.
1 (Правило подстановки) Если в двух равносильных формулах вместо
всех вхождений некоторой переменной х подставить одну и ту же формулу, то
получатся равносильные формулы:

ТЕОРЕМА

V3

№ ( . . . * . . . )

= Э 2 ( . . . У

1

( . . . Я . . . ) { 9 / / ® }

=

5,2(...®...){9//®}).

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

ДОКАЗАТЕЛЬСТВО

Рассмотрим произвольный набор значений а\,..., аХ}..., ап переменных x i , . . . ,
х,..., хп. Обозначим а: = Eval(S, F, а\,..., ах,..., ап). По определению алгоритма интерпретации
E v a l ( J i { S / / x } , F , a i , . . . , ах,...,

ап) = Eval(Ji, F, а ь . . . , а , . . . , а п )

116

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

и, аналогично,
Eval(^2{S//ic},i^,ai,...,ax,...,an) = E v a l ^ , F , a b ... , a , . . . ,an).
Ho J i = 3*2, и значит,
E v a l ( 3 " i , F , a i , . . . , a , . . . , a n ) = Eval(J 2 , F, a b . . . , a , . . . , a n ) ,
откуда
Eval(U'i{S//z}, F , a b . . . , a x , . . . , a n ) = Eval(J 2 {S//x}, F, fll, . . . ,

j • • • ) O-n

ЗАМЕЧАНИЕ

В правиле подстановки условие замены всех вхождений существенно: например, x\f-*x = 1
и i V -1 х{у//х}
=уУ —*у = 1, но х V ->х{у/х} = у V -IX Ф 1!

Т Е О Р Е М А 2 (Правило замены) Если в формуле заменить некоторую подформулу
равносильной формулой, то получится формула, равносильная исходной:

V 7 ( . . . 9i • • •) (Si = 92 = > Я..

Si • • •) = Я • • Si • • • MS2/S1}) •

Рассмотрим произвольный набор значений а\,...,
ных x i , . . . , хп. Имеем Si = S2» и значит,

ДОКАЗАТЕЛЬСТВО

ап перемен-

Eval(Si, F, a i , . . . , а„) = Eval(S 2 , F, a i , . . . , a„),
откуда
Eval(J{Si/Si}, F, a i , . . . , a„) = Eval(3"{S 2 /Si}, F, a b . . . , an).



Пусть F = { / I , . . . , / m } И G =
Тогда говорят, что формулы J[F]
и S [G] имеют одинаковое строение, если J совпадает с результатами подстановки
в формулу S функций /г вместо функций gi:

3.2.4. Алгебра булевых функций
Булевы функции V, А, (и любые другие) могут рассматриваться как операции
на множестве булевых функций, V , A : ? n x P n - > Рп, ->: Рп —• Рп.
Действительно, пусть формулы
и J 2 равносильны и реализуют функцию / ,
а формулы Si и S2 равносильны и реализуют функцию д:
funcSFi = / ,

funcS^ - / ,

funcSi = д,

funcS 2 -