Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ДМ_Конспект

.pdf
Скачиваний:
193
Добавлен:
16.03.2016
Размер:
4.73 Mб
Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ

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

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине

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

для студентов всех форм обучения направления 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

Соседние файлы в предмете Дискретная математика