ДМ_Конспект
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ
УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ
КОНСПЕКТ ЛЕКЦИЙ
по дисциплине
«ДИСКРЕТНАЯ МАТЕМАТИКА»
для студентов всех форм обучения направления 6.050101 – «Компьютерные науки»
Электронное издание
УТВЕРЖДЕНО кафедрой «ИУС»
Протокол № 1 от 29.08.2013 г. кафедрой «ИИ» Протокол № 1 от 31.08.2013 г.
ХАРЬКОВ 2013
1
Конспект лекций по дисциплине «Дискретная математика» для студентов всех форм обучения направления 6.050101 – «Компьютерные науки» [Электронное издание] / Состав. Н.В. Васильцова, Л.Э. Чалая. – Харьков:
ХНУРЭ, 2013. – 293 с.
Составители |
Н.В. Васильцова |
|
Л.Э. Чалая |
2
СОДЕРЖАНИЕ
ЛЕКЦИЯ 1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ. ОСНОВНЫЕ ПОНЯТИЯ И
ОБОЗНАЧЕНИЯ ТЕОРИИ МНОЖЕСТВ............................................................... |
10 |
|
1.1 |
Интуитивное понятие множества ................................................................. |
10 |
1.2 |
Элементы множества ...................................................................................... |
10 |
1.3 |
Конечные, бесконечные, счетные множества .............................................. |
12 |
1.4 |
Пустое и универсальное множества.............................................................. |
13 |
1.5 |
Мощность множества ..................................................................................... |
14 |
1.6 |
Способы задания множеств............................................................................ |
15 |
1.7 |
Множество и подмножество .......................................................................... |
18 |
1.8. Контрольные вопросы и задания .................................................................. |
20 |
|
ЛЕКЦИЯ 2 АЛГЕБРА МНОЖЕСТВ....................................................................... |
20 |
|
2.1 |
Геометрическая интерпретация множеств. Круги Эйлера и диаграммы |
|
Венна....................................................................................................................... |
20 |
|
2.2 |
Операции на множествах................................................................................ |
22 |
2.3 |
Общее определение алгебры.......................................................................... |
25 |
2.4 |
Понятие алгебры множеств. Аксиомы алгебры множеств ......................... |
27 |
2.5 |
Принцип двойственности ............................................................................... |
28 |
2.6 |
Тождественные преобразования формул алгебры множеств ..................... |
29 |
2.7 |
Контрольные вопросы и задания ................................................................... |
29 |
ЛЕКЦИЯ 3 ОТНОШЕНИЯ И ИХ СВОЙСТВА. ОТНОШЕНИЯ И ОПЕРАЦИИ
НАД НИМИ. .............................................................................................................. |
30 |
|
3.1 |
Декартово произведение множеств ............................................................... |
30 |
3.2 |
Понятие отношений. Бинарные и n-арные отношения ............................... |
32 |
3.3 |
Область определения и область значений отношений................................ |
33 |
3.4 |
Способы задания отношений ......................................................................... |
34 |
3.5 |
Операции над отношениями .......................................................................... |
38 |
3.6 |
Контрольные вопросы и задания ................................................................... |
40 |
|
3 |
|
ЛЕКЦИЯ 4 СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ ........................................ |
41 |
|
4.1 |
Основные свойства бинарных отношений ................................................... |
41 |
4.2 |
Классы бинарных отношений ........................................................................ |
43 |
4.3 |
Контрольные вопросы и задания ................................................................... |
50 |
ЛЕКЦИЯ 5 ФУНКЦИОНАЛЬНЫЕ ОТНОШЕНИЯ. ЭЛЕМЕНТЫ |
||
РЕЛЯЦИОННОЙ АЛГЕБРЫ ................................................................................... |
50 |
|
5.1 |
Функциональные отношения ......................................................................... |
50 |
5.2 |
Элементы реляционной алгебры ................................................................... |
54 |
5.3 |
Контрольные вопросы и задания ................................................................... |
61 |
ЛЕКЦИЯ 6. ДВУЗНАЧНАЯ ЛОГИКА. БУЛЕВЫ ФУНКЦИИ. ОСНОВНЫЕ |
||
ПОНЯТИЯ.................................................................................................................. |
62 |
|
6.1 |
Двузначная логика........................................................................................... |
62 |
6.2 |
Булевы переменные и функции ..................................................................... |
62 |
6.3 |
Область определения и область значений булевой функции ..................... |
64 |
6.4 |
Способы задания булевых функций.............................................................. |
65 |
6.5 |
Реализация булевых функций формулами ................................................... |
69 |
6.6 |
Принцип двойственности ............................................................................... |
71 |
6.7 |
Булевы алгебры. Законы и тождества булевой алгебры ............................. |
73 |
6.8 |
Контрольные вопросы и задания ................................................................... |
77 |
ЛЕКЦИЯ 7. НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ ......................... |
78 |
|
7.1 |
Нормальные формы булевых функций, основные понятия ....................... |
78 |
7.3 |
Теоремы о разложениях булевой функции по переменным....................... |
82 |
7.4 |
Переход от табличного представления функции к алгебраическому |
|
представлению функции....................................................................................... |
84 |
|
7.5 |
Правила преобразования произвольной формулы алгебры логики в |
|
нормальную форму с использованием законов булевой алгебры ................... |
86 |
|
ЛЕКЦИЯ 8. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ ...................................... |
87 |
8.1Основные понятия минимизации булевых функций. Критерии
минимизации.......................................................................................................... |
87 |
4
8.3Основные методы минимизации булевых функций. Метод
минимизирующих карт (диаграммы Карно-Вейча)........................................... |
91 |
|
8.4 |
Контрольные вопросы и задания ................................................................... |
97 |
ЛЕКЦИЯ 9. АЛГЕБРА ЖЕГАЛКИНА И ЛИНЕЙНЫЕ ФУНКЦИИ. |
||
ФУНКЦИОНАЛЬНАЯ ПОЛНОТА НАБОРОВ БУЛЕВЫХ ФУНКЦИЙ ........... |
97 |
|
9.1 |
Алгебра Жегалкина и линейные функции.................................................... |
97 |
9.2 |
Функциональная полнота булевых функций ............................................. |
101 |
9.3 |
Контрольные вопросы и задания ................................................................. |
108 |
ЛЕКЦИЯ 10. ЛОГИКА ВЫСКАЗЫВАНИЙ. АЛГЕБРА ВЫСКАЗЫВАНИЙ. 108
10.1 |
Высказывания (основные понятия) ........................................................... |
108 |
10.3 |
Алгебра логики и логика высказываний................................................... |
113 |
10.4 Интерпретация формул логики высказываний. Правильные рассуждения
............................................................................................................................... 114
10.5 |
Логическая эквивалентность и логическое следствие ............................ |
116 |
10.6 |
Контрольные вопросы и задания ............................................................... |
117 |
ЛЕКЦИЯ 11. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ ............................................. |
118 |
|
11.1 |
Основные понятия исчисления высказываний ........................................ |
118 |
11.2 |
Аксиомы и полнота исчисления логики высказываний.......................... |
118 |
11.3 |
Выводимость в исчислении высказываний .............................................. |
119 |
11.4 |
Непротиворечивость, независимость ........................................................ |
121 |
11.5 |
Различные аксиоматизации исчисления высказываний ......................... |
122 |
11.6 |
Некоторые приемы доказательств в исчислении высказываний ........... |
123 |
11.7 |
Контрольные вопросы и задания ............................................................... |
124 |
ЛЕКЦИЯ 12. ЛОГИКА ПРЕДИКАТОВ (ЛОГИКА ПЕРВОГО ПОРЯДКА).
ПРЕДИКАТЫ. АЛГЕБРА ПРЕДИКАТОВ........................................................... |
124 |
|
12.1 |
Основные понятия логики предикатов ..................................................... |
124 |
12.2 |
Операции логики предикатов. Кванторные операции ............................ |
127 |
12.3 |
Формулы и их интерпретация в логике предикатов................................ |
128 |
12.4 |
Законы и тождества логики предикатов ................................................... |
131 |
|
5 |
|
12.5 |
Предваренные нормальные формы ........................................................... |
132 |
12.6 |
Выводимость в логике предикатов............................................................ |
133 |
12.7 |
Контрольные вопросы и задания ............................................................... |
134 |
ЛЕКЦИЯ 13. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ..................................................... |
134 |
|
13.1 |
Основные понятия исчисления предикатов ............................................. |
134 |
13.2 |
Аксиомы исчисления предикатов.............................................................. |
135 |
13.3 |
Правила вывода в исчислении предикатов............................................... |
135 |
13.4 |
Контрольные вопросы и задания ............................................................... |
136 |
ЛЕКЦИЯ 14. ОБЩИЕ ОПРЕДЕЛЕНИЯ КОМБИНАТОРИКИ. ОСНОВНЫЕ |
||
ПРАВИЛА КОМБИНАТОРИКИ. МОДЕЛИ ТИПОВЫХ КОМБИНАТОРНЫХ |
||
КОНФИГУРАЦИЙ.................................................................................................. |
136 |
|
14.1 |
Общие определения комбинаторики. Понятие r -выборки. Общие задачи |
|
комбинаторики .................................................................................................... |
136 |
|
14.2 |
Основные правила комбинаторики ........................................................... |
138 |
14.3 |
Модели комбинаторных конфигураций ................................................... |
139 |
14.4 |
Контрольные вопросы и задания ............................................................... |
144 |
ЛЕКЦИЯ 15. ПРИНЦИП ВКЛЮЧЕНИЯ И ИСКЛЮЧЕНИЯ............................ |
145 |
|
15.1 |
Теорема и формула включений и исключений ........................................ |
145 |
15.2 |
Решето Эратосфена ..................................................................................... |
146 |
15.3 |
Частный случай теоремы о включениях и исключениях ........................ |
146 |
15.3 |
Контрольные вопросы и задания ............................................................... |
147 |
ЛЕКЦИЯ 16. ЗАДАЧИ О РАСПРЕДЕЛЕНИИ ПРЕДМЕТОВ ПО УРНАМ |
||
(УРНОВЫЕ СХЕМЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ).................... |
147 |
|
16.1 |
Задачи о размещении предметов ............................................................... |
147 |
16.3 |
Распределение n одинаковых предметов по k урнам .............................. |
148 |
16.4 Распределение разных предметов без учета порядка предметов по урнам |
||
............................................................................................................................... |
|
148 |
16.5 |
Распределение разных предметов с учетом их порядка в урнах............ |
148 |
6
16.6 |
Распределение разных предметов между одинаковыми урнами при |
|
условии, что урны не пусты ............................................................................... |
149 |
|
16.7 |
Композиции.................................................................................................. |
155 |
16.8 |
Комбинаторика разбиений ......................................................................... |
155 |
16.9 |
Контрольные вопросы и задания ............................................................... |
156 |
ЛЕКЦИЯ 17. ПОДХОДЫ К ИЗУЧЕНИЮ КОМБИНАТОРНЫХ ОБЪЕКТОВ И
ЧИСЕЛ...................................................................................................................... |
156 |
|
17.1 |
Понятие продуктивной функции ............................................................... |
156 |
17.2 |
Рекуррентные соотношения в комбинаторике......................................... |
158 |
17.3 |
Контрольные вопросы и задания ............................................................... |
160 |
ЛЕКЦИЯ 18. ПРОИСХОЖДЕНИЕ ГРАФОВ. ОПРЕДЕЛЕНИЕ ГРАФОВ...... |
160 |
|
18.1 |
Разновидности графов. Неориентированный граф. Определения ......... |
160 |
18.2 |
Ориентированный граф. Определения...................................................... |
162 |
18.3 |
Основные термины для ориентированных и неориентированных графов |
|
............................................................................................................................... |
|
162 |
18.4 |
Способы задания графов ............................................................................ |
168 |
18.5 |
Контрольные вопросы и задания ............................................................... |
174 |
ЛЕКЦИЯ 19. ОПЕРАЦИИ НАД ГРАФАМИ. ИЗОМОРФИЗМ ГРАФОВ.
ПЛОСКИЕ И ПЛАНАРНЫЕ ГРАФЫ .................................................................. |
175 |
|
19.1 |
Операции над графами ............................................................................... |
175 |
19.2 |
Гомеоморфные графы ................................................................................. |
181 |
19.3 |
Плоские и планарные графы ...................................................................... |
181 |
9.4 Контрольные вопросы и задания ................................................................. |
188 |
ЛЕКЦИЯ 20. СВЯЗНОСТЬ ГРАФОВ. ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ
ГРАФЫ ..................................................................................................................... |
188 |
|
20.1 |
Связность графов, компонента связности. n-связный граф.................... |
188 |
20.2 |
Свойства связных графов ........................................................................... |
190 |
20.3 |
Компоненты сильной связности ориентированного графа..................... |
190 |
20.4 |
Алгоритм выделения компонент сильной связности .............................. |
191 |
|
7 |
|
20.5 |
Метрические характеристики связных графов ........................................ |
193 |
20.6 |
Эйлеровы графы .......................................................................................... |
197 |
20.7 |
Алгоритм нахождения эйлерова цикла (алгоритм Флери) ..................... |
199 |
20.8 |
Гамильтоновы графы .................................................................................. |
199 |
20.9 |
Алгоритм Робертса-Флореса (метод перебора Робертса-Флореса) |
|
нахождения гамильтоновых циклов в графе .................................................... |
200 |
20.10 Признаки существования гамильтоновых циклов, путей и контуров . 203
20. 11 Контрольные вопросы и задания ............................................................ |
204 |
|
ЛЕКЦИЯ 21 ДЕРЕВЬЯ ........................................................................................... |
204 |
|
21.1 |
Определение и свойства деревьев ............................................................. |
204 |
21.2 |
Свойства деревьев ....................................................................................... |
205 |
21.3 |
Перечисление графов.................................................................................. |
205 |
21.4 |
Перечисление деревьев............................................................................... |
207 |
21.5 |
Остовы графа ............................................................................................... |
208 |
21.6 |
Алгоритмы построения остовов графа ..................................................... |
209 |
21.7 |
Ориентированные и бинарные деревья. Определения ............................ |
212 |
21.8 |
Правила прохождения бинарных деревьев............................................... |
214 |
21.9 |
Эквивалентные бинарные деревья ............................................................ |
215 |
21.10 Контрольные вопросы и задания ............................................................. |
216 |
|
ЛЕКЦИЯ 22. ЦИКЛОМАТИКА ГРАФОВ. РАСКРАСКА ГРАФОВ................ |
216 |
|
22.1 |
Цикломатика графов ................................................................................... |
216 |
22.2 |
Раскраска графов ......................................................................................... |
222 |
22.3 |
Контрольные вопросы и задания ............................................................... |
229 |
ЛЕКЦИЯ 23. ТРАНСПОРТНЫЕ СЕТИ И ПОТОКИ. ИХ СВОЙСТВА ........... |
229 |
|
23.1 |
Кратчайшие расстояния и пути в графах.................................................. |
229 |
23.2 |
Алгоритм Дейкстры поиска кратчайших путей....................................... |
230 |
23.3 |
Алгоритмы поиска кратчайших путей между всеми парами вершин |
|
графа ..................................................................................................................... |
235 |
|
23.4 |
Транспортные сети и потоки...................................................................... |
237 |
|
8 |
|
УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ .................. |
248 |
Основная литература........................................................................................... |
248 |
Дополнительная литература............................................................................... |
249 |
ГЛОССАРИЙ ТЕРМИНОВ ДИСЦИПЛИНЫ...................................................... |
250 |
9
ЛЕКЦИЯ 1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ. ОСНОВНЫЕ ПОНЯТИЯ И
ОБОЗНАЧЕНИЯ ТЕОРИИ МНОЖЕСТВ
1.1 Интуитивное понятие множества
Понятие множества является одним из наиболее общих математических понятий и как любое другое исходное понятие математической теории оно не определяется точно. Поэтому вместо строгого определения понятия «множество» обычно принимается некоторое основное положение о множестве и его элементах, дается описательное определение, содержание и смысл которого раскрываются при изучении теории множеств. Рассматривая основное положение о множестве и его элементах, чаще всего пользуются определением, предложенным основателем теории множеств немецким математиком Георгом Кантором, который определил множество как «объединение в одно целое объектов, хорошо различимых нашей интуицией и мыслью».
Математическое понятие «множество» связано с абстракцией. Сущность этой абстракции множества заключается в том, что действительно существующие связи объединяемых объектов между собой и с другими объектами игнорируются, а вместо них объединяемым объектам приписываются новые связи друг с другом, выражающие их принадлежность множеству. При этом считается, что два объекта, ничем не отличающиеся друг от друга, являются одним и тем же объектом.
1.2 Элементы множества
Определение. Рассмотрим множество как совокупность объектов произвольной природы, которые удовлетворяют двум свойствам:
все объекты этой совокупности попарно различимы;
существует некий признак принадлежности объекта этой совокупности.
Определение. Объекты, которые образуют множество, называются
элементами (членами) этого множества.
Пример.
N0 – множество натуральных чисел с нулем;
N – множество натуральных чисел;
10