Методическая разработка по дисциплине «Дискретная математика».

Приводятся основные понятия и утверждения из теории множеств и теории отношений, важнейшие операции над графами, иcпользуемые в различных технических приложениях, основные понятия алгебры логики, теории групп и полугрупп. Материал сопровождается поясняющими примерами. Содержит задачи, решение которых позволит глубже освоить учебный материал.
Разработка предназначена для студентов специальностей 220100 «Вычислительные машины, комплексы, системы и сети», 220200 и 071900 «Информационные системы в технике и технологиях»

1. МНОЖЕСТВА 5
1.1. Основные определения 5
1.2. Операции над множествами 6
13. Свойства операций 7
1.4. Уравнения на множествах 8
1.5. Произведение множеств (декартово произведение) 8
1.6. Задачи 9
1.6.1. Задачи на множествах 9
1.6.2. Уравнения на множествах 9
1.6.3. Тождества 10
2. ОТОБРАЖЕНИЯ И ОТНОШЕНИЯ 11
2.1. Способы описания бинарного отношения 11
2.2. Виды бинарных отношений 12
2.3. Эквивалентность 12
2.4. Отношение порядка 12
2.5. Замыкание отношений 14
2.6. Задачи 15
2.6.1. Свойства бинарных отношений. 15
2.6.2. Отношение эквивалентности 15
2.6.3. Отношение порядка 16
2.6.3. Транзитивное замыкание отображений 17
3. ГРАФЫ 18
Введение 18
3.1. Основные определения 18
3.2. Части графа 20
3.3. Неориентированные графы 20
3.4. Расширения модели 21
3.5. Оптимизационные задачи на графах 22
3.5.1. Поиск путей в графе 22
5.2. Деревья 27
5.3. Раскраска графа 32
3.5.4. Паросочетания 34
3.5.5. Паросочетания в двудольном графе 35
3.5.6. Поток в транспортной сети 36
3.5.7. Транспортная задача 39
5.7. Цикломатическое число графа 44
5.8. Планарные графы 45
5.9. Операции над графами. 46
5.10. Декомпозиция графов. 49
Табл. 3.11 50
Табл.3.14 52
Табл.3.15 52
5.11. Задачи 53
11.1. Сетевые графики 53
11.2. Выделение минимального остова 55
11.3. Задачи назначения 56
3.4. Потоки в сетях 57
3.5. Декомпозиция графа 58
4. ГРУППЫ И ПОЛУГРУППЫ 60
4.1. Введение 60
4.2. Группы 61
4.3. Изоморфизмы и гомоморфизмы 63
4.4. Симметрические группы 64
4.5. Полные множества и задача В. М. Глушкова 65
4.6 Задачи 66
5. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 67
5.1. Основные определения 67
5.2. Простейшие функции 68
5.3. Дизъюнктивные нормальные формы и теорема о разложении 69
5.3.1. Метод минимизации по картам Карно 72
5.3.2. Метод неопределенных коэффициентов 73
5.3.3. Метод Квайна Мак-Класки (метод покрытия) 76
5.4. Классы функций алгебры логики 78
5.5. Монотонные функции. 79
5.6. Самодвойственные функции 80
5.7. Линейные функции. 81
5.8. Функции, сохраняющие константу 82
5.9. Функциональная полнота. 83
5.10. Задачи 84
10.1. Представление функций 84
10.2. Разложение функций 84
10.3. Минимизация ФАЛ 85
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 87

1. Горбатов В.А. Фундаментальные основы дискретной математики. М: Высшая школа, 2000.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М: Энергия, 1988.
3. Яблонский С. С. Введение в дискретную математику. М: Наука, 2001 г.
4. Кук Д., Бейз Г. Компьютерная математика. М: Наука, 1990.
5. Берж К. Теория графов и ее применения. М.: ИЛ, 1962.
6. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.
7. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.
8. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. М: Наука, 1972
9. Мальцев А.И. Группы и другие алгебраические структуры.
// Математика, её содержание, методы и значение. Т. 3. М.: Изд. АН ССР, 1956.
10. Курош А.Г. Теория групп. М,: Наука, 1967.
11. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1974.