Разбиение множества
Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств.
Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.
Пример. Продукция предприятия: — высший сорт, I, II, брак.
Рассмотрим некоторое множество M и систему множеств
М = {X1, X2, ..., Xn}
Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям:
- Любое множество X из M является подмножеством множества М
∀X∈M: X⊆M;
- Любые два множества X и Y из М являются непересекающимися
∀X∈М, ∀Y∈M: X≠Y → X∩Y=∅.
- Объединение всех множеств, входящих в разбиение, дает множество M
X1∪X2∪...∪ Xn=M.
Тождества алгебры множеств
С помощью операций объединения, пересечения и дополнения из множеств можно составлять различные алгебраические выражения.
Если алгебраические выражения V(X,Y,Z) и S(X,Y,Z) представляют собой одно и то же множество, то их можно приравнять друг другу, получая алгебраическое тождество вида V(X,Y,Z) = S(X,Y,Z)
- (X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогичное дистрибутивному закону (a+b)c=(a+c)(b+c) в обычной алгебре).
- (X∩Y)∪Z = (X∪Z)∩(Y∪Z)
- Если Y⊆X, то X∩Y=Y, X∪Y=X. Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит пересечение этих множеств, то есть общая множеств Х и Y совпадает с Y. В объединение множеств X и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества Х. Следовательно, X∪Y совпадает с X.
- Пусть в примере 3 Y=X. Тогда, учитывая, что X⊆X, то X∩Х=Х, X∪Х=X. (идемпотентность).
- Докажем тождество (X∪Y)¯=X¯∩Y¯. Предположим, что х∈(X∪Y)¯, то есть х∉X∪Y. Это значит, что х∉X и х∉Y, то есть и x&isinX¯ и x&isinY¯;. Следовательно, x∈X¯∩Y¯. Предположим теперь, что y∈X¯∩Y¯, то есть y∈X¯ и y∈Y¯. Это значит, что y∉X и y∉Y, то есть что y∉X∪Y. Следовательно, y∈(X∪Y)¯.
- Тождество (X∩Y)¯=X¯∪Y¯. Обычно тождества 5) и 6) называются тождествами де-Моргана.
- (A\B)∩C=(A∩C)\B=(A∩C)\(B∩C)
- A\B=A\(A∩B)
- A=(A∩B)∪(A\B)
Дополнение к занятию «операции над множествами»
Множество элементов, принадлежащих или A, или B, называют симметричной разностью или дизьюнктивной суммой.
S = A⊕B = (A\B)∪(B\A) = (A∩B¯)∪(A¯∪B) = (A∪B)∩(A∩B)¯
Для симметрической разности выполняются следующие законы:
- 1) A⊕B = B ⊕A — коммутативность,
- 2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,
- 3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,
- 4) A ⊕А = ∅
- 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.