Ш. И. ГАЛИЕВ

ДИСКРЕТНАЯ

МАТЕМАТИКА

УЧЕБНОЕ ПОСОБИЕ

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

Автор выражает благодарность доценту Л. Г. Амбарцумову за полезные обсуждения некоторых тем пособия и своим студентам за помощь по набору текста пособия.