02. Включение множеств. Операции над множествами

Определение. Говорят, что множество А Включено в множество В (и пишут АÍВ или ВÊА), если для любого элемента аÎА справедливо аÎВ.

Например, очевидны следующие включения NÍZÍQÍR.

Свойства:

1) для любого множества А справедливо включение АÍА;

2) если АÍВ и ВÍА, то А = В;

3) если АÍВ и ВÍС, то АÍС;

4) для любого множества А справедливо включение ÆÍА.

Доказательство. Приведем доказательство лишь одного - четвертого свойства. Предположим противное, что Æ не включено в множество А. Это означает, что должно существовать хÎÆ такое, что хÏА. Но для любого х справедливо хÏÆ. Следовательно такого х не существует и ÆÍА.

Замечание. Необходимо различать символ принадлежности Î и символ включения Í. Символ принадлежности не обязан удовлетворять тем же свойствам что и символ включения. Так, например, 1ÎZ, ZÎ{Z}, однако 1Ï{Z}.

Операция “объединение множеств”. Пусть А и В два множества. Объединением этих множеств называется множество АÈВ, состоящее из тех элементов, которые принадлежат хотя бы одному из множеств А или В:

АÈВ = {x: хÎА либо хÎВ}.

Операция “разность множеств”. Для множеств А и В разность множеств А-В состоит из тех и только тех элементов х, которые удовлетворяют следующим двум условиям хÎА и хÏВ:

А - В = {х: хÎА и хÏВ}.

Операция “пересечение множеств”. Для множеств А и В их пересечением АÇВ называется множество таких элементов х, которые принадлежат как А, так и В:

АÇВ = {х: хÎА и хÎВ}.

Операция “симметрическая разность множеств”. Для множеств А и В их симметрической разностью называется множество

АDВ = (А – В)È(В – А).

Наиболее часто нами будут использоваться операции объединения и пересечения. Они могут быть распространены на любое число множеств (так же как и другие операции):

È aÎI Аa = {х: $a ÎI: хÎАa },

