Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский

множеств называется множество вида

      где А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,