Множество – это многое, мыслимое как единое.

 

Действовать без правил – самое трудное и самое утомительное занятие на этом свете.

А. Мандзони

ГЛАВА 2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

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

ЦЕЛИ

Освоив эту главу, студенты должны:

· знать основные свойства операций над множествами;

· уметь выполнять операции над множествами;

· уметь доказывать тождества с множествами.

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

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

С = А È В,

где È — знак объединения.

Теоретико-множественная запись операции объединения имеет следующий вид:

x ÎC = A È B ® x ÎA Ú x ÎB,

что означает: элемент х принадлежит множеству С, если х принадлежит множеству А или множеству В. Если изобразить элементы множеств А и В точками плоскости, расположенными внутри прямоугольника, то A È B представится множеством точек плоскости, расположенных внутри заштрихованной фигуры (рис.2.1). Такое геометрическое представление множеств называется диаграммой Эйлера-Венна.

Также можно записать: элемент х не принадлежит множеству С, если он не принадлежит множеству A и не принадлежит множеству В:

xÏC = A È B ® xÏA & xÏB.

Рис. 2.1. Пример операции объединения множеств А и В

Например, найдем объединение множеств А = { ЭВМ, студент } и В = { 1, 2, стол, ЭВМ, стул }. Результатом будет множество С = А È В = { 1, 2,стол, ЭВМ, стул, студент }.

Приведем основные свойства операции объединения:

· A È A = A                              - идемпотентность;

· A È B = B È A                                - коммутативность;

· (A È B) È C = A È (B È C)           - ассоциативность;

· A È Æ = A;

· (A Í A È B) & (B Í A È B).

Объединение в множествах является синонимом сложения в арифметике.

Заметим, что можно объединить не только два, но и любое количество множеств.

Объединением n множеств А₁, А₂,..., А _n называется множество, обозначаемое: , состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств A _i:

А₁ È А₂ È А₃ È … А _n = .

Мощность объединения множеств равна числу содержащихся в нем неповторяющихся элементов. Например, А = {1, 2, 3}, B = {1, 2, 9, 10}, C = А È В = {1, 2, 3, 9, 10} и мощность |C| = 5.

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

Множество С называется пересечением множеств А и В, если оно состоит из тех элементов, которые принадлежат одновременно множеству А и множеству В:

С = А Ç В,

где Ç — знак пересечения.

На рис.2.2. приведена диаграмма Эйлера-Венна, иллюстрирующая пересечение множеств А и В. Множество A Ç B изображено заштрихованной фигурой.

Рис. 2.2. Пример операции пересечения множеств

Теоретико-множественная запись операции пересечения имеет следующий вид:

x ÎC = A Ç B ® x ÎA & x ÎB,

что означает: элемент х принадлежит множеству С, если х одновременно принадлежит множеству А и множеству В.

Соответственно элемент х не принадлежит множеству С, если он не принадлежит множеству А или не принадлежит множеству В:

x ÏC = A Ç B ® x ÏA Ú x ÏB.

Приведем пример пересечения множеств A = { 1, 2, 3 } и B = { 3, 4, 5, 6 }. Результатом выполнения данной операции будет множество C = A Ç B = { 3 }.

Свойства операции пересечения:

· A Ç A = А                                  - идемпотентность;

· A Ç B = B Ç A                                - коммутативность;

· (A Ç B) Ç C = A Ç (B Ç C)           - ассоциативноcть;

· A Ç Æ = Æ;

· A Ç B =А «А Í B;

· A Ç B Í А & A Ç B Í B.

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

Рис. 2.3. Пример операции пересечения

Отметим, что операция пересечения может выполняться над любым количеством множеств. Пересечением n множеств А₁, А₂,..., А_n называется множество, обозначаемое через , состоящее из тех и только тех элементов, которые принадлежат каждому из множеств:

.

Примеры пересечения трех и четырех множеств на основе диаграмм Эйлера-Венна показаны на рис. 2.4, 2.5.

Рис. 2.4. Пример пересечения           Рис. 2.5. Пример пересечения

трех множеств                                 четырех множеств

Например, пересечением множеств А = {1, 2, 3}, B = {1, 2, 9, 10} является множество C = {1, 2} и его мощность |C| = 2.

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

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

Множество С называется разностью множеств А и В, если С состоит из тех элементов, которые одновременно принадлежат множеству А и не принадлежат множеству В:

С = А \ В,

где \ — знак разности.

