ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 22012
Скачиваний: 221
Министерство образования и науки Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ
И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
ФАКУЛЬТЕТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ (ФДО)
Ю. П. Шевелев
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Томск
2017
УДК 519.1(075.8)
ББК 22.174я73
Ш371
Рецензенты:
С. Я. Гриншпон, д-р физ.-мат. наук, профессор кафедры алгебры механико-
математического факультета Национального исследовательского
Томского государственного университета;
Л. И. Магазинников, канд. физ.-мат. наук, профессор кафедры математики
факультета систем управления Томского государственного университета
систем управления и радиоэлектроники
Шевелев Ю. П.
Ш371
Дискретная математика : учебное пособие / Ю. П. Шевелев. –
Томск : ФДО, ТУСУР, 2017. – 223 с.
Изложены основные сведения из теории множеств, комбинаторики, тео-
рии графов, булевой алгебры логики. Приведены вводные положения приклад-
ных вопросов теории конечных автоматов, относящихся к теме синтеза комби-
национных схем, контактных структур и автоматов с памятью. В пособие
включены упражнения для закрепления пройденного материала.
Для студентов, обучающихся с применением дистанционных образова-
тельных технологий. Пособие может быть полезно студентам очной и вечерней
форм обучения, учащимся старших классов общеобразовательных школ и всем
тем, кто намерен самостоятельно освоить вводные положения дискретной ма-
тематики.
© Шевелев Ю. П., 2017
© Оформление.
ФДО, ТУСУР, 2017
3
Оглавление
Введение ............................................................................................................ 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
4
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
5
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