Объединением множеств называется множество. Нахождение пересечения и объединения числовых множеств

Лекция 13: Операции над множествами. Упорядоченное множество

1. Объединение множеств

Объединение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y, т.е. принадлежат X или принадлежат Y.

Объединение X и Y обозначается через X∪Y

Формально x∈X∪Y ⇔ x∈X или x∈Y

Пример 1. Если X={1,2,3,4,5} и Y={2,4,6,8}, то

X∪Y={1,2,3,4,5,6,7,8}

Пример 2. Если X={x:x — отл.гр.}, и Y={x:x — gib.}, то

X∪Y={x:x — или отл., или gib}.

Пример 3. Если X — множество точек левого круга и Y — множество точек правого круга, то

X∪Y — заштрихованная область, ограниченная обоими кругами.

Понятие объединения можно распространить и на большее число множеств, на систему множеств. Обозначим через М={X 1 ,X 2 , ...,X n } совокупность n множеств X 1 ,X 2 , ...,X n , называемую иногда системой множеств. Объединение этих множеств

∪X i =∪(X∈M), Х=X 1 ∪X 2 ∪...∪X n

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

Для объединенных множеств справедливы:

• X∪Y = Y∪X — коммутативный закон
• (X∪Y)∪Z = X∪(Y∪Z) = X∪Y∪Z — ассоциативный закон,

справедливость которых вытекает из того, что левая и правая части равенств состоят из одних и тех же элементов.

Очевидно, что X∪∅ = X. Отсюда можно видеть, что ∅ играет роль нуля в алгебре множеств.

2. Пересечение множеств

Пересечение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y.

Пересечение множеств обозначается X∩Y.

Формально x∈X∩Y ⇔ x∈X и x∈Y

Пример 4. X={1,2,3,4,5} Y={2,4,6,8} X∩Y = {2,4}

Пример 5. Если Х — множество точек левого круга, а Y — множество точек правого круга, то X∩Y представляет собой заштрихованную область, являющуюся общей частью обоих кругов.

Множества X и Y называются непересекающимися (дизъюнктными), если они не имеют общих элементов, то есть если X∩Y=∅.

Пример 7. {1,2,3} и {4,5,6}

В отличие от алгебры чисел, где могут быть три возможности: a

X=Y; X⊂Y; Y⊂X; X∩Y=∅ и X и Y находятся в общем положении.

Говорят, что множества X и Y находятся в общем положении, если выполняются три условия:

1. существует элемент множества X, не принадлежащий Y;
2. существует элемент множества Y, не принадлежащий X;
3. существует элемент, принадлежащий как X, так и Y.

Аналогично объединению понятие пересечения можно распространить на систему множеств:

∩X=∩X i =X 1 ∩X 2 ∩...∩X n

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

Для пересечения множеств справедливы:

• X∩Y=Y∩X — коммутативный закон
• (X∩Y)∩Z = X∩(Y∩Z) = X∩Y∩Z — ассоциативный закон

Заметим также, что имеет место соотношение X∩∅=∅.

Пример 8. A={a,b}, B={b,c}, C={a,c}.

A∩B∩C=∅, хотя A∩B={b}, B∩C={c}

3. Разность множеств

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

Обозначается: X\Y.

Формально: x∈X\Y ⇔ x∈X и x∉Y

Пример 9. (см. Пример 1) X={1,2,3,4,5}, Y={2,4,6,8}, X\Y={1,3,5}, Y\X={6,8}

Разность множеств не обладает свойством коммутативности.

Если A\B=∅, то A⊂B — поставить? обратно

при A∩B≠∅

4. Универсальное множество

Роль нуля в алгебре множеств играет пустое множество. А нет ли такого множества, которое играет роль «1», т.е. удовлетворяет условию: X∪I = X, что означает, что пересечение или «общая часть» множества I и множества X для любого множества X совпадает с самим этим множеством. Это возможно лишь в том случае, если множество I содержит все элементы, из которых может состоять множество X, так что любое множество X полностью содержится в множестве I.

Множество I, удовлетворяющее этому условию, называется полным, или универсальным, или единичным.

Если при некотором рассмотрении участвуют только подмножества некоторого фиксированного множества, то это самое большое множество будем считать универсальным и обозначать I.

Пример 12 (Пример 1). I — множество целых чисел

Пример 13 (Пример 2). I — множество студ. гр.

