Свойства операций над множествами

Теорема 1. Для произвольных множеств А, В, С справедливы следующие равенства:

1. АÇB=ВÇА 2. ( АÇB)ÇС= АÇ(BÇС) 3. ( АÇB)ÈС=(АÈС)Ç(ВÈС) 4. АÇ(АÈВ)=А Свойства операций над множествами - student2.ru Свойства операций над множествами - student2.ru Свойства операций над множествами - student2.ru 5. Свойства операций над множествами - student2.ru 6. АÇU=A 7. АÇÆ=Æ Свойства операций над множествами - student2.ru 8. АÇ А=Æ 9. АÇА=А Свойства операций над множествами - student2.ru 10. Свойства операций над множествами - student2.ru =А 11. А\В=АÇВ   1'. АÈB=ВÈА 2'. ( АÈB)ÈС= АÈ(BÈС) 3'.(АÈB)ÇС=(АÇС)È (ВÇС) 4'. АÈ (АÇВ)=А 5'. Свойства операций над множествами - student2.ru 6'. АÈU= U 7'. АÈÆ= А Свойства операций над множествами - student2.ru 8'. АÈ А= U 9'. АÈА=А   - свойство коммутативности - свойство ассоциативности - свойство дистрибутивности - законы поглощения   Свойства операций над множествами - student2.ru - законы де Моргана - законы пустого и универсального множеств   - свойство идемпотентности - свойство инволюции - свойство исключения разности

Доказательство. Свойства 1, 1', 2, 2', 4, 4', 6-8, 6'-8',10 доказываются на основании определения равенства множеств и операций над множествами. Остальные равенства доказываются методом встречных включений.

Докажем, например, свойство 3 методом встречных включений:

( АÇB) ÈС=(АÈС)Ç(ВÈС)

Свойства операций над множествами - student2.ru Свойства операций над множествами - student2.ru X Y

Докажем, что X = Y.

I. Докажем, что X Í Y. Пусть xÎX => xÎАÇB или xÎC => xÎА и xÎB или xÎC => возможны два случая:

1. xÎА и xÎB;

2. xÎC.

1. Пусть xÎА и xÎB => xÎАÈС и xÎВÈС => xÎ(АÈС)Ç(ВÈС)=Y, т.е. xÎY.

2. Пусть xÎC => xÎАÈС и xÎВÈС => xÎ(АÈС)Ç(ВÈС)=Y, т.е. xÎY.

Из 1-2 => X Í Y.

II. Докажем, что Y ÍX .

Пусть yÎY=>yÎАÈС и yÎBÈC=>(yÎA или yÎC) и (yÎB или yÎC).

Возможны четыре случая:

1. yÎA и yÎB.

2. yÎA и yÎC.

3. yÎC и yÎB.

4. yÎC.

1. Пусть yÎA и yÎB=>yÎАÇB=>yÎ( АÇB)ÈС=X, т.е. yÎX.

2. Пусть yÎA и yÎC=>yÎ( АÇB)ÈС=X, т.е. yÎ X.

3. Пусть yÎC и yÎB => yÎ( АÇB)ÈС=X, т.е. yÎX.

4. Пусть yÎC => yÎX.

Из 1-4 => YÍX.

Из I-II => X = Y. Теорема доказана.

Замечание 1. Операции пересечения и объединения можно сформулировать в общем виде для конечного и бесконечного числа множеств.

Пусть A1, A2, …, An - множества. Тогда А1ÇА2Ç…ÇАn - множество всех элементов, принадлежащих каждому из множеств А1, …, An ; A1È…ÈAn - множество всех элементов, принадлежащих хотя бы одному из множеств А1, …, An .

Пусть iÎI, I - некоторое множество индексов (конечное или бесконечное),

{Bi | iÎI} - совокупность множеств. Тогда дистрибутивные законы и законы де Моргана можно сформулировать в общем виде:

Свойства операций над множествами - student2.ru AÇ(ÈBi)=È(AÇBi)

iÎI iÎI - обобщенные дистрибутивные законы.

AÈ(Ç Bi)=Ç(AÈ Bi)

iÎI iÎI

Свойства операций над множествами - student2.ru Свойства операций над множествами - student2.ru Свойства операций над множествами - student2.ru Свойства операций над множествами - student2.ru Ç Bi=ÈBi

iÎI iÎI

Свойства операций над множествами - student2.ru - обобщенные законы де Моргана.

Свойства операций над множествами - student2.ru ÈBi=Ç Bi

iÎI iÎI

Замечание 2. Множество называется конечным, если оно состоит из конечного числа элементов. В бесконечном случае различают счетные множества (например, ℤ) и множества мощности континуум (например, ℝ ).

Если конечное множество M состоит из n элементов, то пишут |M|=n, т.е. |M| -мощность множества M.

Таким образом, мощность конечного множества – это число элементов данного множества.

Пусть M – множество. Обозначим через P(M) - совокупность всех подмножеств множества M.

Утверждение 1. Если |M|=n, то |P(M)|=2n.

Например, если А={1,2}, то |A|=2 и |P(A)|=4.

Замечание 3. На множестве P(U) (совокупность всех рассматриваемых множеств) нами определены операции È, Ç,` , \, причем всякое множество можно представить в виде множества, содержащего лишь две операции:

1) Ç и ` или

2) È и `.

Системы операций 1) и 2) называются минимальными системами операций.

Наши рекомендации