Контрольные вопросы и упражнения................. 103
Обход графа................................................................... 96
Задача определения путей в графах......................... 90
Циклы и разрезы графа.............................................. 84
Характеристики графов............................................. 80
Степени графов............................................................ 77
Операции над графами................................................ 74
Матрицы смежности и инциденций графа.............. 72
Отношения на множествах и графы........................ 70
Основные определения............................................... 60
ТЕОРИЯ ГРАФОВ......................................................... 59
Контрольные вопросы и упражнения..................... 57
Синтез логических схем.............................................. 53
Задача минимизация ДНФ......................................... 43
Полные системы логических функций.................... 38
Булева алгебра.............................................................. 33
Алгебра логики............................................................. 24
МАТЕМАТИЧЕСКАЯ ЛОГИКА................................ 24
Контрольные вопросы и упражнения..................... 22
Отображения множеств.............................................. 20
Бинарные отношения.................................................. 15
Декартово произведение множеств.......................... 13
Системы множеств...................................................... 12
Операции над множествами......................................... 8
Основные определения................................................. 6
ТЕОРИЯ МНОЖЕСТВ.................................................... 6
1.5.1. Определение бинарного отношения......................... 15
1.5.2. Способы задания бинарного отношения.................. 16
1.5.3. Свойства бинарных отношений................................ 18
1.5.4. Отношения эквивалентности.................................... 19
2.1.1. Логические высказывания........................................ 24
2.1.2. Основные логические операции............................... 25
2.1.3. Формулы алгебры логики.......................................... 27
2.1.4. Логические функции.................................................. 30
2.2.1. Булевы функции и операции..................................... 33
2.2.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы 34
2.4.1. Основные определения............................................. 43
2.4.2. Этапы минимизации.................................................. 44
2.4.3. Минимизация ДНФ методом Квайна....................... 49
3.1.1. Общие понятия............................................................ 60
3.1.2. Ориентированные и неориентированные графы.... 61
3.1.3. Маршруты в графах.................................................... 63
3.1.4. Частичные графы и подграфы................................... 65
3.1.5. Связность в графах..................................................... 67
3.1.6. Изоморфизм. Плоские графы.................................... 69
3.4.1. Сумма графов.............................................................. 74
3.4.2. Пересечение графов.................................................... 76
3.5.1. Степени неориентированных графов....................... 77
3.5.2. Степени ориентированных графов........................... 79
3.6.1. Характеристики расстояний в графах...................... 80
3.6.2. Характеристические числа графов........................... 82
3.7.1. Остов и кодерево........................................................ 84
3.7.2. Базисные циклы и разрезающие множества............ 85
3.7.3. Цикломатическая матрица и матрица разрезов....... 87
3.8.1. Определение путей в графе....................................... 90
3.8.2. Алгоритм определения кратчайших путей.............. 91
3.9.1. Эйлеровы маршруты.................................................. 97
3.9.2. Гамильтоновы маршруты......................................... 101
СПИСОК ЛИТЕРАТУРЫ.............................................. 105
ВВЕДЕНИЕ
Для создания и эксплуатации сложных автоматизированных систем обработки информации и их компонент в области экономики, математического и программного обеспечения вычислительной техники, сетей передачи данных и многих других сферах деятельности человека необходимо знание дискретной математики.
Дискретная математика – часть математики, которая зародилась в глубокой древности. Как говорит само название, главной ее особенностью является дискретность, т. е. антипод непрерывности. В ней отсутствует понятие предельного перехода, присущее классической, «непрерывной» математике. Дискретная математика занимается изучением дискретных структур, которые возникают как внутри математики, так и в ее приложениях.
Цель дисциплины «Дискретная математика» – знакомство с основными разделами этой науки: теорией множеств, математической логикой и теорией графов.
Дискретная математика является обязательной дисциплиной цикла «Математические и общие естественнонаучные дисциплины». Знания и навыки, полученные при ее изучении, используются в дисциплинах: «Информатика», «Теория алгоритмов» и т.д.
Данное пособие предназначено для иностранных студентов, обучающихся в Томском политехническом университете по специальностям: 351400 – прикладная информатика (в экономике); 220400 – программное обеспечение вычислительной техники и автоматизированных систем.