Пример 14 (Пример 3). I — лист бумаги, доска

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

Универсальное множество обладает интересным свойством, которое не имеет аналогии в обычной алгебре, а именно, для любого множества X справедливо соотношение X∪I = I.

5. Дополнение множества

Множество, определяемое из соотношения X¯ = I\X, называется дополнением множества X (до универсального множества I).

На диаграмме множество X¯ представляет собой незаштрихованную область.

Формально: X = {x: x∈I и x∉X}.

Из определения следует, что X и X¯ не имеют общих элементов. Х∩X¯=∅.

Кроме того, не имеется элементов I, которые не принадлежали бы ни X, ни X¯ (его дополнению), так как те элементы, которые не принадлежат X, принадлежат X¯ (его дополнению). Следовательно, Х∪X¯=I.

Из симметрии данной формулы относительно Х и X¯ следует не только то, что X¯ является дополнением Х, но и что Х является дополнением X¯. Но дополнение X¯ есть X¯ ¯. Таким образом, X¯ ¯=X¯.

С помощью операции дополнения представим разность множеств:

X\Y = {x: x∈X и x∉Y} ={ x: x∈X и x∈Y¯ }, т.е. X\Y= Х∩Y¯.

Порядок выполнения операций:

1. дополнение;
2. пересечение;
3. объединение, разность.

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

6. Разбиение множества

Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств.

Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.

Пример. Продукция предприятия: — высший сорт, I, II, брак.

Рассмотрим некоторое множество M и систему множеств

М = {X 1 , X 2 , ..., X n }

Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям:

Любое множество X из M является подмножеством множества М

∀X∈M: X⊆M;

Любые два множества X и Y из М являются непересекающимися

∀X∈М, ∀Y∈M: X≠Y → X∩Y=∅.

Объединение всех множеств, входящих в разбиение, дает множество M

X 1 ∪X 2 ∪...∪ X n =M.

7. Тождества алгебры множеств

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

Если алгебраические выражения V(X,Y,Z) и S(X,Y,Z) представляют собой одно и то же множество, то их можно приравнять друг другу, получая алгебраическое тождество вида V(X,Y,Z) = S(X,Y,Z)

1. (X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогичное дистрибутивному закону (a+b)c=(a+c)(b+c) в обычной алгебре).
2. (X∩Y)∪Z = (X∪Z)∩(Y∪Z)
3. Если Y⊆X, то X∩Y=Y, X∪Y=X. Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит пересечение этих множеств, то есть общая множеств Х и Y совпадает с Y. В объединение множеств X и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества Х. Следовательно, X∪Y совпадает с X.
4. Пусть в примере 3 Y=X. Тогда, учитывая, что X⊆X, то X∩Х=Х, X∪Х=X. (идемпотентность).
5. Докажем тождество (X∪Y)¯=X¯∩Y¯. Предположим, что х∈(X∪Y)¯, то есть х∉X∪Y. Это значит, что х∉X и х∉Y, то есть и x&isinX¯ и x&isinY¯;. Следовательно, x∈X¯∩Y¯. Предположим теперь, что y∈X¯∩Y¯, то есть y∈X¯ и y∈Y¯. Это значит, что y∉X и y∉Y, то есть что y∉X∪Y. Следовательно, y∈(X∪Y)¯.
6. Тождество (X∩Y)¯=X¯∪Y¯. Обычно тождества 5) и 6) называются тождествами де-Моргана.
7. (A\B)∩C=(A∩C)\B=(A∩C)\(B∩C)
8. A\B=A\(A∩B)
9. A=(A∩B)∪(A\B)

Дополнение к занятию «операции над множествами»

Множество элементов, принадлежащих или A, или B, называют симметричной разностью или дизьюнктивной суммой.

S = A⊕B = (A\B)∪(B\A) = (A∩B¯)∪(A¯∪B) = (A∪B)∩(A∩B)¯

Для симметрической разности выполняются следующие законы:

1. 1) A⊕B = B ⊕A — коммутативность,
2. 2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,
3. 3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,
4. 4) A ⊕А = ∅
5. 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.

Упорядоченное множество

Упорядоченным множеством (или кортежем) называется последовательность элементов, то есть совокупность элементов, в которой каждый элемент занимает определенное место. Сами элементы — компоненты кортежа.

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

