Содержание

ВВЕДЕНИЕ 5

1. ТЕОРИЯ МНОЖЕСТВ 6

1.1. Основные определения 6

1.2. Операции над множествами 8

1.3. Системы множеств 12

1.4. Декартово произведение множеств 13

1.5. Бинарные отношения 15

1.5.1. Определение бинарного отношения 15

1.5.2. Способы задания бинарного отношения 16

1.5.3. Свойства бинарных отношений 18

1.5.4. Отношения эквивалентности 19

1.6. Отображения множеств 20

1.7. Контрольные вопросы и упражнения 22

2. МАТЕМАТИЧЕСКАЯ ЛОГИКА 24

2.1. Алгебра логики 24

2.1.1. Логические высказывания 24

2.1.2. Основные логические операции 25

2.1.3. Формулы алгебры логики 27

2.1.4. Логические функции 30

2.2. Булева алгебра 33

2.2.1. Булевы функции и операции 33

2.2.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы 34

2.3. Полные системы логических функций 38

2.4. Задача минимизация ДНФ 43

2.4.1. Основные определения 43

2.4.2. Этапы минимизации 44

2.4.3. Минимизация ДНФ методом Квайна 49

2.5. Синтез логических схем 53

2.6. Контрольные вопросы и упражнения 57

3. ТЕОРИЯ ГРАФОВ 59

3.1. Основные определения 60

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.2. Отношения на множествах и графы 70

3.3. Матрицы смежности и инциденций графа 72

3.4. Операции над графами 74

3.4.1. Сумма графов 74

3.4.2. Пересечение графов 76

3.5. Степени графов 77

3.5.1. Степени неориентированных графов 77

3.5.2. Степени ориентированных графов 79

3.6. Характеристики графов 80

3.6.1. Характеристики расстояний в графах 80

3.6.2. Характеристические числа графов 82

3.7. Циклы и разрезы графа 84

3.7.1. Остов и кодерево 84

3.7.2. Базисные циклы и разрезающие множества 85

3.7.3. Цикломатическая матрица и матрица разрезов 87

3.8. Задача определения путей в графах 90

3.8.1. Определение путей в графе 90

3.8.2. Алгоритм определения кратчайших путей 91

3.9. Обход графа 96

3.9.1. Эйлеровы маршруты 97

3.9.2. Гамильтоновы маршруты 101

3.10. Контрольные вопросы и упражнения 103

СПИСОК ЛИТЕРАТУРЫ 105

ВВЕДЕНИЕ

Для создания и эксплуатации сложных автоматизированных систем обработки информации и их компонент в области экономи­ки, математического и программного обеспечения вычислительной техники, сетей передачи данных и многих других сферах деятель­ности человека необходимо знание дискретной математики.

Дискретная математика – часть математики, которая зароди­лась в глубокой древности. Как говорит само название, главной ее особенностью является дискретность, т. е. антипод непрерывности. В ней отсутствует понятие предельного перехода, присущее классиче­ской, «непрерывной» математике. Дискретная математика занимает­ся изучением дискретных структур, которые возникают как внутри математики, так и в ее приложениях.

Цель дисциплины «Дискретная математика» – знакомство с ос­новными разделами этой науки: теорией множеств, математической логикой и теорией графов.

Дискретная математика является обязательной дисциплиной цикла «Математические и общие естественнонаучные дисциплины». Знания и навыки, полученные при ее изучении, используются в дис­циплинах: «Информатика», «Теория алгоритмов» и т.д.

Данное пособие предназначено для иностранных студентов, обучающихся в Томском политехническом университете по специальностям: 351400 – прикладная информатика (в экономике); 220400 – программное обеспечение вычислительной техники и автомати­зированных систем.