bulgakov

05. Разность и симметрическая разность множеств

Что пригодится из прошлого: объединение, пересечение и распределительные законы с формулой для ∣A∪B∣|A\cup B|. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

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

A∖BA\setminus B — это элементы AA, которых нет в BB:

A∖B={x∣x∈A и x∉B}.\boxed{A\setminus B=\{x\mid x\in A\text{ и }x\notin B\}}.

Читают «AA без BB» или «разность AA и BB». Порядок здесь важен: первое множество даёт элементы, второе указывает, какие убрать.

Пусть A={1,2,3,4}A=\{1,2,3,4\}, B={3,4,5}B=\{3,4,5\}. Из AA убираем общие элементы 3,43,4, поэтому

A∖B={1,2},B∖A={5}.A\setminus B=\{1,2\},\qquad B\setminus A=\{5\}.

Число 55 не может попасть в A∖BA\setminus B: его изначально нет в AA. Этот пример сразу показывает, почему множества в разности нельзя переставлять местами.

Свойства

Для любых A,BA,B справедливо:

Равенство Причина
A∖∅=AA\setminus\varnothing=A Убирать нечего.
A∖A=∅A\setminus A=\varnothing Убираем все элементы AA.
A∖B=∅  ⟺  A⊆BA\setminus B=\varnothing\iff A\subseteq B Не остаётся элементов AA, которые отсутствуют в BB.
A∖B=A  ⟺  A∩B=∅A\setminus B=A\iff A\cap B=\varnothing Из AA ничего не удаляется ровно при отсутствии общих элементов.

В последних двух строках знак   ⟺  \iff требует обоих направлений. Если A⊆BA\subseteq B, удалится всё AA; если удалилось всё, каждый элемент AA был в BB. Если A∩B=∅A\cap B=\varnothing, всё AA останется; если всё осталось, общих элементов не было.

Для конечных множеств удаляются ровно элементы пересечения, поэтому

∣A∖B∣=∣A∣−∣A∩B∣.\boxed{|A\setminus B|=|A|-|A\cap B|}.

В нашем примере 4−2=24-2=2. Нельзя без условия вычитать ∣B∣|B|: число 55 увеличивает ∣B∣|B|, но из AA его убрать нельзя. Если же B⊆AB\subseteq A, то A∩B=BA\cap B=B и ∣A∖B∣=∣A∣−∣B∣|A\setminus B|=|A|-|B|.

2. Симметрическая разность

A△BA\triangle B содержит элементы, принадлежащие ровно одному из двух множеств:

A△B=(A∖B)∪(B∖A).\boxed{A\triangle B=(A\setminus B)\cup(B\setminus A)}.

Для тех же A,BA,B:

A△B={1,2}∪{5}={1,2,5}.A\triangle B=\{1,2\}\cup\{5\}=\boxed{\{1,2,5\}}.

Общие элементы 3,43,4 исключены. Сравним четыре операции:

A∪B={1,2,3,4,5}— хотя бы в одном;A∩B={3,4}— в обоих;A∖B={1,2}— в A, но не в B;A△B={1,2,5}— ровно в одном.\begin{aligned} A\cup B&=\{1,2,3,4,5\} &&\text{— хотя бы в одном;}\\ A\cap B&=\{3,4\} &&\text{— в обоих;}\\ A\setminus B&=\{1,2\} &&\text{— в }A\text{, но не в }B;\\ A\triangle B&=\{1,2,5\} &&\text{— ровно в одном.} \end{aligned}

Карта областей

Вернёмся к «карте» из прошлых глав: A={1,2,3,4}A=\{1,2,3,4\}, B={3,4,5}B=\{3,4,5\}, числа от 11 до 66.

Область Элементы в AA? в BB? A∪BA\cup B A∩BA\cap B A∖BA\setminus B B∖AB\setminus A A△BA\triangle B
только в AA 1, 2 да нет ✓ — ✓ — ✓
и в AA, и в BB 3, 4 да да ✓ ✓ — — —
только в BB 5 нет да ✓ — — ✓ ✓
ни в AA, ни в BB 6 нет нет — — — — —

Разность A∖BA\setminus B — область «только в AA»; B∖AB\setminus A — «только в BB»; симметрическая разность — обе «только»-области вместе, то есть «ровно в одном из двух». Общая область в разность и в симметрическую разность не входит.

Свойства и важная ловушка

Для любых A,B,CA,B,C:

A△∅=A,A△A=∅,A△B=B△A,(A△B)△C=A△(B△C).\begin{aligned} &A\triangle\varnothing=A,\qquad A\triangle A=\varnothing,\\ &A\triangle B=B\triangle A,\\ &(A\triangle B)\triangle C=A\triangle(B\triangle C). \end{aligned}

Первые три равенства прямо следуют из «ровно в одном из двух». Но для трёх множеств фраза «ровно в одном» уже неверна: элемент, принадлежащий всем трём, тоже остаётся. Например,