Число элементов кортежа называется его длиной. Обозначают кортеж скобками «< >», иногда круглыми «()». А=. Кортежи длины 2 называются упорядоченными парами, 3 — тройками, n-ками.

Частный случай: кортеж длины 1 —

Так, кортеж может рассматриваться как точка на плоскости или вектор, проведенный из начала координат в данную точку. Тогда компоненты a 1 , a 2 — проекции вектора на оси 1 и 2.

Пр 1 = a 1 , Пр 2 = a 2 , Пр i = a i , Пр 1 2 = — двухэлементный кортеж. Проекция кортежа на пустое множество осей — пустой кортеж.

Обобщая эти понятия, будем рассматривать упорядоченное n-элементное множество вещественных чисел (a 1 , ..., a n) как точку в воображаемом n–мерном пространстве (иногда называемом гиперпространством), или как n-мерный вектор. При этом компоненты n-элементного кортежа а будем рассматривать как проекции этого кортежа на соответствующие оси.

Пр i a = a i , i=1,2,...,n

Пр i,j,...,l a = , i=1,2,...,n

= ⇔ m = n и a 1 = b 1 , b 1 = b 2 , ...

A = < , , >

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

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

Формально: X*Y = {: x∈X, y∈Y}

Пример 2. Пусть X=<1,2>, Y=<1,3,4>

Тогда X*Y={<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4> } См. рис. а).

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

Прямое произведение изменяется при изменении порядка сомножителей т.е.

Прямое произведение множеств X 1 , X 2 , ..., X n — это множество, обозначаемое X 1 *X 2 *...*X n и состоящее из всех тех и только тех кортежей длины n, правая компонента которых принадлежит X 1 , вторая — X 2 и т.д.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Аналогично X 1 *X 2 *...*X n = ∅ тогда и только тогда, когда хотя бы одно из множеств X 1 , X 2 , ..., X n является пустым.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

M s =M*M*...*M, M 1 =M, M 0 =∧.

Обычно R — множество вещественных чисел, тогда R 2 =R*R — вещественная плоскость и R 3 =R*R*R — трехмерное вещественное пространство.

Пример. A={a,b,c,d,e,f,g,h}, B={1,2,3, ...,8}

Тогда A*B ={a 1 , a 2 , a 3 , ..., h7, h8} — множество обозначающее все 64 клеток шахматной доски.

Пример. Пусть A — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества обычно называют алфавитами. Элементы множества a n называются словами длины n в алфавите A. Множество всех символов в алфавите A — это множество A * = ∪A i = A 1 ∪A 2 ∪A 3 ... . При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями.

СЛОВО ⇔ <С,Л,О,В,О>

Теорема. Пусть a 1 , a 2 , ..., a n — конечные множества и |a 1 | = m 1 , |a 2 |=m 2 , ..., |a n |=m n . Тогда мощность множества a 1 *a 2 *a 3 *...*a n равна произведению мощностей a 1 , a 2 , ..., a n

|a 1 *a 2 *...*a n |=|a 1 |*|a 2 |*|a 3 |*...*|a n |= m 1 *m 2 *...*m n

Следствие |a n |=|A| n

Проекция множества.