Ç aÎI Аa = {х: "a ÎI: хÎАa }.

В случае, когда множество индексов I = N, применяется запись вида Èn. Например,

Если Аn = (–1/n, 1/n ), то Ç nАn = {0}.

Если ВÍА, то разность множеств А – В называют еще дополнительным множеством к В или просто дополнением в А и обозначают ВC.

Операции над множествами хорошо иллюстрируются диаграммами Венна

Теорема 1. Для любых множеств A, B, C, D справедливы равенства

1. AÈ(BÈC) = (AÈB)ÈC	1'. AÇ(BÇC) = (AÇB)ÇC
2. AÈB = BÈA	2'. AÇB = BÇA
3. AÈ(BÇC) = (AÈB)Ç(AÈC)	3'. AÇ(BÈC) = (AÇB)È(AÇC)
4. АÈА = А	4'. АÇА = А
5. AÈÆ = A, AÈD = D (при условии A Í D)	5'. AÇÆ = Æ, AÇD = A (при условии AÍD)
6. AÈ(D – A) = D	6'. AÇ(D – A) = Æ

(Некоторые из приведенных выше свойств имеют специальные названия: 1 и 1' - свойства ассоциативности, 2 и 2' - коммутативности, 3 и 3' - дистрибутивности, 4 и 4' - идемпотентности).

Доказательство. Приведем доказательство свойств 3 и 5' (остальные доказываются просто или аналогично). Начнем со свойства 3. В силу одного из свойств операции включения (свойство 2), достаточно показать, что множество справа включено в множество, стоящее слева, и наоборот. Пусть хÎAÈ(BÇC). Тогда либо хÎA, либо хÎBÇC. Если хÎA, то хÎAÈB и хÎAÈC, т. е. хÎ(AÈB)Ç(AÈC). Если же хÎBÇC, то хÎB и хÎC. Следовательно хÎAÈB и хÎAÈC, т. е. снова хÎ(AÈB)Ç(AÈC). Этим показано включение AÈ(BÇC)Í(AÈB)Ç(AÈC). Наоборот, если хÎ(AÈB)Ç(AÈC), то хÎAÈB и хÎAÈC. Если хÎA, то хÎAÈ(BÇC). Если же хÏA, то обязательно хÎB и хÎC. Следовательно хÎBÇC и хÎAÈ(BÇC), что и доказывает утверждение.

Докажем свойство 5'. Из свойства 4 операции включения имеем ÆÍAÇÆ. Покажем обратное включение. Предположим противное, что AÇÆ не включено в Æ. Тогда существует хÎAÇÆ, т. е. хÎA и хÎÆ, такое, что хÏÆ. Но здесь написаны две противоречивые принадлежности. Это доказывает, что наше исходное предположение не верно и AÇÆÍÆ. Аналогично показывается и вторая часть рассматриваемого свойства.

В случае, когда все рассматриваемые множества заведомо принадлежат одному и тому же множеству U, это множество называют Универсумом.

Операции над множествами, хотя и являются похожими на операции сложения (объединение), вычитания (разность множеств), и умножения (пересечение) над обычными числами, отличны от них по своим свойствам. Так, например, (А-В)ÈВ = А верно не всегда (приведите пример).

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

1. АÈ(АÇВ) = А;

2. АÇ(АÈВ) = А;

3. АÈ(АСÇВ) = АÈВ.

Доказательства этих равенств несложные и опираются на теорему 1. Так первое из них получается из следующих равенств:

АÈ(АÇВ) = (АÇU)È(AÇB) = AÇ(UÈB) = AÇU = A.

Для множеств из универсума U справедливы следующие два закона де Моргана.

Теорема 2. Справедливы равенства:

(АÈВ)С = АС Ç ВС и (АÇВ)С = АС È ВС.

Доказательство. Докажем первое из этих равенств. Пусть аÎ(АÈВ)С. Тогда аÏАÈВ, т. е. аÏА и аÏВ. Последнее означает, что аÎАС и аÎВС, а значит и аÎАС Ç ВС. Цепочку этих рассуждений легко теперь провести в обратном порядке.

Второе равенство доказывается по аналогии.

На законах де Моргана основан Принцип двойственности, играющий важную роль в теории множеств и ее приложениях. Принцип двойственности состоит в следующем: если в некотором равенстве, связывающем подмножества данного универсума, заменить операцию Ç на È, а Ç на È, множество U на Æ, множество Æ на U, то получим верное равенство. Новое равенство называется двойственным по отношению к заданному.

Примеры. 1) АÈÆ=А Þ (АÈÆ)С = АС Þ АСÇÆС = АС Þ АС ÇU = АС. Последнее равенство в силу произвольности А (а следовательно и АС ) можно переписать ВÇU = В для любого множества В из U.

2) (Задача Льюиса Керролла) В одном жестоком бою из 100 пиратов 70 потеряли ногу, 75 – руку, 80 – глаз, 85 – ухо. Доказать, что как минимум 10 человек потеряли и руку, и ногу, и глаз, и ухо.

Решение. Обозначим через А – множество пиратов, потерявших ногу, В – потерявших руку, С – глаз, Е – ухо. Тогда нам необходимо найти М=АÇВÇСÇЕ (точнее, показать, что там не менее 10 элементов). Рассмотрим МС = АС ÈВС ÈСС ÈЕС. По условиям задачи в множестве АС – 30 элементов, в множестве ВС – 25 элементов, СС – 20, ЕС – 15 элементов. Таким образом, в множестве МС не более, чем 30 + 25 + 20 + 15 = 90 элементов. Следовательно, в самом множестве М не менее, чем 10 элементов.

Задачи.

1. Доказать следующие утверждения:

А) из АÍВ вытекает, что АÇВ = А и АÈВ = В;

Б) из АÇВ = А вытекает, что АÍВ;

В) из АÈВ = В вытекает, что АÍВ.

2. Доказать:

А) АÈ(ВÇС) = (АÈВ)Ç(АÈС);

Б) АÇ(ВÈС) = (АÇВ)È(АÇС).

3. Доказать включения:

А) (АÇС)È(ВÇD)Í(АÈВ)Ç(СÈD);

Б) (В – С) – (В – А)ÍА – С;

В) А – СÍ(А – В)È(В – С).

4. Доказать: АDВ = (АÈВ) – (АÇВ).

5. Верны ли утверждения для любых множеств А, В, С: 1) если АÍВ и ВÎС, то АÎС; 2) если А ¹ В и В ¹ С, то А ¹ С?

6. При каких условиях на А и В выполняется равенство (А – В)ÈВ = А.

