Тема Основные понятия теории множеств - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Тема Основные понятия теории множеств - страница №1/1



ДИСЦИПЛИНА: “ДИСКРЕТНАЯ МАТЕМАТИКА”.

Тема 1. Основные понятия теории множеств.

Содержание:

1.1. Основные понятия: множество, элемент множества, подмножество, универсальное множество, пустое множество.

1.2. Способы задания множества.

1.3. Основные операции над множествами и их свойствами и их свойства.

1.4. Декартово произведение множеств.




    1. Основные понятия: множество, элемент множества, подмножество, универсальное множество, пустое множество.

Определение. Множеством М называется объединение в единое целое определенных различимых однотипных объектов а, которые называются элементами множества. а  М

Замечание. Вообще говоря, понятие множества считается первичным (исходным) понятием, и, как таковое, не определяется. Приведённое выше определение следует, скорее, считать уточнением понятия множества.

Определение. Если все элементы множества А являются также элементами множества В, то говорят, что множество А включается (содержится) в множестве В.

А

А В


В

Определение. Если А  В, то множество А называется подмножеством множества В (также говорят, что В покрывает А). Если при этом А  В, то множество А называется собственным подмножеством множества В и обозначается А  В.

Замечание. Не следует считать равносильными отношения принадлежности и вхождения одного множества в другое . Можно привести следующий пример. Пусть А – множество всех студентов данной группы, а В – множество всех учебных групп данного института. Здесь , но , поскольку элементы этих множеств разнородны. Этот пример показывает также, что элементами множеств могут являться другие множества.

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

Множество, элементами которого являются другие множества, называется классом или семейством.

Множество, содержащее конечное число элементов, называется конечным. При подсчёте количества элементов учитываются только различные (неповторяющиеся) элементы. Множество, не содержащее элементов, называется пустым и обозначается символом .



    1. Способы задания множества.

Множество можно описать, указав какое-то свойство, присущее всем элементам этого множества.

Множество может быть задано перечислением (списком) своих элементов, порождающей процедурой или описанием характеристических свойств (предикатом), которым должны обладать его элементы. Причём в последнем случае необходимо формулировать описание характеристических свойств элементов множества достаточно корректно, для того, чтобы множество было определено вполне однозначно. Добавим, что многие числовые множества могут быть заданы всеми тремя указанными способами (например, множество чётных однозначных чисел).



Пример 1. Некоторые примеры множеств, заданных различными способами.

а) .

б) .

в) .



Парадокс Рассела. Задание множеств характеристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: . Если такое множество существует, то можно ответить на следующий вопрос: принадлежит ли оно само себе. С одной стороны, если , то . С другой стороны, если , то ! Это противоречие можно разрешить различными способами, в целом сводящимся к тому, что не является множеством.

Для трех множеств А, В, С справедливы следующие соотношения:



Связь между включением и равенством множеств устанавливается следующим соотношением:

Здесь знак  обозначает конъюнкцию (логическое “и”).


    1. Основные операции над множествами и их свойствами и их свойства.

Определение. Объединением множеств А и В называется множество С, элементы которого принадлежат хотя бы одному из множеств А и В.

Обозначается С = А  В.
А

В

Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера – Вэйна.


Определение. Пересечением множеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В.

Обозначение С = А  В.


А С В

Для множеств А, В и С справедливы следующие свойства:

А  А = А  А = А; A  B = B  A; A  B = B  A;

(A  B)  C = A  (B  C); (A  B)  C = A  (B  C);

A  (B  C) = (A  B)  (A  C); A  (B  C) = (A  B)  (A  C);

A  (A  B) = A; A  (A  B) = A;



 = А; A   = ;

Определение. Разностью множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В.

Обозначается: С = А \ В.

А В



Определение. Симметрической разностью множеств А и В называется множество С, элементы которого принадлежат в точности одному из множеств А или В.

Обозначается: А  В.

A B

А  В = (A \ B)  (B \ A)



Определение. СЕ называется дополнением множества А относительно множества Е, если А  Е и CЕ = Е \ A.

A E

Для множеств А, В и С справедливы следующие соотношения:

