Множества. Комбинаторика. Отношения (стр. 1 )

Множества. Комбинаторика. Отношения

1.1. Множества

Понятие множества используется для описания совокупности предметов и объектов (по Г. Кантору – “многое, определяемое как единое”). При этом предполагается, что объекты данной совокупности можно отличить друг от друга и от предметов, не входящих в эту совокупность.

Отношение принадлежности, aÎА, читается “a принадлежит множеству А”. Запись – aÏА – означает, что a не является элементом множества А. Знак Î является стилизацией первой буквы e греческого слова edti – есть, быть.

Отношение включения множеств АÍ В означает, что каждый элемент множества А является элементом множества В. В этом случае говорят, что А – подмножество множества В. Употребляется также равносильная запись В ÊА. Множества А и В называются равными, если состоят из одних и тех же элементов, т. е. (А = В) Û (АÍ В и ВÍ А).

Множество А называется собственным подмножеством множества В, если АÍ В, А¹В. В этом случае пишем АÌ В. Предполагаем также, что все встречающиеся множества являются подмножествами некоторого универсального множества U.

Свойства отношения включения:

АÍ А (рефлексивность);

(AÍ B, BÍ A) Þ A = B (антисимметричность);

(AÍ B, BÍ C) Þ AÍ C (транзитивность).

Если множество В не является подмножеством множества А, то существует хÎ В такой, что xÏ А. Но если В – пустое множество Æ, то такого элемента нет. Поэтому считаем ÆÍ A для каждого множества А.

Упражнения

Докажите, что:

1) ƹ{Æ}, (Пояснение: посчитайте количество элементов в каждом множестве),

если АÍ Æ, то А = Æ;

2) {{1, 2},{2, 3}}¹{1, 2, 3}. (Аналогично первому заданию, учитывайте, что элементы множества могут быть сами по себе множества).

1.1.1. Способы описания множеств

Способ 1. Перечисление всех элементов множества. Например, запись M2n={…, 2-2, 2-1, 20, 21, 22 , …} означает, что множество M2n состоит из всех целых степеней числа 2.

Способ 2. Описание характеристического свойства, которым обладают элементы множества. Запись A={x: P(x)} читается так: А есть множество всех тех элементов, которые обладают свойством Р(х).

Например, M2n = {x: ($kÎZ) (x=2k)}.

Способ 3. Описание правил, по которым строятся элементы множества.

Пример.

1)  1ÎM2n. (Т. е. единица принадлежит данному множеству)

2)  aÎ M2n Þ 2aÎ M2n и a/2Î M2n; (т. е. если какое-то число принадлежит этому множеству, то и удвоенное и уменьшенное в два раза тоже принадлежит данному множеству).

3)  Других элементов в M2n нет.

Такое описание множества называется индуктивным.

Способ 4. Использование для описания множеств операций над множествами, к изучению которых перейдем.

1.1.2. Операции над множествами

Пересечением множеств А и В называется множество всех элементов, которые принадлежат А и В одновременно, т. e.

AÇB={x: xÎA и xÎB}.

Например: пусть даны два множества А={1, 2, 3, 4, 5} и B={3, 5, 7}. Тогда пересечением этих множеств служит множество AÇB={3, 5}.

Свойства пересечения:

1) АÇА = А (идемпотентность);

2) АÇВ = ВÇА (коммутативность);

3) (АÇВ)ÇС = АÇ(ВÇС) (ассоциативность);

4) (АÇВ)Í А, (АÇВ)Í B;

5) АÇÆ = Æ;

6) AÇB = A ó AÍ B.

Докажем свойство 2:

2) АÇВ = ВÇА. Нам надо доказать равенство двух множеств. По определению, нам необходимо доказать включение в обе стороны, т. е. АÇВÍВÇА и ВÇАÍАÇВ. Т. е. если какой-либо элемент принадлежит правой части, то он обязательно принадлежит и левой, и наоборот.

Возьмем произвольный элемент xÎ АÇВ, это означает, что x одновременно принадлежит и множеству А и множеству В, т. е. и множеству ВÇА. Наоборот доказывается также элементарными рассуждениями.

Объединением множеств А и В называется множество всех элементов, которые принадлежат А или В или А и В одновременно, т. е.

AÈB={x: xÎA или xÎB}.

Например: Пусть даны два множества А={1, 2, 3, 4, 5} и B={3, 5, 7}. Тогда объединением этих множеств будет множество AÈB={1, 2, 3, 4, 5, 7}.

Свойства объединения:

1) AÈA = А (идемпотентность);

2) AÈB = BÈA(коммутативность);

3) (AÈB)ÈC = AÈ(BÈC) (ассоциативность);

4) AÍ (AÈB), BÍ (AÈB) (принцип расширения);

5) AÈÆ = A;

6) AÈB=A ó BÍ A.

