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

Чтение книги онлайн.

      Рис. 1.6

      1.6. Фундаментальное произведение множеств

      Операции над множествами позволяют образовывать из исходных множеств новые множества. При этом операция пересечения множеств применяется для различных практических задач, таких как классификация каких-либо объектов, анализ различного рода социологических опросов или исследований, анализ данных, из которых необходимо выбрать данные, характеризуемые заданными свойствами. Рассмотрим следующий пример. Пусть имеется список студентов группы, успешно решивших первую задачу контрольной работы (обозначим множество их фамилий как А). Пусть также имеется список всех тех, кто успешно решил вторую задачу (множество В), и всех тех, кто решил третью (множество С). Если теперь потребуются сведения о тех, кто успешно решил и первую и вторую задачи одновременно, то необходимо будет выбрать тех, кто входит одновременно и в первый и во второй списки. Для этого надо найти новое множество, являющееся пересечением исходных множеств А и В, т. е. найти множество А ∩ B. Однако это множество не содержит информации о том, решили или нет данные студенты третью задачу. Ясно, что для этого потребуется найти еще одно множество, являющееся пересечением всех трех множеств, т. е. множество А ∩ В ∩ С.

      Предположим теперь, что необходимо составить такой список, в котором присутствуют фамилии студентов, которые решили первую и вторую задачи, но не решили третьей. В этом случае надо найти множество А ∩ В ∩ Сс.

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

      Пусть имеется n различных множеств А1, А2,А3, …, Аn. Фундаментальным произведением множеств называется множество вида

      где А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 можно рассматривать множество всех его подмножеств. При этом придется рассматривать множество, элементами которого будут также множества, т. е. множество множеств. Чтобы избегать СКАЧАТЬ