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