ТЕОРИЯ МНОЖЕСТВ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные определения............................................... 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

Отношения на множествах и графы........................ 70

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

ТЕОРИЯ МНОЖЕСТВ