КОНСПЕКТ ЛЕКЦИЙ
Дискретная математика
Кафедра информатики и методики преподавания математики
Комплект учебно-методических материалов к учебной дисциплине:
Для направления 080800 Прикладная информатика
Профиль Прикладная математика в образовании
Ведущий лектор:
Вахитов Р.Х, доцент, кандидат физико-математических наук, доцент
Воронеж
Тема: Элементы теории множеств
Основные вопросы, рассматриваемые на лекции:
1. Конечные множества.
2. Операции над множествами.
3. Диаграммы Эйлера – Венна.
4. Отношения между множествами.
5. Теорема о числе подмножеств конечного множества.
Краткое содержание лекционного материала
1. Конечные множества. Множество называется конечным, если оно пустое или может быть задано перечислением элементов в виде конечной последовательности: . Множество, заданное перечислением элементов, не зависит от того, повторяются элементы или нет, и не зависит от того, переставляются элементы или нет. Например, , .
Множество называется -множеством, если все элементы попарно различны. Число при этом называется числом элементов (или мощностью) множества и обозначается . Число элементов пустого множества равно нулю: . Если множество не конечное, то оно называется бесконечным. Понятие мощности множества обобщается и на бесконечные множества. Мощности бесконечных множеств могут быть различными, например, множества и имеют различные мощности.
2. Операции над множествами. Перечислим известные четыре бинарные операции и одну унарную операцию над множествами.
Объединением двух множеств и называется множество всех элементов, принадлежащих хотя бы одному из множеств и :
.
Пересечением двух множеств и называется множество всех элементов, принадлежащих одновременно каждому из множеств и :
.
Разностью множеств и называется множество всех элементов, принадлежащих множеству , но не принадлежащих множеству :
.
Симметрической разностью множеств и называется объединение двух разностей и :
.
Универсальное множество – это множество всех исследуемых объектов.
Дополнением множества называется разность универсального множества и множества :
.
3. Диаграммы Эйлера – Венна. Свойства отношений между множествами и операций над множествами можно наглядно проиллюстрировать с помощью диаграмм Венна (или кругов Эйлера). Каждое данное множество изображается в виде круга. Универсальное множество изображается в виде прямоугольника.
Результаты операций выделяются в виде частей круга и их соединений.
4. Отношения между множествами. Перечислим известные четыре бинарных отношения между множествами.
Два множества и называются равными , если
.
Множество называется подмножеством множества , если
.
Множество называется собственным подмножеством множества , если и .
Говорят, что множества и не пересекаются, если .
5. Теорема о числе подмножеств конечного множества. Существует множество, содержащее все подмножества данного множества . Оно называется множеством всех подмножеств множества и обозначается :
.
Примеры. Если , то . Если , то .
Теорема 1. Пусть множество конечно. Тогда .
Доказательство. Применим математическую индукцию по числу элементов множества . Заметим, что .
База индукции: . Тогда , и .
Шаг индукции: допустим, что , и для всех множеств с элементами утверждение теоремы 1 выполнено. Так как , можно выбрать некоторый элемент множества . Поскольку , то по индуктивному предположению множество имеет подмножеств, не содержащих элемента . Столько же у него подмножеств, содержащих элемент . Следовательно, . Теорема 1 доказана.