Элементы теории множеств. Множества и его элементы. Подмножества.

Определение:

Множество – это любая совокупность объектов, которые называются его элементами.

Если х- элемент множества М, то обозначают: х Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru М { х – принадлежит М}, если не принадлежит, то х ∉ М; Множество не содержащее элементов называется пустым и обозначается ∅

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

Ư. Множества, состоящие из одних и тех же элементов, называются равными и обозначаются А = В.

Если любой элемент множества В является элементом множества А, то множество В называется подмножеством множества А (частью множества А) и обозначается В ⊂ А; Отсюда следует, что любое множество является частью самого себя.

По определению пустое множество ∅ является подмножеством любого множества. Т.о. у любого множества А есть два подмножества:

А и ∅.

Они называются несобственными подмножествами множества А. Любое множество В множества А, которое не является несобственными подмножествами А, (т.е. они отличны от А и ∅) и называются собственными подмножествами подмножества А. Множество из одного элемента а обозначается {а}.

Пример: А = {1;2;3} тогда пустое множество ∅ и само множество А является несобственными подмножествами А.

Множества:{1},{2},{3},{1;2},{1;3},{2;3} называются собственными подмножествами множества А. Совокупность всех множеств А называется его булеаном и обозначается – 2А; В А, означает, что В Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru А, В ≠ А. В этом случае говорят, что В строго включено в А или В является собственным подмножеством А;

В случае В ⊆ А, В = А говорят, что В нестрогое включение в А, т.е. В является несобственным подмножеством А. Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru

Основные логические символы

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru хР(х) – квантор общности (означает “для любого х выполняется

Р (х)”.)

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru хР(х) – квантор существования (означает “существует х, для которого выполняется Р (х)”.)

Р ⇒ Q – импликация (“из Р следует Q ”)

⟺ - эквивалентность (“тогда и только тогда”)

Р ∧ Q – конъюнкция ( “Р и Q”)

Р ∨ Q – дизъюнкция (“Р или Q”)

Не Р или - отрицание Р

: = - символы присвоения (“положим”)

def – (“положим по определению”)

Используя эти символы можно записать:

1) (А = В) ⟺(( Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru х ∈ А ⇒ х ∈ В) ∧ ( Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru х ∈ В ⇒ х ∈ А)

2) (А ⊆ В) ⟺ ( Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru х/х ∈А ⇒ х ∈ В)

3) ( А = В) ⟺ ( В ⊂ А ∧ А⊂ В)

Задание множеств

Перечислением элементов: М: = { а1; а2; а3; …; аn }

или характеристическим свойством Р(х)

(предикатом): М: = { х | Р(х) }

Например:

1) В = { х ∈ N | х < 3} означает, что В= { 1; 2}

2) А ={ х ∈ N | х +1=5} означает, что А = {4}

3) В = { х ∈ N | х M5} или {5;10;15…}

т.е. { х | Р(х) }означает, что множество элементов х множества обладает свойством Р(х)

4) М = { х ∈ N | х ­3< 5}={1;2;3;4;5;6;7}

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

Рассматриваются следующие операции над множествами:

10. Объединение множеств А и В.

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru U

А ∪ В = { х/х ∈ А или х ∈ В} – т.е. состоит из элементов, принадлежащих хотя б одному из множеств А или В.

20. Пересечение множеств А и В.

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru A∩B = {x/x ∈ A и x ∈ B} – т.е. состоят из элементов, принадлежащих одновременно А и В.

3º. Разность множеств А и В.

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru U

A/B = {x/x ∈ A и x ∉ B} – т.е. состоит из элементов А, не принадлежащих В.

4º. Симметрическая разность А и В (или кольцевая сумма А и В)

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru А Ө B = {x/x ∈ A и x ∉ B} ∪ {x/x ∈ В и x ∉ А} или {А\В ∪ В\А}

5º. Дополнение А до универсума

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru = U\A = {x|x ∈ Uux и x ∉ А}

Произведение множеств

Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которой I элемент из множества А, II элемент – из множества В, т.е. А×В = {(а, в)/а Є А ̂в Є В}

Пример: А={2;5;7;9} и В ={2;4;7},

Тогда А×В = {(2,2) ; (2,4) ; (2,7) ; (5,2) ; (5,4) ; (5,7) ; (7,2) ; (7,4) ; (7,7) ; (9,2) ; (9,4 ); (9,7)}

А∩В={2,7}; А∪В={2,4,5,7,9}; А/В={5,9}; В/А={4}; А Ө В={4,5,9}

Элементы множества А×В называются точками; В паре (х, у) абсцисса – х и ордината – у точки, соответствующей этой паре.

Множество точек плоскости является прямым произведением вида R×R=R2, где R–множество действительных чисел.

R2 называется декартовым квадратом на R.

Элементы теории графов. Виды и способы задания графов

Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты называются вершинами и обозначаются точками, а связи – дугами. Такие системы образуют графы. Например: граф изображает сеть улиц а городе; сеть дорог, трубопроводов, блок – схемы программирования и многие другие модели.

Определение. Графом называется совокупность двух множеств – непустого множества V вершин и множество Е двухэлементных подмножеств множества V (множество ребер Е).

Обозначаются G(V,E) = <V;E>,V≠O

Множество двух элементных подмножеств определяет симметричное бинарное отношение на множестве Е = V×V, E = E-1; поэтому ребро можно считать не только как множество Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru , но и как пару Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru число вершин обозначают Р, число ребер – q; если дугами являются пары вершин Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru то дуга считается исходящей из v1 и заходящей в v2; граф G изображают диаграммой.

2

1 V = Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru - множество вершин

3 Е = Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru -

Множество дуг

Если имеется несколько дуг, исходящих из вершины v1 в вершину v2 , такие дуги называются кратными, граф называется кратным.

Если все элементы множества Е – упорядоченные пары, то граф G называется ориентированным (орграф), элементы V называются узлами, а множество Е дугами, т.е. если Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru (а, b) Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru E, (b, a) ∉ E

Если элементом Е может быть пара одинаковых (не различных) элементов V, то такой элемент называется петлей, а граф называется графом с петлями (псевдографом). Если Е содержит несколько одинаковых элементов, то эти элементы называются кратными ребрами, a G - мультиграфом.

Если Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru (а, b) Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru E /\ (b, a) Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru E, то G называется неориентированным (неографом). В этом случае дуга называется ребром и обозначается в виде отрезка, соединяющего вершины, а вершины а и b называются концами ребра Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru и информацию об этих дугах пишут: Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru = Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru

Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru или Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru Элементы теории множеств. Множества и его элементы. Подмножества. - student2.ru - ребро графа

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