05. Разность и симметрическая разность множеств
Что пригодится из прошлого: объединение, пересечение и распределительные законы с формулой для . Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
1. Разность множеств
— это элементы , которых нет в :
Читают « без » или «разность и ». Порядок здесь важен: первое множество даёт элементы, второе указывает, какие убрать.
Пусть , . Из убираем общие элементы , поэтому
Число не может попасть в : его изначально нет в . Этот пример сразу показывает, почему множества в разности нельзя переставлять местами.
Свойства
Для любых справедливо:
| Равенство | Причина |
|---|---|
| Убирать нечего. | |
| Убираем все элементы . | |
| Не остаётся элементов , которые отсутствуют в . | |
| Из ничего не удаляется ровно при отсутствии общих элементов. |
В последних двух строках знак требует обоих направлений. Если , удалится всё ; если удалилось всё, каждый элемент был в . Если , всё останется; если всё осталось, общих элементов не было.
Для конечных множеств удаляются ровно элементы пересечения, поэтому
В нашем примере . Нельзя без условия вычитать : число увеличивает , но из его убрать нельзя. Если же , то и .
2. Симметрическая разность
содержит элементы, принадлежащие ровно одному из двух множеств:
Для тех же :
Общие элементы исключены. Сравним четыре операции:
Карта областей
Вернёмся к «карте» из прошлых глав: , , числа от до .
| Область | Элементы | в ? | в ? | |||||
|---|---|---|---|---|---|---|---|---|
| только в | 1, 2 | да | нет | ✓ | — | ✓ | — | ✓ |
| и в , и в | 3, 4 | да | да | ✓ | ✓ | — | — | — |
| только в | 5 | нет | да | ✓ | — | — | ✓ | ✓ |
| ни в , ни в | 6 | нет | нет | — | — | — | — | — |
Разность — область «только в »; — «только в »; симметрическая разность — обе «только»-области вместе, то есть «ровно в одном из двух». Общая область в разность и в симметрическую разность не входит.
Свойства и важная ловушка
Для любых :
Первые три равенства прямо следуют из «ровно в одном из двух». Но для трёх множеств фраза «ровно в одном» уже неверна: элемент, принадлежащий всем трём, тоже остаётся. Например,
Почему можно переставлять скобки? Представим, что начинаем с пустого множества и по очереди берём симметрическую разность с , , . При симметрической разности с новым множеством принадлежность меняется только тогда, когда есть в этом новом множестве: был в результате — исчезнет, не был — появится. Поэтому две такие смены отменяют друг друга, а третья снова включает элемент. Для трёх множеств остаются элементы, встречающиеся в одном или во всех трёх.
Проверим эту мысль для обеих расстановок скобок. Следим за одним элементом . Если , он входит в ровно тогда, когда находится в одном из . Если , он входит в результат, когда не входит в , то есть когда находится в нуле или двух множествах из . Итого слева принадлежит одному или трём из .
Справа рассуждаем так же, но сначала смотрим на : если , он должен находиться ровно в одном из ; если , он должен находиться в нуле или двух из . Снова получается один или три из трёх множеств. Значит, состав множеств с обеих сторон одинаков.
Ту же проверку удобно сделать по областям для трёх множеств. Слева и справа элемент входит ровно тогда, когда он лежит в нечётном числе множеств (в одном или во всех трёх):
| Код | В ? | В ? | В ? | в скольких из | ||
|---|---|---|---|---|---|---|
| 000 | нет | нет | нет | 0 | — | — |
| 001 | нет | нет | да | 1 | ✓ | ✓ |
| 010 | нет | да | нет | 1 | ✓ | ✓ |
| 011 | нет | да | да | 2 | — | — |
| 100 | да | нет | нет | 1 | ✓ | ✓ |
| 101 | да | нет | да | 2 | — | — |
| 110 | да | да | нет | 2 | — | — |
| 111 | да | да | да | 3 | ✓ | ✓ |
Для конечных множеств
В сумме каждый общий элемент посчитан дважды, а в симметрическую разность он вообще не входит. Поэтому убираем оба подсчёта. То же следует из двух непересекающихся частей определения. Элемент из не может одновременно быть в : первая часть требует принадлежности , а вторая — отсутствия в . Поэтому их мощности можно просто сложить:
В нашем примере , что совпадает с числом элементов .
Проверь себя
1. Для , найдите , и по формуле.
Решение
. Симметрическая разность: . По формуле — совпало с числом элементов .
2. Проверьте ассоциативность на примере , , : найдите и .
Решение
, затем . Справа: , затем . Результаты совпали.
