Подмножества. Отношение включения.
Множество Х является подмножеством множества Y, если любой элемент множества Х ∈ и множеству Y. Обозначается X⊆Y.
Если необходимо подчеркнуть, что Y содержит и другие элементы, кроме элементов из Х, то используют символ строгого включения ⊂: X⊂Y. Связь между символами ⊂ и ⊆ дается выражением:
X⊂Y ⇔ X⊆Y и X≠Y
Отметим некоторые свойства подмножества, вытекающие из определения:
- X⊆Х (рефлексивность);
- [X⊆Y и Y⊆Z] → X⊆Z (транзитивность);
- ∅ ⊆ M. Принято считать, что пустое множество является подмножеством любого множества.
Исходное множество А по отношению к его подмножествам называется полным множеством и обозначается I.
Любое подмножество Аi множества А называется собственным множеством А.
Множество, состоящие из всех подмножеств данного множества Х и пустого множества ∅, называется булеаном Х и обозначается β(Х). Мощность булеана |β(Х)|=2n.
Счетное множество — это такое множество А, все элементы которого могут быть занумерованы в последовательность (м.б. бесконечную) а1, а2, а3, ..., аn, ... так, чтобы при этом каждый элемент получил ишь один номер n и каждое натуральное число n было бы в качестве номера дано одному и лишь одному элементу нашего множества.
Множество, эквивалентное множеству натуральных чисел, называется счетным множеством.
Сравнение множеств
Множество содержится во множестве (множество включает множество ), если каждый элемент есть элемент :
В этом случае называется подмножеством , — надмножеством . Если и , то называется собственным подмножеством . Заметим, что . По определению .
Два множества называются равными, если они являются подмножествами друг друга:
Иногда для того, чтобы подчеркнуть, что множества могут быть равны, используется запись:
Операции над множествами
Бинарные операции
Ниже перечислены основные операции над множествами:
- пересечение:
- объединение:
Если множества и не пересекаются,то . Их объединение обозначают также: .
- разность (дополнение):
- симметрическая разность:
- Декартово или прямое произведение:
Унарные операции
- Абсолютное дополнение:
Операция дополнения подразумевает некоторый универсум (универсальное множество , которое содержит ):
Относительным же дополнением называется А\В (см.выше):
- Мощность множества:
Результатом является кардинальное число (для конечных множеств — натуральное).
- Множество всех подмножеств (булеан):
Обозначение происходит из того, что в случае конечных множеств.
Приоритет выполнения операций
Сначала выполняются операции абсолютного дополнения, затем пересечения, затем объединения и разности, которые имеют одинаковый приоритет. Последовательность выполнения операций может быть изменена скобками.
Вопрос №8
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.
Граф
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).
Рис. 2.15
Петля это дуга, начальная и конечная вершина которой совпадают.
Простой граф граф без кратных ребер и петель.
Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.