- •Введение
- •Глава 1. Множества, отношения и функции
- •1. Задание множества
- •2. Операции над множествами
- •3. Разбиение множества. Декартово произведение
- •4. Отношения
- •5. Операции над отношениями
- •6. Функция
- •7. Отношение эквивалентности. Фактор-множество
- •8. Отношения порядка
- •9. Вопросы и темы для самопроверки
- •10. Упражнения
- •Глава 2. Алгебраические структуры
- •1. Операции и предикаты
- •2. Алгебраическая система. Алгебра. Модель
- •3. Подалгебры
- •4. Морфизмы алгебр
- •5. Алгебра с одной операцией
- •6. Группы
- •7. Алгебра с двумя операциями. Кольцо
- •8. Кольцо с единицей
- •9. Поле
- •10. Решетки
- •11. Булевы алгебры
- •12. Матроиды
- •13. Вопросы и темы для самопроверки
- •14. Упражнения
- •Глава 3. Булевы функции
- •2. Формулы
- •3. Упрощения в записях формул
- •4. Равносильность формул
- •5. Важнейшие пары равносильных формул
- •6. Зависимости между булевыми функциями
- •7. Свойства операций штрих Шеффера, стрелка Пирса и сложения по модулю два
- •8. Элементарные суммы и произведения. Конституенты нуля и единицы
- •9. Дизъюнктивные и конъюнктивные нормальные формы
- •10. Представление произвольной булевой функции в виде формул
- •11. Совершенные нормальные формы
- •12. Полином Жегалкина
- •13. Сокращенные дизъюнктивные нормальные формы
- •14. Метод Квайна получения сокращенной д.н.ф.
- •15. Тупиковые и минимальные д.н.ф.
- •16. Метод импликантных матриц
- •17. Минимальные конъюнктивные нормальные формы
- •18. Полнота системы функций. Теорема Поста
- •21. Функциональная декомпозиция
- •22. Вопросы и темы для самопроверки
- •23. Упражнения
- •Глава 4. Элементы комбинаторики
- •1. Правило суммы для конечных множеств
- •2. Правило произведения для конечных множеств
- •3. Выборки и упорядочения
- •5. Число всевозможных разбиений конечного множества. Полиномиальная теорема
- •6. Метод включения и исключения
- •7. Задача о беспорядках и встречах
- •8. Системы различных представителей
- •9. Вопросы и темы для самоконтроля
- •10. Упражнения по комбинаторике
- •Глава 5. Теория графов
- •1. Основные типы графов
- •2. Изоморфизм графов
- •3. Число ребер графа
- •4. Цепи, циклы, пути и контуры
- •5. Связность графа. Компоненты связности
- •6. Матрица смежности
- •7. Матрицы смежности и достижимости
- •8. Критерий изоморфизма графов
- •9. Матрица инциденций
- •10. Деревья
- •11. Задача о минимальном соединении
- •12. Центры дерева
- •13. Ориентированные деревья
- •14. Эйлеровы графы
- •15. Гамильтоновы графы
- •16. Планарные графы
- •17. Задача о кратчайшей цепи между произвольными вершинами графа
- •18. Алгоритм Дейкстры нахождения кратчайших путей от заданной вершины орграфа
- •19. Потоки в сетях
- •20. Вопросы и темы для самопроверки
- •21. Упражнения
- •Список литературы
Ш. И. ГАЛИЕВ
ДИСКРЕТНАЯ
МАТЕМАТИКА
УЧЕБНОЕ ПОСОБИЕ
1
Министерство образования и науки Российской Федерации
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А. Н. ТУПОЛЕВА
Ш. И. ГАЛИЕВ
ДИСКРЕТНАЯ МАТЕМАТИКА
УЧЕБНОЕ ПОСОБИЕ
Рекомендовано к изданию в качестве учебного пособия Учебно-методическим центром
КГТУ им. А. Н. Туполева
Казань 2005
2
УДК 519.1(075.8) ББК 22.176я73
С89
Галиев Ш. И. Дискретная математика. Казань: Изд-во Мастер Лайн. 2005. 174 с.
Включены разделы: множества, отношения и функции; алгебры, в том числе группы, кольца, решётки и матроиды; булевые функции, их различные разложения, минимизация, декомпозиция, а также выяснение полноты систем булевых функций; элементы комбинаторики и элементы теории графов.
Все главы снабжены контрольными вопросами и упражнениями. Предназначено студентам технических вузов по специальности 2202
направления «Информатика и вычислительная техника» и может быть использовано для специальности 2204 и других специальностей данного направления.
Ил. 60. Библиогр.: 22 назв.
Рецензенты: кафедра математического анализа (Казанский государственный педагогический университет); докт.физ.-мат. наук. Я. И. Заботин (Казанский государственный университет)
С Изд-во Мастер Лайн, 2005
С Ш. И. Галиев, 2005
3
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ……………………………………………………….. 6
Глава 1. МНОЖЕСТВА, ОТНОШЕНИЯ И ФУНКЦИИ |
8 |
§1. Задание множества……………………………………….. 8
§2. Операции над множествами……………………………... 11
§3. Разбиение множества. Декартово произведение……….. 13
§4. Отношения………………………………………………... 14
§5. Операции над отношениями…………………………….. 17
§6. Функции…………………………………………………... 19
§7. Отношение эквивалентности. Фактор-множество……... 21
§ 8. Отношение порядка……………………………………… 25
§9. Вопросы и темы для самопроверки…………………….. 26
§10. Упражнения……………………………………………... 26
Глава 2. АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ……………….. 31
§1. Операции и предикаты…………………………………... 31
§2. Алгебраическая система. Алгебра. Модель……………. 32
§3. Подалгебры……………………………………………….. 33
§4. Морфизмы алгебр………………………………………… 34
§5. Алгебра с одной операцией……………………………… 36
§6. Группы……………………………………………………. 37
§7. Алгебры с двумя операциями. Кольцо…………………. 40
§8. Кольцо с единицей……………………………………….. 42
§9. Поле……………………………………………………….. 43
§10. Решётки………………………………………………….. 44
§11. Булевы алгебры…………………………………………. 46
§12. Матроиды………………………………………………... 47
§13. Вопросы и темы для самопроверки……………………. 48
§14. Упражнения……………………………………………... 49
Глава 3. БУЛЕВЫ ФУНКЦИИ………………………………… |
54 |
§ 1. Основные булевы функции……………………………… |
54 |
§2. Формулы………………………………………………….. 56
§3. Упрощения в записях формул…………………………… 58
§4. Равносильность формул…………………………………. 59
§5. Важнейшие пары равносильных формул………………. 60
§6. Зависимости между булевыми функциями…………….. 62
§7. Свойства операций штрих Шеффера, стрелка Пирса и
сложения по модулю два………………………………… 64 § 8. Элементарные суммы и произведения. Конституенты
4
нуля и единицы…………………………………………. 65 § 9. Дизъюнктивные и конъюнктивные нормальные
формы……………………………………………………. 67 § 10. Представление произвольной булевой функции в виде
формул…………………………………………………….. 68
§11. Совершенные нормальные формы…………………….. 70
§12. Полином Жегалкина……………………………………. 72
§13. Сокращенные дизъюнктивные нормальные формы….. 73
§ 14. Метод Квайна получения сокращенной д.н.ф………… |
75 |
§ 15. Тупиковые и минимальные д.н.ф……………………… |
76 |
§ 16. Метод импликантных матриц………………………… |
78 |
§17. Минимальные конъюнктивные нормальные формы…. 81
§18. Полнота систем функций. Теорема Поста…………….. 82
§19. Приложение булевых функций к анализу и синтезу контактных (переключательных) схем………………... 86
§20. Приложение булевых функций к анализу и синтезу
схем из функциональных элементов…………………. 88 § 21. Функциональная декомпозиция……………………….. 91 § 22. Вопросы и темы для самопроверки…………………… 95 § 23. Упражнения…………………………………………….. 95
Глава 4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ………………… |
103 |
§ 1. Правило суммы для конечных множеств……………… |
103 |
§2. Правило произведения для конечных множеств………. 104
§3. Выборки и упорядочения……………………………….. 105
§4. Биномиальная теорема………………………………….. 107
§5. Число возможных разбиений конечного множества Полиномиальная теорема………………………………. 109
§6. Метод включения и исключения……………………….. 110
§7. Задача о беспорядках и встречах……………………….. 113
§8. Системы различных представителей…………………... 114
§9. Вопросы и темы для самопроверки……………………. 116
§10. Упражнения…………………………………………….. 116
Глава 5. ТЕОРИЯ ГРАФОВ……………………………………. |
119 |
|
§ 1. Основные типы графов………………………………….. |
120 |
|
§ 2. Изоморфизм графов……………………………………… |
124 |
|
§ 3. |
Число ребер графа……………………………………….. |
125 |
§ 4. |
Цепи, циклы, пути и контуры…………………………… |
126 |
§ 5. |
Связность графа. Компоненты связности……………… |
128 |
§ 6. |
Матрица смежности……………………………………… 130 |
§7. Матрицы смежности и достижимости………………….. 134
§8. Критерий изоморфизма графов…………………………. 136
§9. Матрица инциденций……………………………………. 139
5 |
|
§ 10. Деревья………………………………………………….. |
142 |
§ 11. Задача о минимальном соединении…………………… |
145 |
§12. Центры дерева………………………………………….. 149
§13. Ориентированные деревья…………………………….. 150
§14. Эйлеровы графы………………………………………... 152
§15. Гамильтоновы графы…………………………………... 155
§16. Планарные графы………………………………………. 156
§17. Задача о кратчайшей цепи между произвольными вершинами графа……………………………………….. 160
§18. Алгоритм Дейкстры нахождения кратчайших путей
от заданной вершины орграфа………………..……….. 162 § 19. Потоки в сетях………………………………………….. 165 § 20. Вопросы и темы для самопроверки…………………… 167 § 21. Упражнения…………………………………………….. 168
СПИСОК ЛИТЕРАТУРЫ……………………………………... 173
6
ВВЕДЕНИЕ
Дискретная математика – это раздел математики, в котором изучаются свойства структур конечного характера, а также бесконечных структур, в которых наблюдается скачкообразность происходящих в них процессов. Бурное развитие дискретной математики обусловлено необходимостью разработки математических моделей и методов для современных компьютерных и информационных технологий, а также представлениями различных моделей на компьютерах, являющихся по своей природе конечными (дискретными) структурами.
Вглаве 1 рассматривается понятие множества, даётся аксиоматика теории множеств, позволяющая избегать известных парадоксов и получать результаты, строгость которых находится на современном уровне. Определяется понятие отношения на множествах, устанавливаются некоторые свойства отношений. Рассматриваются важнейшие отношения, такие как отношение эквивалентности и отношения порядка. Вводится понятие функции и рассматриваются её некоторые свойства.
Вглаве 2 приводятся понятия алгебраической системы, алгебры и модели. Вводятся отображения алгебр (изоморфизм и гомоморфизм). Рассматриваются классические алгебры – группы и кольца и изучаются некоторые их свойства. Также даются понятия о решетках, булевых алгебрах
иматроидах.
Глава 3 посвящена теории булевых функций. Вводятся элементарные булевы функции, их свойства. Определяются различные нормальные формы и приводятся некоторые методы их получения, в частности, даны алгоритмы минимизации булевых функций. Вводится понятие полноты систем булевых функций и приведен критерий полноты. Даны некоторые приложения теории булевых функций.
В главе 4 приведены элементы комбинаторики. Здесь рассматриваются начальные понятия комбинаторики и некоторые формулы, без которых не обходится ни одна книга по комбинаторике.
В главе 5 излагаются основы теории графов (неориентированных и ориентированных). Приводятся задачи теории графов, являющиеся математическими моделями ряда прикладных задач.
Каждая глава содержит вопросы и темы для самопроверки и упражнения (задачи), для выработки навыков их решения.
При написании пособия использована литература [1-19], интернетстраницы [20-23] и, естественно, другие источники.
7
Автор выражает благодарность доценту Л. Г. Амбарцумову за полезные обсуждения некоторых тем пособия и своим студентам за помощь по набору текста пособия.