ББК 519. 17(075)
УДК 22. 174я7
Н73
Рецензенты:
Абрамов С. М. , директор Института программных систем им. А. К. Айламазяна РАН,
чл. -корр. РАН, д. ф. -м. н. ;
ГОУВПО «Санкт-Петербургский государственный университет
информационных технологий, механики и оптики»
Новиков Ф. А. Н73 Дискретная математика: Учебник для вузов. Стандарт третьего поколения. —
СПб. : Питер, 2011. — 384 с: ил. ISBN 978-5-459-00452-6
В учебнике изложены все основные разделы дискретной математики и описаны важнейшие
алгоритмы на дискретных структурах данных. Основу книги составляет материал лекционного
курса, который автор читает в Санкт-Петербургском государственном политехническом университете
последние двадцать пять лет. Книга имеет обширный справочный аппарат: указатель обозначений,
детальный предметный указатель с переводом всех терминов на английский язык, развернутый
библиографический список и комментарии к нему. Для студентов вузов, обучающихся по направлениям подготовки «Системный анализ и
управление», «Прикладная математика и информатика», «Информатика и вычислительная техника»,
а также для всех желающих изучить дискретную математику. Рекомендовано Учебно-методическим объединением по университетскому политехническому
образованию в качестве учебника для студентов высших учебных заведений, обучающихся по
направлению подготовки «Системный анализ и управление». ББК 519. 17(075)
УДК 22. 174я7
Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было
форме без письменного разрешения владельцев авторских прав. Тем не менее, имея в виду возможные человеческие или технические ошибки, издательство не
может гарантировать абсолютную точность и полноту приводимых сведений и не несет ответственности за
возможные ошибки, связанные с использованием книги. ISBN 978-5-459-00452-6
© ООО Издательство «Питер», 2011
Краткое содержание
Предисловие 13
Введение 15
Глава 1. Множества и отношения 23
Глава 2. Алгебраические структуры 75
Глава 3. Булевы функции 107
Глава 4. Логические исчисления 142
Глава 5. Комбинаторика 179
Глава 6. Кодирование 208
Глава 7. Графы 240
Глава 8. Связность 265
Глава 9. Деревья 292
Глава 10. Циклы, независимость и раскраска 333
Указатель основных обозначений 365
Список литературы 368
Предметный указатель 370
Содержание
Предисловие 13
Введение 15
Глава 1. Множества и отношения 23
1. 1. Множества 23
1. 1. 1. Элементы и множества 23
1.
1. 2. Задание множеств 25
1. 1. 3. Парадокс Рассела 26
1. 1. 4. Мультимножества 27
1. 2. Алгебра подмножеств 28
1. 2. 1. Сравнение множеств 28
1. 2. 2. Равномощные множества 29
1. 2. 3. Конечные и бесконечные множества 31
1. 2. 4. Добавление и удаление элементов 32
1. 2. 5. Мощность конечного множества 32
1. 2. 6. Операции над множествами 34
1. 2. 7. Разбиения и покрытия 35
1. 2. 8. Булеан 36
1. 2. 9. Свойства операций над множествами 37
1. 3. Представление множеств в программах 38
1. 3. 1. Битовые шкалы 38
1. 3. 2.