Подмножества. Отношение включения.

Множество Х является подмножеством множества Y, если любой элемент множества Х ∈ и множеству Y. Обозначается X⊆Y.

Если необходимо подчеркнуть, что Y содержит и другие элементы, кроме элементов из Х, то используют символ строгого включения ⊂: X⊂Y. Связь между символами ⊂ и ⊆ дается выражением:

X⊂Y ⇔ X⊆Y и X≠Y

Отметим некоторые свойства подмножества, вытекающие из определения:

  1. X⊆Х (рефлексивность);
  2. [X⊆Y и Y⊆Z] → X⊆Z (транзитивность);
  3. ∅ ⊆ M. Принято считать, что пустое множество является подмножеством любого множества.

Исходное множество А по отношению к его подмножествам называется полным множеством и обозначается I.

Любое подмножество Аi множества А называется собственным множеством А.

Множество, состоящие из всех подмножеств данного множества Х и пустого множества ∅, называется булеаном Х и обозначается β(Х). Мощность булеана |β(Х)|=2n.

Счетное множество — это такое множество А, все элементы которого могут быть занумерованы в последовательность (м.б. бесконечную) а1, а2, а3, ..., аn, ... так, чтобы при этом каждый элемент получил ишь один номер n и каждое натуральное число n было бы в качестве номера дано одному и лишь одному элементу нашего множества.

Множество, эквивалентное множеству натуральных чисел, называется счетным множеством.

Сравнение множеств

Множество Подмножества. Отношение включения. - student2.ru содержится во множестве Подмножества. Отношение включения. - student2.ru (множество Подмножества. Отношение включения. - student2.ru включает множество Подмножества. Отношение включения. - student2.ru ), если каждый элемент Подмножества. Отношение включения. - student2.ru есть элемент Подмножества. Отношение включения. - student2.ru :

Подмножества. Отношение включения. - student2.ru

В этом случае Подмножества. Отношение включения. - student2.ru называется подмножеством Подмножества. Отношение включения. - student2.ru , Подмножества. Отношение включения. - student2.ru — надмножеством Подмножества. Отношение включения. - student2.ru . Если Подмножества. Отношение включения. - student2.ru и Подмножества. Отношение включения. - student2.ru , то Подмножества. Отношение включения. - student2.ru называется собственным подмножеством Подмножества. Отношение включения. - student2.ru . Заметим, что Подмножества. Отношение включения. - student2.ru . По определению Подмножества. Отношение включения. - student2.ru .

Два множества называются равными, если они являются подмножествами друг друга:

Подмножества. Отношение включения. - student2.ru

Иногда для того, чтобы подчеркнуть, что множества могут быть равны, используется запись:

Подмножества. Отношение включения. - student2.ru

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

Бинарные операции

Ниже перечислены основные операции над множествами:

  • пересечение:

Подмножества. Отношение включения. - student2.ru

  • объединение:

Подмножества. Отношение включения. - student2.ru

Если множества Подмножества. Отношение включения. - student2.ru и Подмножества. Отношение включения. - student2.ru не пересекаются,то Подмножества. Отношение включения. - student2.ru . Их объединение обозначают также: Подмножества. Отношение включения. - student2.ru .

  • разность (дополнение):

Подмножества. Отношение включения. - student2.ru

  • симметрическая разность:

Подмножества. Отношение включения. - student2.ru

  • Декартово или прямое произведение:

Подмножества. Отношение включения. - student2.ru

Унарные операции

  • Абсолютное дополнение:

Подмножества. Отношение включения. - student2.ru

Операция дополнения подразумевает некоторый универсум (универсальное множество Подмножества. Отношение включения. - student2.ru , которое содержит Подмножества. Отношение включения. - student2.ru ):

Подмножества. Отношение включения. - student2.ru

Относительным же дополнением называется А\В (см.выше):

  • Мощность множества:

Подмножества. Отношение включения. - student2.ru

Результатом является кардинальное число (для конечных множеств — натуральное).

  • Множество всех подмножеств (булеан):

Подмножества. Отношение включения. - student2.ru

Обозначение происходит из того, что Подмножества. Отношение включения. - student2.ru в случае конечных множеств.

Приоритет выполнения операций

Сначала выполняются операции абсолютного дополнения, затем пересечения, затем объединения и разности, которые имеют одинаковый приоритет. Последовательность выполнения операций может быть изменена скобками.

Вопрос №8

Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

Подмножества. Отношение включения. - student2.ru

Рис. 2.15

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

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