A \ B  A; A \ A = ; A \ (A \ B) = A  B;

A  B = B  A; A  B = (A  B) \ (A  B);

A \ (B  C) = (A \ B)  (A \ C); A \ (B  C) = (A \ B)  (A \ C);

(A  B) \ C = (A \ C)  (B \ C); (A  B) \ C = (A \ C)  (B \ C);

A \ (B \ C) = (A \ B)  (A  C); (A \ B) \ C = A \ (B  C);

(A  B)  C = A  (B  C); A  (B  C) = (A  B)  (A  C);

A  CEA = E; A  CEA = ; CEE = ; CE = E; CECEA = A;

CE(A  B) = CEA  CEB; CE(A  B) = CEA  CEB;

Пример 2. Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграммы Эйлера - Вэйна.

Решение:


Из записанных выше соотношений видно, что = A \ В

Что и требовалось доказать.

Для иллюстрации полученного результата построим диаграммы Эйлера – Вэйна:

А В А В
AB


Пример 3. Исходя из определения равенства множеств и операций над множествами, доказать тождество: A \ (B  C) = (A \ B)  (A \ C)

Решение:


Если некоторый элемент х  А \ (В  С), то это означает, что этот элемент принадлежит множеству А, но не принадлежит множествам В и С.

Множество А \ В представляет собой множество элементов множества А, не принадлежащих множеству В.

Множество А \ С представляет собой множество элементов множества А, не принадлежащих множеству С.

Множество (A \ B)  (A \ C) представляет собой множество элементов, которые принадлежат множеству А, но не принадлежат ни множеству В, ни множеству С.

Таким образом, тождество можно считать доказанным.


    1. Декартово произведение множеств.

Вектором (кортежем) в линейной алгебре и дискретной математике называют упорядоченный набор элементов. Это не есть определение вектора, поскольку целесообразнее это понятие считать основным.

Элементы, определяющие вектор, называются координатами или компонентами. Координаты нумеруются слева направо, а их число называется длиной или размерностью вектора. В отличие от элементов множества, координаты вектора могут совпадать. Координаты вектора заключаются в круглые скобки, например . Иногда скобки или запятые опускаются. Часто векторы длины 2 называются упорядоченными парами, длины 3 – тройками и т. д.



Определение. Два вектора равны, если они имеют равную длину и их соответствующие координаты равны. Иначе говоря, векторы и равны, если и .

Определение. Декартовым (прямым) произведением множеств А и В (обозначение ) называется множество всех упорядоченных пар , таких, что . В частности, если А=В, то обе координаты принадлежат множеству А, такое произведение обозначается А2. Аналогично, прямым произведением множеств называется множество всех векторов длины п, таких, что .

Пример 4. Множество - это множество всех упорядоченных пар действительных чисел, геометрической интерпретацией которого служит декартова координатная плоскость.

Координатное представление точек плоскости было впервые предложено Р. Декартом и исторически является первым примером прямого произведения. Поэтому часто прямое произведение множеств называют декартовым произведением.



Пример 5. Даны множества и . Тогда есть множество обозначений клеток шахматной доски.

Вообще конечное множество, элементами которого являются какие-либо символы (буквы, цифры, знаки препинания, знаки операций и т. д.) называется алфавитом. Любые элементы множества в этом случае являются словами длины п в алфавите А. Например, десятичное целое число – это слово в алфавите цифр.



Определение. Проекцией вектора на некоторую ось называется его компонента (координата) с соответствующим порядковым номером (обозначается прia). Например, проекция точки плоскости на 1-ю ось есть её абсцисса (первая координата).

Теорема 1.1. Мощность произведения конечных множеств равна произведению мощностей этих множеств: .

Следствие. .

Эта простая теорема и её следствие впоследствии широко используются в комбинаторике.



В заключение добавим, что Г. Кантор предложил использовать понятие “универсального множества” (универсум), как бы противоположного понятию пустого множества . По мысли Кантора, универсальное множество содержит все мыслимые множества, и при этом оно само содержится во множестве своих подмножеств в качестве элемента. В дальнейшем смысл и содержание понятия универсального множества будут раскрыты более подробно.