Часть 1. Краткий теоретический материал

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

1.1. Понятие множества

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

Если объект x является элементом множества M, то говорят, что x принадлежит М (x  M). В противном случае говорят, что x не принадлежит M (x  M).

Множество, не содержащее элементов, называется пустым ().

Обычно в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества U (своего для каждого случая), которое называется универсальным множеством (или универсумом).

Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами:

• Перечислением: M = {a₁, a₂, …, a_k}

• Характеристическим предикатом: M ={x  P(x)}

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

Пример. M₀ = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае – не принадлежит.

Пример. M₀ = {n  n  N  n < 10}

(Множество M₀ состоит из элементов n таких, которые принадлежат множеству натуральных чисел и меньше 10)

1.2. Объединение, пересечение, дополнение, разность множеств

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

A  B = {x  x  A  (или) x  B}

П ересечением (или произведением) множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и А, и В.

A  B = {x  x  A  (и) x  B}

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

A \ B = {x  x  A  x  B}

Симметрическая разность (или кольцевая сумма):

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

= {x  (x  A  x  B)  (x  A  x  B)}

Дополнением (до универсального множества) или абсолютным дополнением называется множество всех элементов, не принадлежащих А.

Ā = {x  x  A}

Ā = U \ A

Пример. Пусть А = {1, 2, 3}, B = {3, 4, 5}.

Определим множества D₁ = (A  B) \ (A  B) и D₂ = A  B.

A  B = {1, 2, 3, 4, 5}

A  B = {3}

D₁ = (A  B) \ (A  B) = {1, 2, 4, 5}

D2 = A  B = {1, 2, 4, 5}

1.3. Прямое произведение множеств

Пусть А и В – два множества. Прямым (декартовым) произведением двух множеств называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит А, а второй принадлежит В:

A  B = {(a, b)  a  A  b  B}

Степенью множества А называется его прямое произведение самого на себя:

Соответственно, А¹ = A, A² = A  A и вообще Аⁿ = A ^n–1  A.

Пример. А = {a, b}, B = {1, 2, 3}.

A  B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}

B  A = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}

A  B  B  A (Декартово произведение не подчиняется коммутативному закону, и A  B = B  A справедливо, если А = В)

A² = {(a, a), (a, b), (b, a), (b, b)}

A³ = {(a, a, a), (a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a), (b, b, b)}