ТЕОРЕМА.

АÈ(BÇC) = (AÈB)Ç(AÈC),

AÇ(BÈC) = (АÇВ)È(АÇС).

Доказательство. 1) xÎAÈ(BÇC) Þ xÎA или xÎBÇC Þ xÎA или xÎB, xÎC. В обоих случаях по принципу расширения xÎAÈB и xÎAÈC Þ xÎ(AÈB)Ç(AÈC) Þ (AÈ(BÇC))Í ((AÈB)Ç(AÈC)). Аналогично доказывается включение ((AÈB)Ç(AÈC))Í (AÈ(BÇC)). Из этих двух включений и следует доказываемое равенство (дистрибутивность объединения множеств относительно пересечения слева).

Второе утверждение теоремы (дистрибутивность пересечения относительно объединения) доказывается аналогично. ■

Разностью множеств А и В называется множество всех элементов, которые принадлежат А, но не принадлежат В

A\B = {x: xÎA и xÎB}

(в иных обозначениях СAB – дополнение В до множества А).

Например: Пусть даны два множества А={1, 2, 3, 4, 5} и B={3, 5, 7}. Тогда A\B={1, 2, 4}, а В\A={7}.

Из этого примера видно, что разность, в отличие от пересечения и объединения, не обладает свойством коммутативности.

Свойства разности множеств:

А\ВÍ A;

(А\В)ÇВ = Æ;

(АÍ B) Þ ((A\B)ÈB = А);

А\Æ = А.

ТЕОРЕМА.

А\(ВÇС) = (А\В)È(А\С);

А\(ВÈС) = (А\В)Ç(А\С);

(АÈВ)\С = (A\C)È(B\C) (дистрибутивность разности относительно объединения справа);

AÇ(B\C) = (AÇB)\(AÇC) (дистрибутивность пересечения относительно разности справа). ■

Упражнения

Докажите, что:

А\(ВÈС) = (А\В)\С,

А\(В\С) = (А\В)È(АÇС),

(A\B)È(B\A) = (АÈВ)\(АÇB).

Дополнением множества А называется множество U\A = - А.

Свойства дополнения:

1) (-А)ÇА = Æ;

2) (-A)ÈA = U (правила исключенного третьего);

3) -(-A) = A (двойное отрицание);

4) -(АÇВ) = (-A)È(-B);

5) -(АÈВ) = (-A)Ç(-B) (законы двойственности де Моргана).

Действия над множествами иллюстрируются с помощью кругов Эйлера или диаграмм Венна (см. рис. 1-5). Универсальное множество принято изображать прямоугольником, а все произвольные множества, которые считаются подмножествами универсального – изображают кругами.

Симметрической разностью множеств А и В называется

А¸В = (А\В)È(В\А).

Её свойства:

1) А¸В = B¸A;

2) A¸(B¸C) = (А¸В)¸С;

3) А Ç (В¸С) = (А Ç В)¸(А Ç С);

4) A¸Æ= A;

5) A¸A = A;

6) A¸U= - A;

7) A¸B=C ó B¸C=A ó C¸A=B.

Например: пусть даны два множества А={1, 2, 3, 4, 5} и B={3, 5, 7}. Тогда симметрическая разность A¸B={1, 2, 4, 7}, т. е., говоря русским языком, симметрическая разность – это объединение без пересечения.

С помощью кругов Эйлера симметрическая разность изображается следующим образом.

Семейство всех подмножеств множества А называется булеаном множества А и обозначается Р(А).

Пример. А={a,b,c}, P(a)={Æ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.

Пример доказательства теоретико-множественного равенства А\(ВÈС) = (А\В)\С:

Сначала надо проверить это равенства с помощью кругов Эйлера (запомните, что круги Эйлера – это не доказательство, это только иллюстрация данного равенства. Т. е. если на кругах Эйлера равенство не выполняется, то это означает, что равенство не верно вообще, если же оно выполняется, то это не означает, что оно выполняется всегда, мы просто рассмотрели какой-то частный случай и теперь мы можем предположить, что равенство справедливо для любых множеств).

Изображаем правую и левую часть на кругах Эйлера:

Теперь мы проводим строгое доказательство. Так как нам надо доказать равенство двух множеств. Значит, нам надо доказать включение в обе стороны, т. е. правая часть содержится в левой и наоборот.

Берем любой элемент xÎ А\(ВÈС) Þ xÎA и xÏ ВÈС (по определению разности двух множеств) Þ xÎA и xÏ В и xÏ С Þ (расставим скобки следующим образом) (xÎA и xÏ В) и xÏ С Þ (xÎA\B) и xÏ С Þ xÎ(A\B)\С. Мы показали следующее включение А\(ВÈС)Í (A\B)\С. Теперь нам надо доказать обратное включение, что делается аналогично.