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

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

Определение 1.1. Множество – это любая, определенная совокупность объектов. Объекты из которых составлено множество называют его элементами. Элементы множества различны и отличны друг от друга. Множества обозначают прописными буквами латинского алфавита, а их элементы – строчными. Например N, Z, Q, R – множества натуральных, целых, рациональных и действительных чисел.

N={1, 2, 3…} A={a₁, a₂, a₃…}

Если объект х является элементом множества М, то говорят, что хÎМ. Если х не является элементом множества М, то говорят, что хÏМ.

Одно множество равно другому, если выполняется условие: A=B | A B & B A

Множество не содержащее элементов называется пустым. Его обозначают Ø.

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

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

1)перечислением элементов множества А={a₁, a₂,…, a_n|n=6} (перечислением можно задавать только конечное множество);

2) характеристическим предикатом M={ x | P(x) }, где P(x) – предикат.

Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения, возвращаемое логическое значение. Если для данного элемента условие выполнено, т.е. P(x) = 1, то этот элемент принадлежит определяемому множеству, в противном случае – не принадлежит. Пример 1.1.:

M = { x | xÎN & x < 10}

P(x) = (11) = ( 11 & 11 < 10 ) = 0 11ÏМ

3) порождающей процедурой: M={ x | x := f }

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

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

Пример 1.2.: M = { x | x := from 1 to 9 generate x}

Диаграммы Венна.

Определение 1.2. Диаграммы Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматривать как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

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

Самого понятия множество недостаточно, следует определить способы конструирования новых множеств из уже имеющихся, т.е. задать операции над множествами.

Множество A содержится в множестве B (множество B включает множество A), если элемент множества A есть элемент множества B. A B:=xÎA=>xÎB. В этом случае A называют подмножеством B, а B – надмножеством A. Также возможен случай когда множество А включено в В и может полностью совпадать с ним (А В).

Обычно рассматривают следующие операции над множествами:

1. Объединение AÈB := { x | xÎA xÎB}

2. Пересечение AÇB:= { x | xÎA & xÎB}

3. Разность A \ B := { x | xÎA xÏB}

4. Симметричная разность ADB:=(AÈB) \ (AÇB)

5. Дополнение :={ x | x Ï A }Операция Дополнение подразумевает некоторый универсум U: := U \ A