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

Русаков Алексей Михайлович

RusakovAM.narod.ru

Лекции по дисциплине «Дискретная математика»

Москва 2011

Оглавление.

Введение. 6

Глава 1. Теория множеств. 7

1.01. Понятие множества. Операции над множествами. 7

1.02. Свойства операций сложения и пересечения множеств. 9

1.03. Принцип двойственности в теории множеств. 11

1.04. Отображения множеств. 12

1.05. Разбиение на классы. Отношения эквивалентности. 15

1.06. Упорядоченные множества. Изоморфизм теории множеств. 20

1.07. Счётные множества. Теорема Кантора. 24

1.08. Аксиома выбора. Теорема Цермело. 31

1.09. Примеры задач и упражнений. 33

1.10. Задачи для самостоятельного решения. 40

Глава 2. Теория графов. 47

2.01. Основные определения теории графов. 47

2.02. Планарные графы. 49

2.03. Локальные степени графа. Части и подграфы. 50

2.04. Бинарные отношения в теории графов. 51

2.05. Матрицы смежности и инцидентности. 52

2.06. Маршруты, цепи и простые цепи. 55

2.07. Связность, сильная связность и компоненты. 56

2.08. Расстояние и протяжённость в графе. 59

2.09. Деревья и леса. 62

2.10. Помеченные графы. Перечисление помеченных деревьев. 63

2.11. Задача о кратчайшем соединении. 66

2.12. Эйлеровы цепи, критерий Эйлеровости. 68

2.13. Гамильтовы циклы. 72

2.14. Примеры задач и упражнений. 74

2.15. Задачи для самостоятельного решения. 78

Глава 3. Основы теории формальных грамматик. 84

3.01. Основные определения формальных грамматик. 84

3.02. Основные операции формальных грамматик. 87

3.03. Определение и способы описания формальных грамматик. 92

3.04. Классификация формальных языков по Хомскому. 98

Глава 4. Теория автоматов. 100

4.01. Основные понятия теории автоматов. 100

4.02. Способы задания автоматов. Таблица переходов. 103

4.03. Способы задания автоматов. Граф автомата. 105

4.04. Способы задания автоматов. Матрица переходов и выходов. 107

4.05. Машины Тьюринга и конечные автоматы. 108

4.06. Машины Тьюринга с двумя выходами. 112

4.07. Машины Тьюринга и линейно-ограниченные автоматы. 116

4.08. Автоматы с магазинной памятью и бесконтекстные языки. 118

4.09. Бесконтекстные (контекстно-свободные) языки. 122

4.10. Модель дискретного преобразователя Глушкова В. М. 124

4.11. Понятие об абстрактном автомате и индуцируемом им отображении. 126

4.12. Автоматные отображения и события. 130

4.13. Представление событий в автоматах. 135

4.14. Регулярные языки и конечные автоматы. 137

4.15. Основной алгоритм синтеза конечных автоматов. 138

4.16. Правила подчинения мест в регулярных выражениях. 141

4.17. Правила построения основного алгоритма синтеза конечных автоматов. 143

4.18. Автомат Мили. 148

4.19. Автомат Мура. 150

Глава 5. Теория булевых функций. 151

5.01. Связь булевых функций и схем из функциональных элементов и контактных схем. 151

5.02. Основные понятия булевых функций. 155

5.03. Законы двойственности. 162

5.04. Основные свойства булевых функций. 167

Глава 6. Элементы теории доказательств. 170

6.01. Естественная дедукция. 171

6.02. Метод математической индукции. 175

6.03. Доказательство неравенств методом математической индукции. Неравенство Коши-Буняковского. 176

6.04. Примеры задач и упражнений. 179

6.05. Задачи для самостоятельного решения. 182

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

7.01. Основные понятия комбинаторики. 185

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

7.03. Множество степень. 189

7.04. Примеры задач и упражнений. 193

Глава 8. Практическое занятие №1. Разработка синтаксических анализаторов для регулярных языков. 195

8.01. Общие указания к выполнению практической работы. 195

8.02. Цель работы 196

8.03. Постановка задачи 196

8.04. Последовательность выполнения. 199

