Учебник включает шесть разделов: основы теории множеств,
алгебраические системы, числовые системы, теория графов, комбинаторика, алгебра логики. <...> Здесь
приводятся понятия формулы и функции алгебры логики, алгоритмы минимизации функций алгебры логики, критерий полноты системы булевых функций, приложения алгебры логики. <...> 9
Мы будем использовать следующие обозначения для числовых множеств: N или множество натуральных чисел, Z множество целых чисел, Q множество рациональных чисел,
R множество вещественных чисел, C множество комплексных чисел. <...> Множество A \ B A B {x|x A и x / B} называется разностью множеств A и B ,
(A\B)(B \A) кольцевой суммой
множество AB AB
или симметрической разностью множеств A и B , а множество
A U \ A дополнением множества A в U (см. рис. <...> ¤
Бинарные отношения P A Ч B иногда удобно изображать
графически. <...> Функция f называется взаимно однозначным соответствием между множествами A и B или биективной функцией (биекцией ), если f разнозначное отображение A на B . <...> Биекция f : A A называется
подстановкой множества A. <...> Если f и g разнозначные отображения, то f g разнозначное отображение. <...> Принцип математической индукции
Рассмотрим два подхода к заданию множества натуральных
чисел. <...> Таким образом, с одной
стороны, указывается множество натуральных чисел, а с другой стороны все существенные (определяющие) свойства этого
множества. <...> Объединив эти множества, получаем множество всех
натуральных чисел {0, 1, 2, . . . , n, . . .}, обозначаемое через . <...> В этом состоит принцип математической индукции . <...> Принцип математической индукции позволяет также давать
индукционные определения , т. е. определения понятий P (n) для
всех натуральных чисел n, построенные по следующей схеме: <...> Множества A и B называются эквивалентными (обозначается A B ), если существует биекция f : A B . <...> Так как
ет Mi на Mi+2 для любого i ,
определенное следующим образом:
a,
если
h(a) =
(f g)(a), если
k6i
f g разнозначно отображато отображение h : A A <...>
Дискретная_математика.pdf
УДК 519.1(075.8)
С892
Рецензенты:
д-р физ.-мат. наук, проф. Е. А. Палютин,
канд. техн. наук, доц. В. М. Зыбарев
Судоплатов С. В.
С892 Дискретная математика : учебник / С. В. Судоплатов, Е. В. Овчинникова.
– 3-e изд., перераб. и доп. – Новосибирск : Изд-во НГТУ, 2010. –
280 с. (Серия «Учебники НГТУ»)
ISBN 978-5-7782-1327-2
В книге излагаются основы теории множеств, алгебраических систем, компьютерной
арифметики, теории графов, комбинаторики, алгебры логики, которые
образуют курс дискретной математики.
Для студентов технических вузов, изучающих дискретную математику.
Может служить справочным пособием по дискретной математике.
УДК 519.1(075.8)
ISBN 978-5-7782-1327-2
© Судоплатов С. В., Овчинникова Е. В.,
2002, 2005, 2010
© Новосибирский государственный
технический университет,
2002, 2005, 2010
Стр.2
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Г л а в а 1. Элементы теории множеств . . . . . . . . . . . . . . 9
1.1. Множества и основные операции над ними . . . . . . . 9
1.2. Отношения. Функции. Взаимно однозначные соответствия
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3. Натуральные числа. Принцип математической индукции
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4. Мощность множества. Конечные и бесконечные множества
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.5. Матрица бинарного отношения. Специальные бинарные
отношения . . . . . . . . . . . . . . . . . . . . . . . 30
1.7. Отношения порядка . . . . . . . . . . . . . . . . . . . . . 36
1.8. Аксиомы теории множеств . . . . . . . . . . . . . . . . . 42
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . 44
1.6. Отношения эквивалентности и разбиения. Фактор-множества
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Г л а в а 2. Алгебраические системы . . . . . . . . . . . . . . . . 47
2.1. Определения и примеры . . . . . . . . . . . . . . . . . . 47
2.2. Морфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3. Подсистемы . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.5. Декартовы произведения алгебр. Теорема Биркгофа . 57
2.6. Решетки и булевы алгебры . . . . . . . . . . . . . . . . . 58
2.7. Идеалы и фильтры булевой алгебры . . . . . . . . . . . 63
2.8. Алгебры отношений и реляционные алгебры . . . . . . 64
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . 68
Г л а в а 3. Числовые системы . . . . . . . . . . . . . . . . . . . . 70
3.1. Бесконечные числовые системы . . . . . . . . . . . . . . 70
3.2. Системы счисления . . . . . . . . . . . . . . . . . . . . . 75
3.3. Компьютерная алгебра и численный анализ . . . . . . 81
3.4. Списочное представление чисел . . . . . . . . . . . . . . 83
3.5. Делимость в кольце целых чисел . . . . . . . . . . . . . 86
3.6. Разложение целых чисел на множители . . . . . . . . . 89
3.7. Целые числа по модулю m . . . . . . . . . . . . . . . . . 91
3.8. Линейные уравнения по модулю m. Китайская теорема
об остатках . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.9. Точные вычисления, использующие модулярную арифметику
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . 105
3
Стр.3
Г л а в а 4. Элементы теории графов . . . . . . . . . . . . . . . . 107
4.1. Виды и способы задания графов . . . . . . . . . . . . . 107
4.2. Подграфы и части ãðàôà. Операции над графами . . . 113
4.3. Ìàðøðóòû. Достижимость. Связность . . . . . . . . . . 117
4.4. Расстояния в графах . . . . . . . . . . . . . . . . . . . . 122
4.5. Нахождение кратчайших маршрутов . . . . . . . . . . . 124
4.6. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . 128
4.7. Обходы графов . . . . . . . . . . . . . . . . . . . . . . . 129
4.8. Остовы графов . . . . . . . . . . . . . . . . . . . . . . . 132
4.9. Обходы графа по глубине и ширине. Решение задачи
коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . 135
4.10. Упорядоченные и бинарные деревья . . . . . . . . . . . 142
4.11. Фундаментальные циклы . . . . . . . . . . . . . . . . . . 144
4.12. Разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.13. Векторные пространства, связанные с графами . . . . 148
4.14. Раскраски графов . . . . . . . . . . . . . . . . . . . . . . 150
4.15. Планарные графы . . . . . . . . . . . . . . . . . . . . . . 152
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . 154
Г л а в а 5. Комбинаторика . . . . . . . . . . . . . . . . . . . . . . 157
5.1. Перестановки и подстановки . . . . . . . . . . . . . . . . 157
5.2. Размещения и сочетания . . . . . . . . . . . . . . . . . . 160
5.3. Размещения и сочетания с повторением . . . . . . . . . 161
5.4. Разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . 162
5.5. Метод включений и исключений . . . . . . . . . . . . . 164
5.6. Рекуррентные соотношения. Возвратные последовательности
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . 196
Г л а в а 6. Алгебра логики . . . . . . . . . . . . . . . . . . . . . . 170
6.1. Формулы алгебры логики . . . . . . . . . . . . . . . . . 170
6.2. Функции алгебры логики . . . . . . . . . . . . . . . . . 173
6.3. Эквивалентность формул . . . . . . . . . . . . . . . . . 176
6.4. Дизъюнктивные и конъюнктивные нормальные формы 178
6.5. Двухэлементная булева алгебра. Фактор-алгебра алгебры
формул . . . . . . . . . . . . . . . . . . . . . . . . . . 183
6.6. Минимизация булевых функций в классе ДНФ . . . . . 184
6.7. Карты Карно . . . . . . . . . . . . . . . . . . . . . . . . 187
6.8. Принцип двойственности для булевых функций . . . . 191
6.9. Полные системы булевых функций . . . . . . . . . . . . 192
6.10. Функциональная декомпозиция . . . . . . . . . . . . . . 195
6.11. Логические сети . . . . . . . . . . . . . . . . . . . . . . . 202
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . 210
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
П р и л о ж е н и å. Варианты типового расчета . . . . . . . . . . 214
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . 241
Стр.4