Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский
Читать онлайн книгу.
множеств называется множество вида
где Аi* – это либо Аi, либо Аic. Заметим также, что:
1) имеется точно 2n таких фундаментальных произведений;
2) любые два таких фундаментальных произведения не пересекаются;
3) универсальное множество является объединением всех таких фундаментальных произведений.
Рассмотрим пример из трех множеств А, В и С и дадим геометрическую интерпретацию их фундаментальных произведений (рис. 1.7):
А = {1, 2, 3, 6, 7},
B = {3, 4, 5, 6},
C = {5, 6, 7, 8}.
Имеется ровно восемь фундаментальных произведений из трех множеств:
P0 = Ac ∩ Bc ∩ Cc = {9}
P1 = Ac ∩ Bc ∩ C = {8}
P2 = Ac ∩ B ∩ Cc = {4}
P3 = Ac ∩ B ∩ C = {5}
P4 = A ∩ Bc ∩ Cc = {1, 2}
P5 = A ∩ Bc ∩ C = {7}
P6 = A ∩ B ∩ Cc = {3}
P7 = A ∩ B ∩ C = {6}
Рис. 1.7
1.7. Классы множеств, степенные множества и разбиения
Для данного множества S можно рассматривать множество всех его подмножеств. При этом придется рассматривать множество, элементами которого будут также множества, т. е. множество множеств. Чтобы избегать путаницы, часто бывает более удобно говорить о классе множеств или о семействе множеств. Если необходимо рассмотреть множества из данного класса, то можно говорить о подклассе или подсемействе. Например, рассмотрим множество S = {a, b, c, d}. Пусть А класс подмножеств S из трех элементов. Тогда
А = [{a, b, c}, {a, b, d}, {a, c, d}, {d, c, d}].
Элементами класса А являются множества {a, b, c}, {a, b, d}, {a, c, d} и {b, c, d}].
Пусть теперь В класс подмножеств S, который содержит элемент а и два других элемента из S. Тогда
В = {{a, b, c}, {a, b, d}, {a, c, d}]. Элементами В являются множества {a, b, c}, {a, b, d} и {a, c, d}]. Поэтому В является подклассом класса А.
Для данного множества S можно говорить о классе всех подмножеств S. Этот класс называют степенным множествомS и обозначают 2S. Если n(S) – число элементов множества S, то число элементов степенного множества n(2S) представляет собой степень 2 и равно n(2S) = 2 n(S). Например, если S = {a, b, c}, то степенное множество
2S = [Ø,{a}, {b}, {c}, {a, b},{a, c}, {b, c}, S].
Заметим, что пустое множество Ø принадлежит к 2S, так как пустое множество является подмножеством S и само S принадлежит 2S, поэтому число элементов n(2S) = 23 = 8.
Рассмотрим теперь еще одно важное понятие, которое называется разбиением множества S. Разбиением множества S называется семейство {Аi} непустых подмножеств S, для которых:
1) каждый элемент х из S принадлежит к одному из подмножеств Аi;
2) подмножества из {Аi} взаимно не пересекаются, т. е. если
Аi≠ Аj, тогда Аi ∩ Аj = Ø.
Подмножества в разбиении иногда называют клетками или блоками. На рис. 1.8 представлена диаграмма Венна, изображающая разбиение прямоугольного множества точек S на пять клеток А1, А2, А3, А4,