Введение......................................3
1. Основы теории множеств..........................................................4
1.1. Основные понятия и определения....................................4
1.2. Способы задания множеств..............................................5
1.3. Операции над множествами.............................................8
1.3.1. Объединение...............................................................8
1.3.2. Пересечение................................................................9
1.3.3. Разность.....................................................................10
1.3.4. Дополнение...............................................................12
1.3.5. Симметрическая разность.......................................12
1.3.6. Свойства операций над множествами....................13
1.4. Декартово произведение множеств
Отношения на множествах................................15
1.4.1. Определения.............................................................15
1.4.2. Свойства отношений и действия над ними...........17
1.5. Элементы общей алгебры...............................................20
1.5.1. Алгебры. Операции на множествах........................20
1.5.2. Свойства бинарных алгебраических операций.....22
1.5.3. Гомоморфизм и изоморфизм..................................24
1.6. Контрольные задания к разделу.....................................27
2. Элементы математической логики........................................29
2.1. Алгебра высказываний....................................................29
2.1.1. Логические операции..............................................29
2.1.2. Равносильность......................................................... 32
2.2. Булевы функции..............................................................34
2.2.1. Булевы функции и их свойства...............................34
2.2.2. Признаки полноты булевых функций....................40
2.2.3. Представление булевых функций дизъюнктивными нормальными формами..........44
2.3. Логика предикатов...........................................................50
2.3.1. Предикаты и операции квантирования..................50
2.3.2. Равносильные формулы логики предикатов.........54
2.4. Контрольные вопросы к разделу....................................56
3. Комбинаторный анализ...........................................................58
3.1. Предмет и задачи комбинаторного анализа..................58
3.2.Общие принципы подсчёта комбинаций.......................58
3.2.1. Правило сложения....................................................58
3.2.2. Правило произведения.............................................60
3.2.3. Принцип включения-исключения........................... 60
3.3. Типовые комбинации и способы их подсчета...............65
3.3 Л.Перестановки.............................................................65
3.3.2. Беспорядки.................................................................68
3.3.3. Размещения...............................................................70
3.3.4. Сочетания..................................................................73
3.4. Рекуррентные соотношения в комбинаторном анализе..... 80
3.4.1. Общие сведения о рекуррентном соотношении......... 80
3.4.2. Решение рекуррентных соотношений с помощью
характеристических уравнений............................85
3.4.3. Решение рекуррентных соотношений с помощью производящих функций...................93
3.5. Контрольные вопросы и задания к разделу...................99
4. Основы теории графов..........................................................105
4.1. Основные понятия и определения................................105
4.2. Основные операции над графами.................................117
4.3. Деревья.............................................................121
4.4. Алгоритмы анализа графов...........................................126
4.4.1. Поиск в глубину и в ширину.................................126
4.4.2. Эйлеровы циклы.....................................................131
4.4.3. Гамильтоновы пути...............................................133
4.4.4. Алгоритмы нахождения кратчайших путей в графе............135
4.5. Контрольные вопросы и задания к разделу.................140
Заключение.................................................147
Библиографический список.....................................148