Теоретико-множественная запись операции разности имеет следующий вид:

x ÎC = A \ B ® x ÎA & x ÏB,

что означает: элемент х принадлежит множеству С, если х принадлежит А и одновременно х не принадлежит множеству В.

Соответственно элемент х не принадлежит множеству С, если он не принадлежит множеству А или принадлежит множеству В:

x ÏC = A \ B ® x ÏA Ú x ÎB.

Например, заданы множества A = {1, 2} и B = {3, 8, 9}. Тогда разность между множествами A и B равна A \ B = {1, 2}, а разность между множествами B и A равна B \ A = {3, 8, 9}.

На рис. 2.6 приведены диаграммы Эйлера-Венна, иллюстрирующие операцию разности множеств A\B, а также разности множеств B \ A.

Рис. 2.6. Пример операции разности множеств

Очевидно, что:

А \ А = Æ; А \ U = Æ; В \ Æ = В; Æ \ А = Æ.

Основные свойства операции разности множеств:

· (A \ B) \ C = A \ (B \ C) = (A \ C) \ B - ассоциативноcть;

· A \ B Í A, B \ A Í A.

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

С = А Å В,

где Å — знак симметрической разности.

Теоретико-множественная запись операции симметрической разности имеет следующий вид:

x ÎC = A Å B ® (x ÎA & x ÏB) Ú (x ÎВ & x ÏА).

Например, заданы множества A = { 1, 2, 3, 8 } и B = { 3, 4, 8, 9 }. Тогда симметрическая разность A и B равна A Å B = { 1, 2, 4, 9 }.

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

Множество  называется дополнением множестваА до некоторого универсального множества U, если оно состоит из элементов, принадлежащих множеству U и не принадлежащих множеству А. Теоретико-множественная запись операции дополнения имеет вид

x Î  = U \ A ® x Î U & x Ï A,

x Ï  = U \ A ® x Ï U Ú x Î A.

На рис. 2.7 приведена диаграмма Эйлера-Венна, иллюстрирующая операцию дополнения множества А. Множество точек, расположенных в заштрихованной фигуре, образует множество .

Рис. 2.7. Пример дополнения множества А до универсального множества U

Основные свойства операции дополнения множества:

· = A,

· A È  = U,

· A Ç  = Æ,

·  = Æ,

·  = U.

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

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

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

Основные тождества алгебры множеств:

Пусть А, В и С - произвольные подмножества семейства Â(U).

· - ассоциативность;

·                                 - коммутативность;

·    - дистрибутивность;

·                                 - закон Де Моргана;

·                               - закон поглощения;

·                                        - закон тавтологии;

· ;

· A \ B = A \ (A Ç B);

· A \ B = A Ç ;

· A \ (A \ B) = A Ç B;

· A Ç (B \ C) = (A Ç B) \ (A Ç C).

Приведем формулу включений-исключений, которая позволяет вычислять мощности объединения двух множеств:

|A È B| = |A| + |B| - |A Ç B|.

Например, заданы множества A = { 1, 2, 3, 8 } и B = { 3, 4, 5, 8, 9 }. Тогда |A| = 4, |B| = 5, |A Ç B| = 2, |A È B| = 4 + 5 – 2 = 7.

2.6. Доказательства тождеств с множествами

Введем понятие записи. Например, выражение A Ç (B \ C) является записью. Число букв и знаков операций является длиной записи. В приведенном примере длина записи равна 5. Отметим, что различные по длине записи могут соответствовать одним и тем же множествам. Например, запись A Ç (B \ C) и запись(A Ç B) \ (A Ç C) равны, хотя имеют разную длину (5 и 7).

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

Рассмотрим способы доказательства равенств с множествами. Равенство с множествами имеет две формы:

1) E (A, B, C...) = F (A, B, C...).

E и F — высказывания над множествами A, B, C и т.д. Необходимо доказать или опровергнуть, что они равны.

2) E (A, B, C...) = Æ.

Доказать или опровергнуть, что высказывание равно Æ.

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

E = F ® E Í F & F Í E.

Причем доказательство включения E Í F называется необходимостью, а доказательство включения F Í E - достаточностью.

Например, необходимо доказать или опровергнуть справедливость тождества (A È B) Ç C = (A Ç C) È (B Ç C). Левую часть тождества обозначим Е, а правую F. Тогда нам необходимо доказать или опровергнуть, что

E Í F & F Í E.

