Файл: Дискретная математика - учебное пособие.pdf

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

Министерство образования и науки Российской Федерации 

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ 

И РАДИОЭЛЕКТРОНИКИ (ТУСУР) 

 

ФАКУЛЬТЕТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ (ФДО) 

 
 
 
 

Ю. П. Шевелев 

 
 
 
 

 

ДИСКРЕТНАЯ МАТЕМАТИКА 

 

 
 
 
 
 

Учебное пособие 

 
 
 
 
 

 
 
 

Томск 

2017


background image

 

УДК  519.1(075.8) 
ББК  22.174я73 
 

Ш371 

 

Рецензенты: 

С. Я. Гриншпон, д-р физ.-мат. наук, профессор кафедры алгебры механико-

математического факультета Национального исследовательского  

Томского государственного университета; 

Л. И. Магазинников, канд. физ.-мат. наук, профессор кафедры математики 

факультета систем управления Томского государственного университета  

систем управления и радиоэлектроники 

 

Шевелев Ю. П. 

Ш371 

Дискретная  математика  :  учебное  пособие  /  Ю.  П.  Шевелев.  – 

Томск : ФДО, ТУСУР, 2017. – 223 с. 

 

Изложены основные сведения из теории множеств, комбинаторики, тео-

рии графов, булевой алгебры логики. Приведены вводные положения приклад-
ных вопросов теории конечных автоматов, относящихся к теме синтеза комби-
национных  схем,  контактных  структур  и  автоматов  с  памятью.  В  пособие 
включены упражнения для закрепления пройденного материала.  

Для  студентов,  обучающихся  с  применением  дистанционных  образова-

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

 
 
 

 
 

 
 

© Шевелев Ю. П., 2017 

© Оформление. 

ФДО, ТУСУР, 2017 


background image

Оглавление 

Введение ............................................................................................................ 7

 

1 Элементы теории множеств ....................................................................... 9

 

1.1 Понятие множества .................................................................................. 9

 

1.2 Понятие подмножества.......................................................................... 12

 

1.3 Объединение, пересечение и дополнение множеств ......................... 13

 

1.4 Разность и симметрическая разность множеств ................................. 16

 

1.5 Диаграммы Венна .................................................................................. 18

 

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

 

1.7 Заключительные замечания .................................................................. 24

 

2 Элементы комбинаторики ....................................................................... 26

 

2.1 Вводные замечания ................................................................................ 26

 

2.2 Факториал ............................................................................................... 27

 

2.3 Правило произведения в комбинаторике ............................................ 29

 

2.4 Правило суммы в комбинаторике ........................................................ 31

 

2.5 Перестановки без повторений .............................................................. 33

 

2.6 Перестановки с повторениями .............................................................. 36

 

2.7 Размещения без повторений ................................................................. 38

 

2.8 Размещения с повторениями ................................................................. 41

 

2.9 Сочетания без повторений .................................................................... 43

 

2.10 Сочетания с повторениями ................................................................. 51

 

3 Теория графов ............................................................................................. 54

 

3.1 Понятие графа ........................................................................................ 54

 

3.2 Смежность. Инцидентность. Степень вершины ................................. 57

 

3.3 Однородный граф. Полный граф. Дополнение графа ........................ 59

 

3.4 Маршруты, цепи, циклы ........................................................................ 61

 

3.5 Связность графа ..................................................................................... 63

 

3.6 Нахождение простых цепей в простом графе ..................................... 65

 

3.7 Двудольные графы ................................................................................. 67

 

3.8 Двойственные графы ............................................................................. 70

 

3.9 Древовидные графы ............................................................................... 72

 

3.10 О прикладных аспектах теории графов ............................................. 74

 

4 Булева алгебра ............................................................................................ 77

 

4.1 Вводные понятия .................................................................................... 77

 

4.2 Логические операции и формулы ......................................................... 79

 

4.3 Нормальные формы булевых выражений ........................................... 82

 


background image

4.4 Вычисление значений булевых формул .............................................. 83

 

4.5 Основные теоремы алгебры логики ..................................................... 86

 

4.6 Понятие булевой функции .................................................................... 88

 

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

 

4.8 Совершенная конъюнктивная нормальная форма .............................. 93

 

