ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9306
Скачиваний: 93
Министерство образования Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ
УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизации обработки информации (АОИ)
З.А. Смыслова
ДИСКРЕТНАЯ
МАТЕМАТИКА
Учебное пособие
2000
Смыслова З.А.
Дискретная математика: Учебное пособие. - Томск: Томский межвузовский
центр дистанционного образования, 2000. - 116 с.
Данное учебное пособие содержит теоретический материал по теории
множеств и комбинаторике, математической логике, основам теории гра-
фов, а также варианты двух контрольных работ для студентов специально-
сти 061000 "Государственное и муниципальное управление", обучающихся
по дистанционной форме. Приведены примеры решения задач контроль-
ных работ.
Пособие может быть использовано для студентов заочной и дневной
форм обучения.
© Смыслова З.А., 2000
© Томский межвузовский центр
дистанционного образования, 2000
3
СОДЕРЖАНИЕ
1. Теория множеств………………………………………………………... 6
1.1. Множества и операции над ними…………………………………… 6
1.1.1. Понятие множества………………..………………………….. 6
1.1.2. Способы задания множеств……...…………………………… 6
1.1.3. Основные определения……………………………………….. 6
1.1.4. Диаграммы Эйлера – Венна ………………………………….
7
1.1.5. Операции над множествами ………………………………….
7
1.1.6. Системы множеств ……………………………………………
8
1.1.7. Законы алгебры множеств ……………………………………
9
1.1.8. Решение задач 1-3 контрольной работы № 1…….………….
10
1.1.9. Контрольные вопросы и упражнения ……………………….
12
1.2. Бинарные отношения ………………………………………………..
13
1.2.1. Декартово произведение множеств ………………………….
13
1.2.2. Определение бинарного отношения …………………………
14
1.2.3. Способы задания бинарного отношения ……………………
15
1.2.4. Свойства бинарных отношений ……………………………..
16
1.2.5. Отношения эквивалентности …………………………………
17
1.2.6. Отношения порядка …………………………………………..
18
1.2.7. Решение задачи 4 контрольной работы № 1 ………………...
19
1.2.8. Контрольные вопросы и упражнения ……………………….
21
1.3. Реляционная алгебра ………………………………………………..
22
1.3.1. Применение отношений для обработки данных ……………
22
1.3.2. Теоретико-множественные операции реляционной алгебры
22
1.3.3. Специальные операции реляционной алгебры ……………..
24
1.3.4. Решение задачи 5 контрольной работы № 1 ………………...
25
1.3.5. Контрольные вопросы и упражнения ………………………..
26
1.4. Конечные и бесконечные множества ………………………………
27
1.4.1. Биекция ………………………………………………………..
27
1.4.2. Равномощные множества …………………………………….
27
1.4.3. Классы равномощных множеств …………………………….
28
1.4.4. Сравнение множеств по мощности …………………………..
28
1.4.5. Определение конечного множества ………………………….
30
1.4.6. Свойства конечных множеств ………………………………..
30
1.4.7. Определение счетного множества …………………………...
33
1.4.8. Свойства счетных множеств …………………………………
34
1.4.9. Несчетные множества ………………………………………..
36
1.4.10. Выводы ………………………………………………………
37
1.4.11. Решение задачи 6 контрольной работы № 1 ………………
38
1.4.12. Контрольные вопросы и упражнения ………………………
39
1.5. Комбинаторика ………………………………………………………
40
1.5.1. Задачи комбинаторики ……………………………………….
40
1.5.2. Типы выборок …………………………………………………
40
1.5.3. Основные правила комбинаторики ………………………….
41
4
1.5.4. Размещения с повторениями …………………………………
42
1.5.5. Размещения без повторений …………………………………
42
1.5.6. Перестановки без повторений ……………………………….
43
1.5.7. Перестановки с повторениями ………………………………
43
1.5.8. Сочетания ……………………………………………………..
44
1.5.9. Сочетания с повторениями …………………………………...
45
1.5.10. Решение задач 7,8 контрольной работы № 1 ………………
46
1.5.11. Бином Ньютона ………………………………………………
47
1.5.12. Свойства биноминальных коэффициентов ………………..
48
1.5.13. Контрольные вопросы и упражнения ………………………
50
2. Элементы математической логики …..………………………………
52
2.1. Логика высказываний ……………………………………………….
52
2.1.1. История математической логики ….…………………………
52
2.1.2. Понятие высказывания ………………………………………
52
2.1.3. Операции над высказываниями ……………………………..
53
2.1.4. Таблицы истинности …………………………………………
53
2.1.5. Формулы логики высказываний ……………………………..
54
2.1.6. Равносильные преобразования формул ……………………..
55
2.1.7. Решение задач контрольной работы № 2 ……………………
56
2.1.8. Контрольные вопросы и упражнения ……………………….
58
2.2. Логические рассуждения ……………………………………………
58
2.2.1. Определение логически правильного рассуждения ………..
58
2.2.2. Проверка правильности логического рассуждения ………...
60
2.2.3. Прямые и косвенные методы доказательств ………………..
63
2.2.4. Решение задачи контрольной работы № 2 …...……………..
64
2.2.5. Контрольные вопросы и упражнения ……………………….
66
2.3. Логика предикатов …………………………………………………..
66
2.3.1. Понятие предиката ……………………………………………
66
2.3.2. Кванторы ………………………………………………………
67
2.3.3. Формулы логики предикатов………………………………… 68
2.3.4. Равносильные преобразования формул ……………………..
69
2.3.5. Рассуждения в логике предикатов …………………………...
70
2.3.6. Решение задачи контрольной работы № 2 …………………..
71
2.3.7. Контрольные вопросы и упражнения ………………………..
71
3. Основы теории графов ………………...………………………………. 72
3.1. Ориентированные графы .…………………………………………...
72
3.1.1. Основные понятия ……………………………………………
72
3.1.2. Орграфы и бинарные отношения ……………………………
72
3.1.3. Матрицы орграфа …………...………………………………...
73
3.1.4. Решение задачи 5 контрольной работы № 2 ………………...
74
3.1.5. Контрольные вопросы и упражнения ………………………..
75
3.2. Неориентированные графы …………………………………………
76
3.2.1. Основные термины ……………………………………………
76
3.2.2. Матрицы графа …………………………………………….….
77
3.2.3. Решение задачи 6 контрольной работы № 2 ………………...
78
3.2.4. Контрольные вопросы и упражнения ………………………..
79
5
3.3. Планарные графы ………...………………………………………….
79
3.3.1. Изоморфизм графов ……………………………………….….
79
3.3.2. Планарность …………………………………………………...
80
3.3.3. Критерий планарности ………………………………………..
81
3.3.4. Решение задачи 7 контрольной работы № 2 ………………...
82
3.3.5. Контрольные вопросы и упражнения ………………………..
83
3.4. Связность графов …………………………………………………….
83
3.4.1. Маршруты ……………………………………………………..
83
3.4.2. Компоненты связности ……………………………………….
84
3.4.3. Эйлеровы цепи и циклы ………………………………………
85
3.4.4. Цикломатическое число ………………………………………
86
3.4.5. Решение задачи 8 контрольной работы № 2 ………………...
87
3.4.6. Контрольные вопросы и упражнения ………………………..
88
3.5. Графы без циклов ……………………………………………………
89
3.5.1. Дерево и лес …………………………………………………...
89
3.5.2. Свойства деревьев …………………………………………….
89
3.5.3. Каркасы графа …………………………………………………
90
3.5.4. Обход графа “в ширину” ………………………………….….
91
3.5.5. Обход графа “в глубину” ………………………………….….
92
3.5.6. Решение задачи 9 контрольной работы № 2 ………………...
93
3.5.7. Контрольные вопросы и упражнения …………………….….
94
Приложение 1. Контрольная работа № 1…………………………….….
95
Приложение 2. Контрольная работа № 2………………………….…….
106