Материал: Дискретная математика. учебное пособие. Собенина О.В
Из определения равенства множеств вытекает, что порядок элементов в множестве несуществен. Так, например, множества {3, 4, 5, 6} и {4, 5, 6, 3} представляют собой одно и то же множество.
Если каждый элемент
множества X является элементом
множества Y, то говорят, что X
включено в Y и обозначают
:
В этом случае
говорят, что множество X является
подмножеством множества Y. В
частности X и Y могут совпадать,
поэтому
называется также отношением нестрогого
включения. Отметим некоторые свойства
подмножества, вытекающее из его
определения:
,
(
и
.
Если
и
,
то говорят, что X есть собственное
подмножество Y и обозначают
,
отношение между множествами в этом
случае называется отношением нестрогого
включения. Для отношения строгого
включения справедливо
(
и
.
Невключение
подмножества X в множество Y
обозначается
Пример. Пусть Y — множество студентов группы, а Х – множество отличников той же группы. Так как каждый отличник группы является в то же время студентом этой группы, то множество X является подмножеством множества Y.
Замечание. Не
следует смешивать отношение принадлежности
и отношение включения
.
Хотя
и
,
неверно, что
,
поскольку единственным элементом
множества
является {0}.
Пример. Справедливы следующие включения: NZ, ZQ, QR, RC.
Заметим, что если X является подмножеством Y и наоборот, то X и Y состоят из одних и тех же элементов, поэтому
и
Таким образом, чтобы доказать равенство двух множеств, надо установить два включения.
Пример. Покажем,
что множества М1={x
| sin x
= 1} и M2={x
| x =
,
}
совпадают.
Если x
М1,
то x является решением
уравнения sin x=1.
Но это значит, что x
можно представить в виде x=
и поэтому x
М2.
Таким образом,
.
Если x
М2,
т.е. x=
,
то sin x=1,
т.е.
.
Следовательно, М1=М2.
Для каждого
множества X существует множество,
элементами которого являются различные
подмножества множества X. Такое
множество называется семейством
множества или булеаном множества
X и обозначается P(X) Так как
включено в любое множество, то
.
Пример.
Пусть
.
Тогда
1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
Для получения новых множеств из уже существующих используют операции над множествами. Рассмотрим основные из них.
Объединением
множеств X и Y называется
множество
,
все элементы которого являются элементами
множества X или Y:
={x
x
или
}.
Пересечением
множеств X и Y называется
множество
,
элементы которого являются элементами
обоих множеств X и Y:
={x
| x
X
и x
Y}.
Очевидно, что выполняются включения
;
Разностью
множеств X и Y
называется множество
всех тех элементов X, которые не
принадлежат Y:
={x
x
и
}.
Дополнением
множества X называется множество
всех тех элементов x, которые не
принадлежат множеству X:
.
Симметрической разностью (или кольцевой суммой) множеств X и Y называется множество
.
Замечание.
.
Универсальное множество графически изображают в виде множества точек прямоугольника, отдельные области внутри этого прямоугольника соответствуют различным подмножествам универсального множества. Такое представление универсального множества и его подмножеств называется диаграммой Эйлера-Венна. На диаграмме Эйлера-Венна можно проиллюстрировать все основные операции над множествами (рис. 1.1-1.5).
Операции над множествами обладают определенными свойствами и удовлетворяют некоторым соотношениям. Рассмотрим следующие утверждения.
Утверждение 1.2.1. Для любых множеств X, Y, Z выполняются следующие тождества (основные свойства операций):
1. Коммутативность
операций
и
:
2. Ассоциативность операций и :
3. Законы дистрибутивности
4.
.
5.
.
6. Законы
комплиментарности:
7. Законы
идемпотентности:
8. Законы де Моргана:
.
(Август де Морган (1806–1871) – английский математик).
9. Закон двойного
дополнения
10. Законы поглощения
Докажем один из законной дистрибутивности:
Доказательство.
Чтобы доказать равенство двух множеств
А=В нужно доказать, что АВ
и ВА.
Докажем, что
Для доказательства этого включения
выберем произвольный элемент из множества
и покажем, что он принадлежит множеству
.
Итак, пусть
.
Тогда
и
.
Если
,
то
,
а значит,
.
Если
,
то
,
а значит,
.
Таким образом,
Теперь докажем,
что
Пусть
.
Если
,
то
и
,
отсюда следует, что
и
,
т.е.
.
Если
,
то
и
.
Отсюда следует, что
и
,
т.е.
.
Итак,
Таким образом, получили, что
и
,