- •Едеральное агентство по образованию
- •Оглавление
- •Раздел 1. Элементы теории множеств 8
- •Раздел 2. Элементы комбинаторики 20
- •Раздел 3. Алгебра логики 36
- •Раздел 4. Синтез управляющих систем 62
- •Раздел 5. Теория графов 77
- •Введение
- •Раздел 1 элементы теории множеств
- •1.1. Множества и операции над ними
- •1.2. Алгебра множеств
- •1.3. Разбиение множества на подмножества
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Отображение множеств
- •1.6. Отношения
- •1.7. Свойства бинарных отношений
- •1.8. Алгебра подмножеств
- •1.9. Задания для самостоятельной работы
- •Раздел 2 элементы комбинаторики
- •2.1. Комбинаторика
- •2.2. Различные комбинаторные соотношения
- •2.3. Свойства биномиальных коэффициентов. Биномиальная теорема. Полиномиальная теорема
- •2.4. Принцип включения и исключения
- •2.5. Формула решета
- •2.6. Производящие функции
- •2.7. Производящие функции числа основных комбинаторных объектов
- •2.8. Задания для самостоятельной работы
- •Раздел 3 алгебра логики
- •3.1. Булевы функции
- •3.2. Формулы
- •3.3. Сопоставление формулам над множеством функций
- •3.4. Свойства элементарных функций
- •3.5. Разложение булевых функций
- •3.6. Совершенная д. Н. Ф., совершенная к. Н. Ф.
- •3.7. Полные системы
- •3.8. Примеры полных систем
- •3.9. Полиномы Жегалкина
- •3.10. Единственность представления булевых функций полиномами Жегалкина
- •3.11. Методы построения полиномов
- •I. Метод построения с помощью таблицы.
- •II. Метод неопределенных коэффициентов.
- •III. Метод суперпозиции.
- •3.12. Замыкание. Свойства операции замыкания. Замкнутые классы
- •3.13. Классы и их свойства
- •3.14. Линейные функции и их свойства
- •3.15. Принцип двойственности
- •3.16. Самодвойственные функции, их свойства
- •3.17. Лемма о несамодвойственной функции
- •3.18. Монотонные функции, их свойства
- •3.19. Лемма о немонотонной функции
- •3.20. Теорема о полноте в р2
- •3.21. Предполные классы
- •3.22. Возможность выделить из любой полной системы полную подсистему, состоящую из не более чем 4-х функций
- •3.23. Представление о результатах Поста
- •3.24. Задания для самостоятельной работы
- •Раздел 4 синтез управляющих систем
- •4.1. Схемы из функциональных элементов
- •4.2. Определение схем из функциональных элементов
- •4.3. Основные понятия и определения
- •4.4. Возможность реализации любой функции алгебры логики сфэ
- •4.5. Простейшие методы синтеза
- •4.6. Метод Шеннона
- •4.7. Асимптотически наилучший метод (метод о.Б. Лупанова)
- •4.8. Задания для самостоятельной работы
- •Раздел 5 теория графов
- •5.1. Элементы теории графов
- •5.2. Основные понятия и определения
- •5.3. Способы задания графа
- •5.4. Некоторые соотношения в графе
- •5.5. Перечисление графов
- •5.6. Оценка числа неизоморфных графов с p вершинами
- •5.7. Оценка числа неизоморфных графов с q ребрами
- •5.8. Укладки графов. Укладка графов в трехмерном пространстве
- •5.9. Планарность. Формула Эйлера для плоских графов
- •5.10. Следствия из формулы Эйлера для плоских графов
- •5.11. Операция подразделения ребра
- •5.12. Гомеоморфность графов
- •5.13. Теорема Понтрягина-Куратовского
- •5.14. Деревья и их свойства
- •5.15. Деревья и операции над ними
- •5.16. Оценка числа неизоморфных корневых деревьев на p вершинах
- •5.17. Задания для самостоятельной работы
- •Литература Основная
- •Дополнительная
- •Михеева Елизавета Алексеевна
Едеральное агентство по образованию
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет математики и информационных технологий
Е. А. Михеева
ВВЕДЕНИЕ В ДИСКРЕТНУЮ МАТЕМАТИКУ
Учебное пособие
для студентов 1 курса факультета математики и информационных технологий
Часть первая
Ульяновск
2013
УДК 519.7 + 519.1(075.8)
ББК 22.174 я73
М69
Печатается по решению Ученого совета факультета математики и информационных технологий Ульяновского государственного университета (протокол № 7/13 от 15.10.2013)
Рецензенты:
профессор, доктор физико-математических наук С. П. Мищенко
доцент, кандидат физико-математических наук А. В. Жарков
Михеева, Е. А.
М69 Введение в дискретную математику : учебное пособие для студентов 1 курса факультета математики и информационных технологий / Е. А. Михеева. – Ч. 1. – Ульяновск : УлГУ, 2013. – 102 с.
Учебное пособие основано на конспектах лекций, читавшихся автором на механико-математическом факультете, факультете информационных и телекоммуникационных технологий, а ныне на факультете математики и информационных технологий начиная с 1989/90 учебного года. Пособие охватывает программу первого семестра курса «Дискретная математика», которая включает такие разделы, как элементы теории множеств, элементы комбинаторики, алгебра логики, синтез управляющих систем, теория графов. В конце каждого раздела приведены задачи и упражнения в виде тестов для лучшего усвоения и закрепления теоретического материала.
Учебное пособие предназначено для студентов 1 курса факультета математики и информационных технологий УлГУ. Оно может быть полезно для студентов вузов прикладных математических и инженерных специальностей, а также для преподавателей, ведущих курс дискретной математики.
УДК 519.7 + 519.1(075.8)
ББК 22.174 я73
© Михеева Е. А., 2013
©Ульяновский государственный университет, 2013
Оглавление
Введение 6
Раздел 1. Элементы теории множеств 8
1.1. Множества и операции над ними 8
1.2. Алгебра множеств 10
1.3. Разбиение множества на подмножества 11
1.4. Кортежи и декартово произведение множеств 12
1.5. Отображение множеств 13
1.6. Отношения 14
1.7. Свойства бинарных отношений 14
1.8. Алгебра подмножеств 15
1.9. Задания для самостоятельной работы 15
Раздел 2. Элементы комбинаторики 20
2.1. Комбинаторика 20
2.2. Различные комбинаторные соотношения 20
2.3. Свойства биномиальных коэффициентов. Биномиальная теорема. Полиномиальная теорема 23
2.4. Принцип включения и исключения 27
2.5. Формула решета 28
2.6. Производящие функции 29
2.7. Производящие функции числа основных комбинаторных объектов 32
2.8. Задания для самостоятельной работы 34
Раздел 3. Алгебра логики 36
3.1. Булевы функции 36
3.2. Формулы 39
3.3. Сопоставление формулам над множеством В функций 40
3.4. Свойства элементарных функций 41
3.5. Разложение булевых функций 42
3.6. Совершенная д.н.ф., совершенная к.н.ф. 44
3.7. Полные системы 44
3.8. Примеры полных систем 46
3.9. Полиномы Жегалкина 46
3.10. Единственность представления булевых функций полиномами Жегалкина 47
3.11. Методы построения полиномов 48
3.12. Замыкание. Свойства операции замыкания. Замкнутые классы 50
3.13. Классы и их свойства 51
3.14. Линейные функции и их свойства 52
3.15. Принцип двойственности 53
3.16. Самодвойственные функции, их свойства 54
3.17. Лемма о несамодвойственной функции 55
3.18. Монотонные функции, их свойства 56
3.19. Лемма о немонотонной функции 57
3.20. Теорема о полноте в 57
3.21. Предполные классы 59
3.22. Возможность выделить из любой полной системы полную подсистему, состоящую из не более чем 4-х функций 59
3.23. Представление о результатах Поста 60
3.24. Задания для самостоятельной работы 61