Начальные понятия теории множеств

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

Множество и его элементы обозначаются следующим образом:

А = { a₁, a₂, a₃ } – множество, состоящее из трех элементов;

А = { a₁, a₂, … } – множество, состоящее из бесконечного числа элементов. Множество может состоять из элементов, которые сами являются множествами. Нужно различать элемент a и множество, состоящее из единственного элемента a.

Пример. Множество А = {1, 2} состоит из двух элементов 1, 2; но множество { А } состоит из одного элемента А.

Если элемент a принадлежит множеству А, это записывается следующим образом: a Î А. Если элемент a непринадлежит множеству А, то записывают так: a Ï А. Если какое-либо множество А включено в другое множество В, то используется запись А Ì В. Множество, содержащее конечное число элементов, называется конечным, если множество не содержит ни одного элемента, то оно называется пустым и обозначается Æ. Принято считать, что пустое множество является подмножеством любого множества: Æ Í А, где А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя.

Пример. 1. Множество корней уравнения sin x = 2 является пустым.

2.Пусть А₁ – множество простых чисел, А ₂ – множество целых чисел, a = 4. Тогда a Î А ₂, a Ï А ₁.

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

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

Примеры задания множеств. 1. Множество M цифр десятичного алфавита можно задать в виде: M   = {0, 1,..., 9} или M = { х │ х – целое,       0 £ х £ 9}, где справа от вертикальной черты указывают свойство элементов этого множества. Множество M чётных чисел можно записать в виде: M = { х│х – чётное число}.

2. Если R – множество точек числовой прямой, то R ⁿ – множество точек n -мерного арифметического пространства; в частности, R² – множество точек плоскости, R³ – множество точек пространства трех измерений.

Для каждого множества М существует множество, элементами которого являются подмножества множества М и только они. Такое множество будем называть семейством множества М или булеаном этого множества и обозначать В(М), а множество М будем называть универсальным (универсумом или пространством) и обозначать 1 или U. Множество М (универсальное) не должно быть ýже объединения рассматриваемых множеств, т. е. оно должно быть равно или содержать объединение рассматриваемых множеств.

Пример. Пусть множество А = {1, 2} состоит из двух элементов 1, 2. Тогда множество В(A) включает в себя пустое множество Æ, два одноэлементных множества {1} и {2} и само множество А = {1, 2}, т. е.

В(A) = {Æ, {1}, {2}, {1, 2}}. Мы видим, что множество В(A) состоит из четырех элементов (4 = 2²).

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

N – множество натуральных чисел (иногда его начинают с 1, иногда с 0; обычно это оговаривается);

Р – простые числа;

Z – множество целых чисел (положительные, отрицательные и 0);

R – множество действительных чисел.

Очевидное соотношение: N  Í Z   Í R.

Рассмотрим методы получения новых множеств из уже существующих на примере пространства или множества U, определив в нём 4 операции над множествами A и B: объединение, пересечение, разность, дополнение.

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

Объединением А и В называется множество А È В, все элементы которого являются элементами хотя бы одного из множеств А или В:

А È В = { x ç x Î А и / или  x Î В }.

Из определения следует, что А Í А È В и В Í А È В. Аналогично определяется объединение нескольких множеств.

Пример. 1. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А È В = {2, 4, 5, 6}.

2. Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А È В – множество чисел, которые делятся на 2 или на 3: А È В = {2, 3, 4, 6, 8, 9, 10, …}.

Пересечением множеств А и В называется множество А Ç В, все элементы которого являются элементами обоих множеств А и В: А Ç В = { x ç x Î А и x Î В }. Из определения следует, что А Ç В Í А, А Ç В Í В и А Ç В Í А È В. Аналогично определяется пересечение нескольких множеств.

Пример. 1. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А Ç В  = {4, 6}.

2. Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А Ç В  – множество чисел, которые делятся и на 2, и на 3: А È В = {6, 12, 18, …}.

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

Пример. Пусть А = {1, 2}, В = {2, 3}, C = {3, 4}. Тогда А Ç В Ç C = Æ.

Разностью (относительным дополнением) множества В до множества А называется множество А \ В, все элементы которого являются элементами множества А, но не являются элементами множества В:

А \ В = { x ç x Î А и x Ï В }.

Пример. 1.  А = {4, 5, 6}, В = {2, 4, 6}. А \ В  = {5}, В \ А = {2}.

2. А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда   А \ В – множество чисел, которые делятся на 2, но не делятся на 3, а В \ А – множество чисел, которые делятся на 3, но не делятся на 2: А \ В = {2, 4, 8, 10, 14, …}. В \ А = {3, 9, 15, 21, 27, …}.

Симметрической разностью множеств А и В  называется множество А + В: А + В = (А \ В) È (В \ А).

Пример. 1. А = {4, 5, 6}, В = {2, 4, 6}. А \ В  = {5}, В \ А = {2}, А + В = {2, 5}.

2. А = {2, 4, 6, …}, В  = {3, 6, 9, …}, А \ В = {2, 4, 8, 10, 14, …}.

В \ А = {3, 9, 15, 21, 27, …}, А + В = {2, 3, 4, 8, 9, …}.

Дополнением ` М множества М является множество

` М = { m_i │ m_i Ï M }.

Пример. Заданы множества А = {1, 2, 5, 6} и В = {2, 3, 4, 6} на универсальном множестве U = {1, 2, 3, 5, 6, 7}. Выполнить операции` А, `В.

Решение. В результате выполнения заданных операций получим следующие множества: ` А = {3, 7};` В = {1, 5, 7}.

Для конечных множеств существует понятие: мощность множества А – число его элементов. Обозначают мощность множества | А |.

Пример. А = {1, 2, 5, 6}, тогда мощность множества | А | = n(А) = 4; |Æ| = 0; |{Æ}| = 1.

Также справедливы следующие формулы: для любых множеств А и В Þ | А È В | = | А | + | В | – | А Ç В |, то есть учитываются общие для обоих множеств элементы.

Пример. А = {1, 2, 3} | А | = 3; В = {1, 2, 3, 4, 5} | В | = 5, тогда А È В = {1, 2, 3, 4, 5} | А È В | = 5; А Ç В = {1, 2, 3} | А Ç В | = 3, то есть получим равенство: | А È В | = | А | + | В | – | А Ç В | 5 = 3 + 5 – 3.

Для конечного множества М мощность его булеана | В(М) | равна 2^|М|.