АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

Например, очевидны следующие включения 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 и 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 элементов.

Дата добавления: 2015-09-27 | Просмотры: 908 | Нарушение авторских прав