Читать онлайн «Дискретная математика»

ББК 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.