375

В. Ф. Пономарев

Дискретная математика

для инженеров

УДК 519.45

ПОНОМАРЕВ В.Ф. Дискретная математика для инженера.

В книге изложены основы теории множеств и отношений, булевой алгебры и комбинаторики, графов и автоматов, математической логики и алгоритмов. Основные разделы изложены для “четких” и “нечетких” множеств. Каждый раздел иллюстрируется многочисленными примерами.

Книга предназначена инженерам, как инструмент в их творческой деятельности, и может служить учебным пособием студентам в изучении основных разделов дискретной математики и в освоении инженерных способов решения практических задач.

Оглавление

В. Ф. Пономарев 1

УДК 519.45 2

Оглавление 3

Введение 15

Глава 1. Алгебраические системы 17

1.1 Множества 17

1.1.1. Четкие множества 18

1.1.2. Нечеткие множества 22

1.2. Соответствия, отображения и функции 25

1.2.1. Четкие отображения и функции 25

таблица 1.3 27

1.2.2. Нечеткие отображения 29

1.3. Отношение 30

1.3.1. Четкие отношения 31

1.3.2. Нечеткое отношение 34

1.4. Элементы общей алгебры 34

1.5. Булева алгебра 36

1.5.1. Булевы операции 36

1.5.2. Законы булевой алгебры 37

1.5.3. Формула булевой функции 37

1.5.4. Описание булевой функции 38

1.5.5. Суперпозиция булевых функций 44

1.5.6. Свойства булевых функций 46

1.5.6.1. Самодвойственные булевы функции 46

1.5.6.2. Монотонные булевы функции 47

1.5.6.3. Линейные булевы функции 47

1.5.6.4. Функции, сохраняющие “0” 49

1.5.6.6. Функционально полные системы 49

1.5.7. Разложение булевых функции 51

1.5.7.1. ДНФ булевой функции 52

1.5.7.2. КНФ булевой функции 53

1.5.8. Минимизация булевых функций. 55

1.5.8.1.Минимизация ДНФ булевой функции 56

1.5.8.2. Минимизация КНФ булевой функции 58

1.6. Алгебра четких множеств 60

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

1.6.2. Законы алгебры множеств 68

1.6.3. Эквивалентные преобразования формул 68

F=(CABD)(CA)(CB)(CD); 68

F=(CABD)(CA)(C(BD)); 68

1.6.4. Композиция отображений и отношений 70

1.6.5. Поиск неизвестного множества 70

1.7. Алгебра нечетких множеств 73

1.7.1. Операции над нечеткими множествами 73

1.7.2. Композиция нечетких отображений 79

1.7.3. Композиция нечетких отношений 81

1.7.4. Свойства нечетких отношений 81

Вопросы и задачи 84

Глава 2. Элементы комбинаторики 88

2.1. Размещение из n элементов по k 89

2.2. Перестановка элементов 90

2.3 Сочетание из n элементов по k 90

2.4. Разбиение множества 92

2. 5 Правила комбинаторики 96

Вопросы и задачи 100

Глава 3. Основы теории графов 101

3.1. Граф и его характеристики 102

3.2. Описание графа 110

3. 3. Числа графа 116

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

3.4.1. Унарные операции 120

3.4.1.1 Поиск дополнительного графа 121

3.4.1.2. Введение и удаление вершин графа 121

3.4.1.3. Стягивание вершин графа 121

3.4.1.4. Введение и удаление ребер графа 122

3.4.1.5. Поиск плотности и неплотности графа 122

3.4.1.6. Поиск числа компонент связности графа 124

3.4.1.7. Поиск устойчивости графа 127

3.4.1.8. Поиск цикломатического числа графа 130

3.4.1.9. Поиск хроматического числа графа 131

3.4.2. Бинарные операции 132

3.4.2.1. Объединение графов 132

3.4.2.2. Пересечение графов 134

3.4.2.3. Композиция графов 135

3.4.2.4. Соединение графов 136

3.4.2.5. Прямое произведение графов 136

3.4.2.6. Изоморфизм графов 137

3.5. Некоторые алгоритмы на графах 139

3.5.1. Построение покрывающего остова 139

3.5.2. Построение остова минимального веса 142

3.5.3. Поиск кратчайших путей в сети. 145

3.5.4. Поиск максимального потока в сети 149

3.5.5. Метод критического пути в управлении 154

3.6. Нечеткие графы 160

Вопросы и задачи 162