7. Пусть U={a, b, c, d, e, f} – универсум, A = {a, b, c}, B = {a, c, e, f}, C = {d, e, f}. Найти А – В, В – С, С – В, А – С, АCÈВ, ВÇАC, АÇС, СDА.

8. Пусть АÇВ = Æ. Что можно сказать про множества А – В и В – А.

9. Пусть АÇВС = Æ. Что можно сказать про множества АÇВ и АÈВ.

10. Доказать равенства:

А) (А – В) – С = (А – С) – (В – С);

Б) (А – В)È(В – С)È(С – А)È(АÇВÇС) = АÈВÈС;

В) А – В = А – (АÇВ) = (АÈВ) – В;

Г) А – (А – В) = АÇВ;

Д) А – (ВÈС) = (А – В)Ç(А – С);

Е) А – (ВÇС) = (А – В)È(А – С);

Ж) (АÈВ) – С = (А – С)È(В – С).

11. Вытекает ли из А – В = С, что А = ВÈС?

12. Вытекает ли из А = ВÈС, что А – В = С?

13. Пусть А – заданное множество, про другое множество Х известно, что АDХ = А. Доказать, что Х = Æ.

14. Доказать равенства:

А) АD(ВDD) = (АDВ)DD;

Б) АÇ(ВDD) = (АÇВ)D(АÇD);

В) АDА = Æ;

Г) АDÆ = А.

15.Доказать следующие тождества:

А) (АÇВ)È(СÇD) = (АÈС)Ç(ВÈС)Ç(АÈD)Ç(ВÈD);

Б) (АÈВ)ÇА = (АÇВ)ÈА = А;

В) А – (В – С) = (А – В)È(АÇС);

Г) АÇ(В – С) = (АÇВ) – (АÇС) = (АÇВ) – С;

Д) АÈВ = АÈ(В – А);

Е) (АС)С = А;

Ж) АÈАС = U;

З) АÇАС = Æ;

И) [АСÈВ]ÇА = АÇВ;

К) АÇ(В-А) = Æ;

Л) А – (ВÈС) = (А – В) – С.

16.Доказать, что

А) (АÈВ)ÇС = АÈ(ВÇС) Û АÍС;

Б) А = В Û АDВ = Æ;

В) АÇВ = АÈ В Û А = В;

Г) (АÈВ) – В = А Û АÇВ = Æ;

Д) (А – В)ÈВ = А Û ВÍА;

Е) (АÇВ)ÈС = АÇ(ВÈС) Û СÍА;

Ж) АÍВ Þ АÈСÍВÈС;

З) АÍВ Þ АÇСÍВÇС;

И) АÍВ Þ (С-В) Í(С-А);

К) АÍВ Þ ВСÍАС;

Л) А = ВС Û АÇВ=Æ и АÈВ = U.

17.Доказать тождества:

А) АÈВ = АÈВÈ(АÇВ);

Б) А – В = А – (АÇВ);

В) АÈÆ = А;

Г) А – А = Æ;

Д) ADU = AC;

Е) АDВ = (АÈВ) – (АÇВ);

18. Пусть A Í U, B Í U. Доказать:

А) A – B = A Ç BC;

Б) ADB = (A Ç BC) È (AC Ç B).

19. Решить систему уравнений

А)

Где А, В, С – данные множества и В Í А Í С.

Б)

Где А, В, С – данные множества и В Í А , АÇС = Æ.

В)

Где А, В, С – данные множества и В Í А Í С.

20. Определить операции È, Ç, \ через:

А) Ç и D;

Б) D и È;

А) \ и D.

21. Доказать, что для любых множеств E, F, G, H справедливы

Включения:

А) ED(FÈG) Ì (EDF)È(EDG);

Б) ED (F – G) Ê (FDE) – (GDE);

В) (EDF)Ç(GDH) Ì (EÇG)D(FÇH);

Г) (EDF)-(GDH) Ì [ED(F-H)]È[(E-G)D(FÇH)];

Д) ED(FÇG) É (EDF)Ç(EDG);

Е) (FÇE)D(GÇH) Í (GDE)È(FDH).

22. Справедливо ли равенство

(АDВ)Ç(СDD) = (АÇС)D(ВÇD)?

23. Справедливо ли равенство

(АDВ)È(СDD) = (АÈС)D(ВÈD)?

< Предыдущая		Следующая >