МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«Южный федеральный университет»
ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ
В г. ТАГАНРОГЕ
Гладков Л.А, Курейчик В.В., Курейчик В.М.
Дискретная математика
УЧЕБНИк
Под ред. КуреЙчика В.М.
Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы»
Таганрог
2011
УДК: 621.3 + 681.3
Рецензенты:
Кафедра прикладной математики Московского энергетического института, зав. кафедрой, д.т.н., профессор, лауреат премии президента РФ в области образования А.П. Еремеев (г. Москва).
Ю.О. Чернышев, зав. каф. прикладной математики и вычислительной техники Ростовской государственной академии сельскохозяйственного машиностроения, д.т.н., профессор, заслуженный деятель науки РФ (г. Ростов-на-Дону).
Гладков Л.А, Курейчик В. В., Курейчик В. М. Дискретная математика. Учебник / Под ред. В.М. Курейчика. – Таганрог: Изд-во ТТИ ЮФУ, 2011. – 312 с.
NSB №978-5-8327-0309-1
Рассмотрены такие основные разделы дискретной математики, как теория множеств, алгоритмов, алгебра логики, теория графов. Для лучшего усвоения материала использована современная методика обучения на основе “решебников”. Авторы рассмотрели вопросы: исчисления множеств, задания отношений и соответствий, описания упорядоченных бесконечных множеств, мультимножеств и нечетких множеств, основные алгоритмические модели, основные логические функции и законы алгебры логики, виды и способы задания графов, алгоритмы решения задач на ориентированных и неориентированных графах, а также основные определения из теории гиперграфов и нечетких графов. В начале каждой главы приводится краткое изложение теории, затем подробно рассматриваются примеры и задачи с решениями. Приводятся контрольные задачи, упражнения и глоссарий с пояснением основных терминов. Учебник предназначен для студентов вузов, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы». Учебник может быть полезным для специалистов, занятых разработкой интеллектуальных САПР, поддержки и принятия решений, новых информационных технологий в науке, технике, образовании, бизнесе и экономике.
ISBN 978-5-8327-0309-1 © ТТИ ЮФУ, 2011
© Гладков Л.А., Курейчик В. В.,
Курейчик В. М., 2011
Оглавление
Введение 9
Цели и задачи преподавания дисциплины
«Дискретная математика» 13
МОДУЛЬ 1. Основы теории множеств 16
Глава 1. Исчисление множеств 18
1.1. Понятие множества 18
1.2. Способы задания множеств 21
1.3. Подмножество 23
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 25
КОНТРОЛЬНЫЕ ВОПРОСЫ 27
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 28
Глава 2. Операции над множествами 30
2.1. Объединение множеств 30
2.2. Пересечение множеств 30
2.3. Разность множеств 31
2.4. Дополнение множества 34
2.5. Тождества алгебры множеств 35
2.6. Доказательства тождеств с множествами 36
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 38
КОНТРОЛЬНЫЕ ВОПРОСЫ 42
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 42
Глава 3. Упорядоченные множества 45
3.1. Кортеж (Упорядоченное множество) 45
3.2. Декартово произведение 47
3.3. Операция проектирования множеств 49
3.4. График 52
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 56
КОНТРОЛЬНЫЕ ВОПРОСЫ 61
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 62
Глава 4. Отношения 63
4.1. Основные понятия отношений 64
4.2. Основные свойства отношений 65
4.3. Операции над отношениями 66
4.4. Основные свойства специальных отношений 68
4.5. Разбиение множеств 70
4.6. Отношение порядка 72
КОНТРОЛЬНЫЕ ВОПРОСЫ 75
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 76
Глава 5. Соответствия 78
5.1. Определение соответствия 78
5.2. Операции над соответствиями 81
5.3. Понятие образа и прообраза при соответствии 84
5.4. Доказательства тождеств с соответствиями 87
5.5. Основные свойства соответствий 89
5.6. Функция 97
КОНТРОЛЬНЫЕ ВОПРОСЫ 100
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 103
Глава 6. Упорядоченные бесконечные множества 102
6.1. Основные сведения об упорядоченных бесконечных
множествах 102
6.2. Проблема континуума 105
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 110
КОНТРОЛЬНЫЕ ВОПРОСЫ 111
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 112
Глава 7. Основные понятия теории мультимножеств 114
7.1. Понятие мультимножества 114
7.2. Операции над мультимножествами 117
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 122
КОНТРОЛЬНЫЕ ВОПРОСЫ 124
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 124
Глава 8. Нечеткие множества 126
8.1. Нечеткие высказывания 126
8.2. Операции над нечеткими множествами 129
8.3. Нечеткие отношения и соответствия 131
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 134
КОНТРОЛЬНЫЕ ВОПРОСЫ 140
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 142
ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 1 142
ГЛОССАРИЙ К МОДУЛЮ 1 152
МОДУЛЬ 2. Основы теории алгоритмов 163
Глава 9. Введение в теорию алгоритмов 164
9.1. Понятие алгоритма 164
9.2. Основные свойства алгоритмов 167
9.3. Классификация алгоритмов 169
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 173
КОНТРОЛЬНЫЕ ВОПРОСЫ 176
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 177
Глава 10. Универсальные алгоритмические модели 178
10.1. Преобразование слов в произвольных абстрактных
алфавитах 178
10.2. Числовые функции 181
10.3. Построение алгоритмов по принципу «разделяй и
властвуй» 184
10.4. Представление алгоритма в виде детерминированного устройства 185
10.5. Универсальные схемы алгоритмов 188
10.6. «Жадные» алгоритмы 204
10.7. Нечеткие (расплывчатые) алгоритмы 206
КОНТРОЛЬНЫЕ ВОПРОСЫ 209
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 211
Глава 11. Сложность алгоритмов 213
11.1. Анализ алгоритмов 213
11.2. Сложность алгоритмов 221
КОНТРОЛЬНЫЕ ВОПРОСЫ 225
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 226
ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 2 227
ГЛОССАРИЙ К МОДУЛЮ 2 230
МОДУЛЬ 3. АЛГЕБРА ЛОГИКИ 236
Глава 12. Элементы алгебры логики 237
12.1. Логические функции 238
12.2. Основные логические тождества и законы 245
12.3. Булевы функции одной и двух переменных 248
КОНТРОЛЬНЫЕ ВОПРОСЫ 252
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 253
Глава 13. Нормальные формы булевых функций 255
13.1. Дизъюнктивная и конъюнктивная нормальные формы 255
13.2. Способы перехода от нормальных к совершенным
нормальным формам 2609
13.3. Алгебра Жегалкина 263
13.4. Функциональная полнота БФ 264
КОНТРОЛЬНЫЕ ВОПРОСЫ 266
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 267
Глава 14. Логические схемы 269
14.1. Реализация булевых функций 269
14.2. Минимизация булевых функций 273
14.3. Карты Карно 277
14.4. Метод Квайна-МакКласски 283
14.5. Переход от БФ к простейшим комбинационным схемам 289
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 289
КОНТРОЛЬНЫЕ ВОПРОСЫ 291
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 291
ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 3 292