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