Дискретная математика

А.И. Белоусов, С.Б. Ткачев5-7038-1769-2

В девятнадцатом выпуске серии “Математика в техническом университете” изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам.

---

Table of contents :
Предисловие……Page 6
Основные обозначения……Page 13
1.1. Множества……Page 24
1.2. Кортеж. Декартово произведение……Page 38
1.3. Соответствия и бинарные отношения……Page 41
1.4. Операции над соответствиями……Page 52
1.5. Семейства множеств……Page 61
1.6. Специальные свойства бинарных отношений……Page 63
1.7. Отношения эквивалентности……Page 71
1.8. Упорядоченные множества. Теорема о неподвижной точке……Page 76
1.9. Мощность множества……Page 90
Д.1.1. Об одном парадоксе теории множеств……Page 101
Д.1.2. Метод характеристических функций……Page 103
Вопросы и задачи……Page 107
2. Алгебры: группы и кольца……Page №113
2.1. Операции. Понятие алгебраической структуры……Page 113
2.2. Группоиды, полугруппы, группы……Page 122
2.3. Кольца, тела, поля……Page 136
2.4. Области целостности……Page 142
2.5. Модули и линейные пространства……Page 146
2.6. Подгруппы и подкольца……Page 148
2.7. Теорема Лагранжа……Page 153
2.8. Гомоморфизмы групп и нормальные делители……Page 158
2.9. Гомоморфизмы колец……Page 167
Д.2.1. Кватернионы……Page 169
Вопросы и задачи……Page 172
3.1. Полукольца. Основные примеры……Page 176
3.2. Замкнутые полукольца……Page 183
3.3. Решение систем линейных уравнений……Page 196
3.4. Булевы алгебры……Page 205
3.5. Решетки……Page 213
Вопросы и задачи……Page 224
4.1. Модели и алгебры……Page 227
4.2. Подсистемы……Page 231
4.3. Конгуэнции и фактор-системы……Page 237
4.4. Гомоморфизмы……Page 243
4.5. Прямые произведения алгебраических систем……Page 254
4.6. Конечные булевы алгебры……Page 261
4.7. Многосортные алгебры……Page 267
Вопросы и задачи……Page 274
5. Теория графов ……Page 276
5.1. Основные определения……Page 277
5.2. Способы представления……Page 289
5.3. Деревья……Page 298
5.4. Остовное дерево наименьшего веса……Page 307
5.5. Методы систематического обхода вершин графа……Page 312
5.6. Задача о путях во взвешенных ориентированных графах……Page 327
5.7. Изоморфизм графов……Page 342
5.8. Топологическая сортировка……Page 350
5.9. Элементы цикломатики……Page 357
Вопросы и задачи……Page 369
6.1. Понятие булевой функции. Булев куб……Page 376
6.2. Таблицы булевых функций……Page 384
6.3. Фиктивные переменные. Равенство булевых функций ……Page 389
6.4. Формулы и суперпозиции……Page 394
6.5. Дизъюнктивные и конъюнктивные нормальные формы……Page 406
6.6. Построение минимальных ДНФ……Page 409
6.7. Теорема Поста……Page 430
6.8. Схемы из функциональных элементов……Page 448
Вопросы и задачи……Page 457
7. Конечные автоматы и регулярные языки ……Page 461
7.1. Алфавит, слово, язык ……Page 463
7.2. Порождающие грамматики ……Page 473
7.3. Классификация грамматик и языков ……Page 487
7.4. Регулярные языки и регулярные выражения ……Page 491
7.5. Конечные автоматы. Теорема Клини ……Page 495
7.6. Детерминизация конечных автоматов ……Page 522
7.7. Минимизация конечных автоматов ……Page 532
7.8. Лемма о разрастании для регулярных языков ……Page 539
Д.7.1. Обоснование алгоритма детерминизации конечных автоматов ……Page 545
Д.7.2. Конечные автоматы с выходом. Структурный синтез ……Page 552
Д.7.3. Морфизмы и конечные подстановки ……Page 565
Д.7.4. Машины Тьюринга ……Page 570
Вопросы и задачи ……Page 580
8.1. КС-грамматики. Деревья вывода. Однозначность ……Page 588
8.2. Приведенная форма КС-грамматики ……Page 603
8.3. Лемма о разрастании для КС-языков ……Page 617
8.4. Магазинные автоматы ……Page 626
8.5. Алгебраические свойства КС-языков ……Page 655
Д.8.1. О методах синтаксического анализа КС-языков ……Page 674
Д.8.2. Семантика формальных языков ……Page 693
Д.8.3. Графовое представление МП-автоматов ……Page 712
Вопросы и задачи ……Page 715
Список рекомендуемой литературы……Page 721
Предметный указатель……Page 725