1. Докажем необходимость: E Í F.

Для доказательства этой части предполагается, что существует какой-то элемент, принадлежащий множеству E, и далее путем различных преобразований делается попытка доказать, что этот элемент принадлежит F.

a Î E ® a Î[(A È B) Ç C] ® a Î (A È B) & a Î C ® (a Î A Ú a Î B) & a Î C ® a Î (A Ç B) & a Î (B Ç C) ® a Î [(A Ç C) È (B Ç C)] ® a Î F.

Следовательно, мы доказали, что Е включается в F.

2. Докажем теперь достаточность, т.е. докажем, что если a Î F, то a Î E.

a Î F ® a Î [(A Ç C) È (B Ç C)] ® a Î (A Ç C) Ú a Î (B Ç C) ® a Î A & a Î C Ú a Î B & a Î C ® a Î (A È B) & a Î C ® a Î [(A È B) Ç C] ® a Î E.

Следовательно, мы доказали, что F включается в E.

Значит, E = F и исходное тождество справедливо.

Для доказательства тождеств с множествами, записанными во второй форме, используется метод от противного. Например, докажем справедливость тождества

A \ [(A Ç B) È (A \ B)] = Æ.

Метод от противного предполагает, что это выражение не равно Æ, т.е. существует какой-то элемент, принадлежащий этому выражению. Здесь пытаются найти противоречие.

Обозначим левую часть тождества через Е и будем считать, что она не равна пустому множеству. Тогда существует хотя бы одни элемент, принадлежащий Е:

E ¹ Æ ® a Î E ® a Î A & a Ï [(A Ç B) È (A \ B)] ® a Î A & (a Ï (A Ç B) & a Ï (A \ B)) ® a Î A & (a Ï A & a Ï B) & (a Ï A Ú a Î B).

Таким образом, мы получили противоречие, когда элемент а одновременно принадлежит и не принадлежит множеству А. Значит, наше первоначальное предположение неверно и исходное тождество справедливо, т.е. равно Æ.

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 2.1. Пусть A = {1, 3, 5, 7, 9} и B = {3, 5, 6, 10, 11}. Множества А и В являются элементами семейства Â(N), где N - множество натуральных чисел. Найти A È B, A Ç B, А \ В, .

Ответ: A È B = {1, 3, 5, 7, 9, 10, 11, 6}; A Ç B = {3, 5}; A \ B = {1, 7, 9};  = {2, 4, 6, 8, 10, 11, 12,...}.(Множество Nв данной задаче является универсумом).

 

Пример 2.2. Пусть A = { x ÎN | х - четнoe число}, В = { x | ($ y)(y ÎN & x = 2 y +1}, C = { x | ($ y)(y ÎN & x = 4 y }.

Найти A È B, A Ç B, А \ В, A È C, A \ C.

Решение: Множества А, В, С являются подмножествами множества N. Множество В состоит из нечетных натуральных чисел, а множество А - из четных натуральных чисел, следовательно, A Ç B = Æ, A È B = N, A \ B = A. Элементы множества С - натуральные числа, кратные четырем, следовательно, множество С является собственным подмножеством множества А, а A È C = A,A \ C = { x Î N | ($ y)(y Î N & x = 4 y + 2)}.

Ответ: A È B = N, A Ç B = Æ, A \ B = A, A È C = A, A \ C = { x Î N | ($ y)(y Î N & x = 4 y + 2)}.

 

Пример 2.3. Докажите, что для записи последовательности операций объединения и пересечения необходимы круглые скобки, если количество операций больше одной.

Решение: Пусть имеется последовательность операций над произвольными множествами А, В, С - A Ç B È C, которую можно рассматривать как A Ç (B È C) либо как (A Ç B) È C. Покажем, что последние два множества не равны.

Предположим, что A = Æ, а C ¹ Æ.

Тогда (A Ç B) È C = (Æ Ç B) È C = Æ È C = C, в то время, как A Ç (B È C) = Æ Ç (B È C) = Æ.

Ответ: Таким образом, доказано, что (A Ç B) È C¹A Ç (B È C).

 

Пример 2.4. Доказать, что A Í B ® Í .

Решение: Пусть А и В - подмножества некоторого универсума Е и А Í В, тогда справедлива следующая последовательность утверждений:

(" x Î E)(x Î A ® x Î B); (" x Î E)(x Ï B ® x Ï A); (" x Î E)(x Î  ® x Î ),значит Í .