4.9 О формах высших порядков ................................................................. 95

 

4.10 Понятие суперпозиции ........................................................................ 97

 

4.11 О неоднозначности обозначений в булевой алгебре ........................ 98

 

5 Минимизация ДНФ логических формул ............................................ 100

 

5.1 Алгебраическое упрощение булевых формул .................................. 100

 

5.2 Метод Квайна ....................................................................................... 103

 

5.3 Метод Петрика ..................................................................................... 106

 

5.4 Карты Вейча ......................................................................................... 109

 

5.5 Нанесение булевых функций на карту Вейча ................................... 112

 

5.6 Операции над функциями, представленными в СДНФ ................... 113

 

5.7 Минимизация ДНФ при помощи карт Вейча ................................... 116

 

5.8 Примеры минимизации ДНФ булевых формул при помощи  

карт Вейча ............................................................................................ 118

 

5.9 Примеры минимизации ДНФ с учётом неопределённых  

состояний .............................................................................................. 123

 

6 Конъюнктивные формы и другие направления в развитии  

булевой алгебры ....................................................................................... 127

 

6.1 Минимизация конъюнктивных нормальных форм булевых  

функций ................................................................................................ 127

 

6.2 Минимизация КНФ с учётом неопределённых состояний .............. 128

 

6.3 Примеры минимизации КНФ с учётом неопределённых  

состояний .............................................................................................. 130

 

6.4 Алгебра Жегалкина .............................................................................. 132

 

6.5 Упрощение логических выражений в алгебре Жегалкина .............. 134

 

6.6 Производная от булевой функции ...................................................... 137

 

6.7 Дифференцирование булевых функций с применением  

карт Вейча ............................................................................................ 140

 

6.8 Симметрические булевы функции ..................................................... 141

 

7 Булева алгебра и контактные структуры ........................................... 144

 

7.1 Вводные сведения ................................................................................ 144

 

7.2 Тумблеры .............................................................................................. 145

 


background image

7.3 Кнопки ................................................................................................... 145

 

7.4 Электромагнитные реле ...................................................................... 146

 

7.5 Контактная интерпретация булевых формул .................................... 148

 

7.6 Примеры построения контактных схем ............................................. 149

 

7.7 Примеры синтеза простейших контактных структур ...................... 153

 

7.8 Задача о звонке и осветительных лампах .......................................... 159

 

7.9 Инверсные структуры .......................................................................... 161

 

8 Комбинационные схемы ......................................................................... 165

 

8.1 Электронная интерпретация булевых формул.................................. 165

 

8.2 Электрическая схема элемента И ....................................................... 166

 

8.3 Электрическая схема элемента ИЛИ ................................................. 168

 

8.4 Электрическая схема элемента НЕ (инвертора) ............................... 169

 

8.5 Триггер типа RS .................................................................................... 171

 

8.6 Построение комбинационных схем ................................................... 173

 

8.7 О весовых и невесовых кодах ............................................................. 176

 

8.8 Синтез преобразователя весового двоичного кода .......................... 179

 

8.9 О путях дальнейшего упрощения комбинационных схем .............. 182

 

9 Функциональная полнота системы булевых функций .................... 183

 

9.1 Вводные замечания .............................................................................. 183

 

9.2 Монотонные функции ......................................................................... 183

 

9.3 Линейные функции .............................................................................. 184

 

9.4 Самодвойственные функции .............................................................. 186

 

9.5 Функции, сохраняющие единицу ....................................................... 188

 

9.6 Функции, сохраняющие нуль ............................................................. 190

 

9.7 Теорема Поста о функциональной полноте ...................................... 191

 

10 Автоматы с памятью ............................................................................. 194

 

10.1 Вводные замечания ............................................................................ 194

 

10.2 Триггер типа Т .................................................................................... 195

 

10.3 Синтез синхронного автомата на Т-триггерах ................................ 199

 

10.4 Триггер типа JK .................................................................................. 202

 

10.5 Синтез многотактных автоматов на JK-триггерах ......................... 203

 

10.6 Триггер типа D ................................................................................... 206

 

10.7 Автомат с памятью – это сочетание запоминающих элементов  

и комбинационных схем ................................................................... 209

 

Заключение ................................................................................................... 212

 

Литература.................................................................................................... 213