lekcii_dm

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

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

RusakovAM.ru

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

Москва 2014

Оглавление
Введение.........................................................................................................	6
Глава 1. Теория множеств............................................................................	6
1.01. Понятие множества. Операции над множествами. ......................	6
1.02. Свойства операций сложения и пересечения множеств..............	9
1.03. Принцип двойственности в теории множеств............................	11
1.04. Отображения множеств.................................................................	11
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. Планарные графы...........................................................................	50
2.03. Локальные степени графа. Части и подграфы............................	51
2.04. Бинарные отношения в теории графов........................................	52
2.05. Матрицы смежности и инцидентности........................................	53
2.06. Маршруты, цепи и простые цепи.................................................	56
2.07. Транспортные сети.........................................................................	58
2.08. Связность. Компоненты связности..............................................	59
2.09. Матрицы достижимости и связности...........................................	61
2.10. Расстояние и протяжённость в графе...........................................	67
2.11. Деревья............................................................................................	69
2.12. Помеченные графы. Перечисление помеченных деревьев. ......	73
2.13. Задача поиска маршрутов в графе................................................	76
2.14. Поиск оптимального пути (маршрута)........................................	77
2.15. Минимальные пути, маршруты в нагруженных графах............	80

2

2.16. Специальные пути в орграфах (маршруты в графах). ...............	84
2.17. Эйлеровы цепи и цепи...................................................................	87
2.18. Гамильтовы циклы.........................................................................	89
2.19. Примеры задач и упражнений......................................................	91
2.20. Задачи для самостоятельного решения. ......................................	95
Глава 3. Основы теории формальных грамматик..................................	101
3.01. Основные определения формальных грамматик......................	101
3.02. Основные операции формальных грамматик...........................	104
3.03. Определение и способы описания формальных грамматик....	109
3.04. Классификация формальных языков по Хомскому.................	115
Глава 4. Теория автоматов.......................................................................	117
4.01. Основные понятия теории автоматов........................................	117
4.02. Способы задания автоматов. Таблица переходов. ...................	121
4.03. Способы задания автоматов. Граф автомата.............................	123
4.04. Способы задания автоматов. Матрица переходов и выходов. 124
4.05. Машины Тьюринга и конечные автоматы................................	125
4.06. Машины Тьюринга с двумя выходами......................................	130
4.07. Машины Тьюринга и линейно-ограниченные автоматы.........	134
4.08. Автоматы с магазинной памятью и бесконтекстные языки....	136
4.09. Бесконтекстные (контекстно-свободные) языки......................	140
4.10. Модель дискретного преобразователя Глушкова В. М...........	142
4.11. Понятие об абстрактном автомате и индуцируемом им
отображении. ...................................................................................................	144
4.12. Автоматные отображения и события.........................................	148
4.13. Представление событий в автоматах.........................................	153
4.14. Регулярные языки и конечные автоматы. .................................	154
4.15. Основной алгоритм синтеза конечных автоматов....................	156
4.16. Правила подчинения мест в регулярных выражениях.............	159

3

4.17. Правила построения основного алгоритма синтеза конечных
автоматов..........................................................................................................	161
4.18. Автомат Мили..............................................................................	166
4.19. Автомат Мура...............................................................................	168
Глава 5. Теория булевых функций..........................................................	169
5.01. Связь булевых функций и схем из функциональных элементов
и контактных схем...........................................................................................	169
5.02. Основные понятия булевых функций........................................	173
5.03. Законы двойственности...............................................................	180
5.04. Основные свойства булевых функций.......................................	185
Глава 6. Элементы теории доказательств...............................................	189
6.01. Естественная дедукция................................................................	189
6.02. Метод математической индукции..............................................	193
6.03. Доказательство неравенств методом математической индукции.
Неравенство Коши-Буняковского. ................................................................	195
6.04. Примеры задач и упражнений....................................................	198
6.05. Задачи для самостоятельного решения. ....................................	201
Глава 7. Элементы комбинаторики.........................................................	203
7.01. Основные понятия комбинаторики............................................	203
7.02. Декартово произведение множеств............................................	208
7.03. Примеры задач и упражнений....................................................	209
7.04. Задачи для самостоятельного решения. ....................................	212
Глава 8. Основная часть: практическая работа студентов....................	213
Практическое занятие №1. Разработка синтаксических анализаторов
для регулярных языков.......................................................................................	213
8.01. Общие указания к выполнению практической работы............	213
8.02. Цель работы..................................................................................	213
8.03. Постановка задачи .......................................................................	213
8.04. Последовательность выполнения...............................................	217

