МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«Южный федеральный университет»
ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В г. ТАГАНРОГЕ
Гладков Л.А, Курейчик В.В., Курейчик В.М.
Дискретная математика
УЧЕБНИк
Под ред. КуреЙчика В.М.
Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы»
Таганрог
20 11
УДК: 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
Понятие множества 18
Способы задания множеств 21
Подмножество 23
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 25
КОНТРОЛЬНЫЕ ВОПРОСЫ 27
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 28
Глава 2. Операции над множествами 30
Объединение множеств 30
Пересечение множеств 30
Разность множеств 31
Дополнение множества 34
Тождества алгебры множеств 35
Доказательства тождеств с множествами 36
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 38
КОНТРОЛЬНЫЕ ВОПРОСЫ 42
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 42
Глава 3. Упорядоченные множества 45
Кортеж (Упорядоченное множество) 45
Декартово произведение 47
Операция проектирования множеств 49
График 52
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ 56
КОНТРОЛЬНЫЕ ВОПРОСЫ 61
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 62
Глава 4. Отношения 63
Основные понятия отношений 64
Основные свойства отношений 65
Операции над отношениями 66
Основные свойства специальных отношений 68
Разбиение множеств 70
Отношение порядка 72
КОНТРОЛЬНЫЕ ВОПРОСЫ 75
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 76
Глава 5. Соответствия 78
Определение соответствия 78
Операции над соответствиями 81
Понятие образа и прообраза при соответствии 84
Доказательства тождеств с соответствиями 87
Основные свойства соответствий 89
Функция 97
КОНТРОЛЬНЫЕ ВОПРОСЫ 100
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 103
Глава 6. Упорядоченные бесконечные множества 102