({1}△{1})△{1}=∅△{1}={1}.(\{1\}\triangle\{1\})\triangle\{1\} =\varnothing\triangle\{1\}=\{1\}.

Почему можно переставлять скобки? Представим, что начинаем с пустого множества и по очереди берём симметрическую разность с AA, BB, CC. При симметрической разности с новым множеством принадлежность xx меняется только тогда, когда xx есть в этом новом множестве: был в результате — исчезнет, не был — появится. Поэтому две такие смены отменяют друг друга, а третья снова включает элемент. Для трёх множеств остаются элементы, встречающиеся в одном или во всех трёх.

Проверим эту мысль для обеих расстановок скобок. Следим за одним элементом xx. Если x∉Cx\notin C, он входит в (A△B)△C(A\triangle B)\triangle C ровно тогда, когда находится в одном из A,BA,B. Если x∈Cx\in C, он входит в результат, когда не входит в A△BA\triangle B, то есть когда находится в нуле или двух множествах из A,BA,B. Итого слева xx принадлежит одному или трём из A,B,CA,B,C.

Справа рассуждаем так же, но сначала смотрим на AA: если x∉Ax\notin A, он должен находиться ровно в одном из B,CB,C; если x∈Ax\in A, он должен находиться в нуле или двух из B,CB,C. Снова получается один или три из трёх множеств. Значит, состав множеств с обеих сторон одинаков.

Ту же проверку удобно сделать по областям для трёх множеств. Слева и справа элемент входит ровно тогда, когда он лежит в нечётном числе множеств (в одном или во всех трёх):

Код В AA? В BB? В CC? в скольких из A,B,CA,B,C (A△B)△C(A\triangle B)\triangle C A△(B△C)A\triangle(B\triangle C)
000 нет нет нет 0 — —
001 нет нет да 1 ✓ ✓
010 нет да нет 1 ✓ ✓
011 нет да да 2 — —
100 да нет нет 1 ✓ ✓
101 да нет да 2 — —
110 да да нет 2 — —
111 да да да 3 ✓ ✓

Для конечных множеств

∣A△B∣=∣A∣+∣B∣−2∣A∩B∣.\boxed{|A\triangle B|=|A|+|B|-2|A\cap B|}.

В сумме ∣A∣+∣B∣|A|+|B| каждый общий элемент посчитан дважды, а в симметрическую разность он вообще не входит. Поэтому убираем оба подсчёта. То же следует из двух непересекающихся частей определения. Элемент из A∖BA\setminus B не может одновременно быть в B∖AB\setminus A: первая часть требует принадлежности AA, а вторая — отсутствия в AA. Поэтому их мощности можно просто сложить:

∣A△B∣=∣A∖B∣+∣B∖A∣=(∣A∣−∣A∩B∣)+(∣B∣−∣A∩B∣)=∣A∣+∣B∣−2∣A∩B∣.\begin{aligned} |A\triangle B| &=|A\setminus B|+|B\setminus A|\\ &=(|A|-|A\cap B|)+(|B|-|A\cap B|)\\ &=|A|+|B|-2|A\cap B|. \end{aligned}

В нашем примере 4+3−2⋅2=34+3-2\cdot2=3, что совпадает с числом элементов {1,2,5}\{1,2,5\}.

Проверь себя

1. Для A={1,2,3,4,5}A=\{1,2,3,4,5\}, B={4,5,6}B=\{4,5,6\} найдите A∖BA\setminus B, A△BA\triangle B и ∣A△B∣|A\triangle B| по формуле.

Решение

A∖B={1,2,3}A\setminus B=\{1,2,3\}. Симметрическая разность: A△B={1,2,3}∪{6}={1,2,3,6}A\triangle B=\{1,2,3\}\cup\{6\}=\{1,2,3,6\}. По формуле ∣A△B∣=∣A∣+∣B∣−2∣A∩B∣=5+3−2⋅2=4|A\triangle B|=|A|+|B|-2|A\cap B|=5+3-2\cdot2=4 — совпало с числом элементов {1,2,3,6}\{1,2,3,6\}.

2. Проверьте ассоциативность на примере A={1,2}A=\{1,2\}, B={2,3}B=\{2,3\}, C={3,4}C=\{3,4\}: найдите (A△B)△C(A\triangle B)\triangle C и A△(B△C)A\triangle(B\triangle C).

Решение

A△B={1,3}A\triangle B=\{1,3\}, затем (A△B)△C={1,3}△{3,4}={1,4}(A\triangle B)\triangle C=\{1,3\}\triangle\{3,4\}=\{1,4\}. Справа: B△C={2,4}B\triangle C=\{2,4\}, затем A△{2,4}={1,4}A\triangle\{2,4\}=\{1,4\}. Результаты совпали.

ПрактикаЗагружаем тест…