4

8.05. Методический пример.................................................................	218
8.06. Контрольная распечатка..............................................................	219
8.07. Замечания......................................................................................	221
8.08. Отчет по практической работе. ..................................................	224
8.09. Контрольные вопросы.................................................................	224
8.10. Варианты заданий........................................................................	226
Домашняя работа №1. По всей теории...................................................	230
Домашняя работа №2. Способы задания графов...................................	231
Глава 9. Дополнительная часть: практическая работа студентов........	276
Практическое занятие №1. Работа с регулярными выражениями на
основе PERL ........................................................................................................	276
9.01. Общие указания к выполнению практической работы............	276
9.02. Цель работы..................................................................................	277
9.03. Теоретические сведения..............................................................	277
9.04. Установка необходимого программного обеспечения............	282
9.05. Замечания......................................................................................	283
9.06. Методический пример.................................................................	285
9.07. Контрольная распечатка..............................................................	285
9.08. Отчет по практической работе. ..................................................	286
9.09. Контрольные вопросы.................................................................	286
9.10. Варианты заданий........................................................................	287
Глава 10. Дополнительные материалы...................................................	288
10.01. Биография Георга Кантора (основатель теории множеств)..	288
10.02. Город Калининград (Кёнигсберг). ...........................................	290
Глава 11. Список литературы..................................................................	291

5

Введение.

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

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

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

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

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

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

6.Комбинаторика.

Сегодня дискретная математика является важным звеном

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

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

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

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

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

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

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

Утверждение "элемент a принадлежит множеству A " символически

записывается так: a A	или	A a , a "элемент b не принадлежит
множеству A " записывается так: b A или A b.
Определение.
Если все элементы,	из которых состоит A , входят и в B , причем

случай A B не исключается, то A называется подмножеством B . Записывается это так: A B .

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

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

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

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

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

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

7

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

Подмножества множества, отличные от него самого и от ,

называются собственными.

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

Рис. 1.1. C A B .

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

числа множеств, а именно:
если A — произвольное множество, то их сумма	A		— есть

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

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

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

Пересечением любого (конечного или бесконечного) числа множеств

A называется совокупность A элементов, принадлежащих каждому из

множеств A .

8

A B

Рис. 1.2. C A B .

Пример.

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

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

A B B A.	– коммутативность
A B B A.
(A B) C A (B C).		– ассоциативность
(A B) C A (B C).
(A B) C (A C) (B C).		– взаимная
(A B) C (A C) (B C).		дистрибутивность
Свойства 1. – 4. выполняются по определению.
Докажем свойство 5,	то есть что (A B) C (A C) (B C).
Пусть х (A B) C . Это означает, что х С и принадлежит по
крайней мере одному из множеств А или В. Но тогда х A C или			B C ,
то есть х множеству, записанному в правой части равенства 5.
Докажем обратное,	то есть	пусть х (A C) (B C).	Тогда

х A C или х B C х С, а также х А или х В, то есть х A B

9

х (A B) C , то есть х множеству, записанному в левой части равенства 5. Таким образом, равенство 5 доказано.

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

Разность множеств А и В, обозначаемая как С = А \ В, – это совокупность тех элементов из А, которые не содержатся в В.

A B

Рис. 1.3. С = А \ В.

Замечание.

1.При определении разности А \ В, вообще говоря, не предполагается, что

АВ.

2.Иногда вместо А \ В пишут А – В.

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

Симметрическая разность двух множеств А и В – это сумма разностей А \ В и В \ А, то есть

A B (A \ B) (B \ A).

A B

Рис. 1.4. С = А В.

Замечание.

Название “симметрическая разность” для операции A B не совсем

удачна. Операция A B	во	многом аналогична операции взятия суммы
A B . Действительно,	A B	означает, что связываются неисключающим

10