8.05. Методический пример. 200

8.06. Контрольная распечатка. 202

8.07. Замечания. 203

8.08. Отчет по практической работе. 206

8.09. Контрольные вопросы 206

8.10. Варианты заданий. 207

Глава 9. Практическое занятие №2. Работа с регулярными выражениями на основе PERL . 211

9.01. Общие указания к выполнению практической работы. 211

9.02. Цель работы 211

9.03. Теоретические сведения. 211

9.04. Установка необходимого программного обеспечения. 216

9.05. Замечания. 217

9.06. Методический пример. 219

9.07. Контрольная распечатка. 219

9.08. Отчет по практической работе. 220

9.09. Контрольные вопросы. 221

9.10. Варианты заданий. 221

Глава 10. Задания для домашней работы 222

Глава 11. Дополнительные материалы. 223

11.01. Биография Георга Кантора (основатель теории множеств). 223

11.02. Город Калининград (Кёнигсберг). 224

Список литературы. 226

Введение.

Дискретная математика — часть математики, которая зародилась в глубокой древности. В широком смысле этого слова к дискретной математике относятся как классические разделы математики: алгебра, теория чисел, теория множеств, математическая логика и т.д., так и новые разделы, которые возникли в середине прошлого столетия в связи с внедрением ЭВМ в практическую жизнь. В настоящее время понятие «дискретная математика» употребляется в узком смысле только для тех разделов современной математики, которые связаны с областью компьютерной науки. К ним относятся:

1. Теория множеств.

2. Теория графов.

3. Теория автоматов.

4. Теория формальных грамматик.

5. Теория булевых функций (переключательные функции).

6. Комбинаторика и другие разделы современной «компьютерной» математики.

Сегодня дискретная математика является важным звеном математического образования. Умение пользоваться «математическими аппаратами» дискретной математики является обязательным квалификационным требованием к специалистам в области информационных технологий.

1. Теория множеств.

1.Понятие множества. Операции над множест­вами.

В математике встречаются самые разнообразные множества. Можно говорить о множествах граней многогранника, точек, чисел и т.д.

Теория множеств, возникшая в конце XIX века, оказала и продолжает оказывать большое влияние на всю математику в целом.

По определению Георга Кантора (биография приведена в разделе дополнительные сведения), основоположника теории множеств, множество есть любое собрание определенных и различимых между собой объектов нашей интуиции или интеллекта, мыслимое нами как единое целое. Между отдельными объектами и множествами существует отношение принадлежности. Как правило, множества обозначают прописными буквами, а их элементы — малыми, которые перечисляются внутри фигурных скобок через запятую .

Определение.

Утверждение "элемент принадлежит множеству " символически записывается так: или , "элемент не принадлежит множеству " записывается так: или .

Определение.

Если все элементы, из которых состоит , входят и в , причем случай не исключается, то называется подмножеством .

Записывается это так: .

Например, целые числа образуют подмножество в множестве действительных чисел.

Иногда не известно заранее, содержит ли некое множество, например, множество действительных корней данного уравнения, хотя бы один элемент. Поэтому целесообразно ввести понятие пустого множества.

Определение.

Множество, не содержащее ни одного элемента, называется пустым множеством. Его обозначают символом .

Следствие из определения.

Любое множество содержит в качестве подмножества множество .

Определение.

Подмножества множества, отличные от него самого и от , называются собственными.

Определение.

Пусть и — множества. Тогда их суммой или объединением называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств или .

Рис. 1.1. .

Аналогично определяется сумма любого (конечного или бесконечного) числа множеств, а именно:

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

Определение.

Пересечением множеств и называется множество, состоящее из всех элементов, принадлежащих как , так и .

Пересечением любого (конечного или бесконечного) числа множеств называется совокупность элементов, принадлежащих каждому из множеств .

Рис. 1.2. .

Пример.

Пересечение множества всех четных чисел и множества чисел, делящихся на три, состоит из всех целых чисел, делящихся без остатка на шесть.

2.Свойства операций сложения и пересечения множеств.

. – коммутативность

.

. – ассоциативность

.

. – взаимная

. дистрибутивность