Операция программирования множества тесно связана с операцией проектирования кортежа и может применяться лишь к таким множествам, элементами которых являются кортежи одинаковой длины.

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Пример. Пусть М={<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тогда Пр 2 М={2,1,3}, Пр 3 M={3}, Пр 4 M={4,5,3}, Пр 24 M={<2,4>,<1,5>,<3,3>}, Пр 13 M={<1,3>,<2,3>,<3,3>}, Пр 15 M={<1,5>,<2,5>,<1,3>}, Пр 25 M={<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно что если М=Х*Y то Пр 1 М=Х, Пр 2 М=Y

и если Q⊆Х*Y то Пр 1 Q⊆Х и Пр 2 Q⊆Y

Пример. V={,,}

Пр 1 V={a,c,d}

Пр 1 2V={,,}

Пр 2 3V={,}

Пр 1 3V={,,}

Пусть V — множество векторов одинаковой длины S.

Пр i V ={Пр i v/v∈Y}, Пр i i ...i k v = { Пр i i ...i k v/v∈Y}.

Если V =A 1 *A 2 *...*A n , то Пр i i ...i k V=A i1 *A i2 *...*A ik .

В общем случае Пр i V — вовсе не обязательно прямое произведение: оно может быть подмножеством.

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

Обозначим произвольную операцию знаком *. Множество, получаемое из данных множеств А и В, записывают в виде А*В. Полученное множество и саму операцию принято называть одним термином.

Замечание. Для основных числовых операций используют два термина: один обозначает саму операцию как действие, другой - число, получаемое после выполнения действия. Например, операция, обозначаемая +, называется сложением, а число, полученное в результате сложения, - суммой чисел. Аналогично - знак операции умножения, а результат а b - произведение чисел а и Ь. Тем нс менее часто эту разницу нс учитывают и говорят «Рассмотрим сумму чисел», имея в виду не конкретный результат, а саму операцию.

Операция пересечения. Пересечением множеств А и В АглВ , состоящее из всех объектов, каждый из которых принадлежит обоим множествам А и В одновременно.

Другими словами, АсВ - это множество всех.г, таких, что хеА и хеВ:

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

Операцию объединения иногда обозначают знаком + и называют сложением множеств.

Операции разности. Разностью множеств А и В называется множество, обозначаемое АВ , состоящее из всех объектов, каждый из которых лежит в А, но не лежит В.

Выражение АпВ читают «А в пересечении с В », AkjB- «А в объединении с В», АВ - «А без В».

Пример 7.1.1. Пусть А = {1, 3,4, 5, 8,9}, В = {2,4, 6, 8}.

Тогда AkjB= {1,2, 3,4, 5, 6, 8, 9}, AcB={ 4,8}, АВ = {1,3, 5, 9}, ЯЛ = {2,6}.»

На основе указанных операций можно определить еще две важные операции.

Операция дополнения. Пусть AqS. Тогда разность SA называется дополнением множества А до S и обозначается A s .

Пусть любое рассматриваемое множество является подмножеством некоторого множества U. Дополнение до такого фиксированного (в контексте решения той или иной задачи) множества U обозначают просто А . Также используются обозначения СА, с А, А".

Пример 7.1.2. Дополнение множества {1, 3,4, 5, 8, 9} до множества всех десятичных цифр равно {0, 2, 6, 7}.

Дополнение множества Q до множества R есть множество 1.

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

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

Операция симметрической разности. Симметрической разностью множеств А и В называется множество, обозначаемое А®В , состоящее из всех объектов, каждый из которых принадлежит в точности одному из множеств А и В:

Нетрудно видеть, что симметрическая разность есть объединение двух множеств АВ и ВА. Это же самое множество можно получить, если вначале объединить множества А и В, а затем убрать из множества общие элементы.

Пример 7.1.3. Пусть даны действительные числа а Тогда для соответствующих числовых промежутков имеем:

Заметим, что так как отрезок [а; Ь] содержит число с> а интервал (с; d) точку с не содержит, го число с лежит в разности [а; Ь] без [с; cf. А вот разность, например, (2;5), число 3 не содержит, так как оно лежит в отрезке . Имеем (2;5)=(2;3).

Пусть даны непересекающиеся множества А и В. Поскольку п - знак операции пересечения, то запись А(ЬВ некорректна. Неправильно также говорить, что у множеств нет пересечения. Пересечение есть всегда, оно определено для любых множеств. То, что множества не пересекаются, означает, что их пересечение пусто (то есть, выполнив указанную операцию, мы получаем пустое множество). Если же множества пересекаются, значит, их пересечение не пусто. Делаем вывод:

Обобщим операции объединения пересечения на случай, когда множеств более двух.

Пусть дана система К множеств. Пересечением множеств данной системы называется множество всех элементов, каждый из которых лежит во всех множествах их К.

Объединением множеств данной системы называется множество всех элементов, каждый из которых лежит хотя бы в одном множестве их К.

Пусть множества системы К занумерованы элементами какого-то семейства индексов /. Тогда любое множество из К можно обозначить А,-, где iel. Если совокупность конечная, то в качестве / используют множество первых натуральных чисел {1,2,...,и}. В общем случае / может быть бесконечным.

Тогда в общем случае объединение множеств А для всех iel обозначают (J А { , а пересечение - f]A i .

Пусть совокупность К конечная, тогда К= В этом случае

пишут AyjA 2 v...KjA„ и АГ4 2 (^---Г4п-

Пример 7.1.4. Рассмотрим промежутки числовой прямой Л| = [-оо;2], Л 2 =Н°; 3], Л 3 =}