Что пригодится из прошлого: законы де Моргана для двух множеств и объединение и пересечение нескольких множеств. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Все дополнения берутся относительно одного фиксированного универсального множества U; A1,…,An⊆U, n≥1.
Для двух множеств мы уже знаем:
A∪B=A∩B.
A∩B=A∪B.
Та же мысль работает для любого конечного числа множеств. Сначала вспомним запись: например,
i=1⋃4Ai=A1∪A2∪A3∪A4.
i=1⋂4Ai=A1∩A2∩A3∩A4.
Главное — правильно отрицать условие принадлежности. «Попасть хотя бы в одно множество» отрицается как «не попасть ни в одно». А «попасть в каждое» отрицается как «найдётся хотя бы одно, куда не попал». Поэтому:
i=1⋃nAi=i=1⋂nAi.
i=1⋂nAi=i=1⋃nAi.
Например, при n=3 получаем:
A∪B∪C=A∩B∩C.
A∩B∩C=A∪B∪C.
В левых частях черта стоит над всем объединением или пересечением: сначала выполняем операцию, затем берём дополнение результата. В правых частях дополнение берём у каждого Ai отдельно, а уже потом соединяем их. Именно равенство этих двух способов и нужно доказать.
Карта для трёх множеств
Для n=3 каждый элемент описывается кодом из трёх цифр: на i-м месте 1, если он лежит в Ai (здесь для краткости A,B,C). Вне объединения лежит только элемент с кодом 000 — и ровно он лежит в каждом из дополнений; вне пересечения лежат все, кроме кода 111:
| Код |
В A? |
В B? |
В C? |
A∪B∪C |
A∪B∪C |
A∩B∩C |
A∩B∩C |
A∩B∩C |
A∪B∪C |
| 000 |
нет |
нет |
нет |
— |
✓ |
✓ |
— |
✓ |
✓ |
| 001 |
нет |
нет |
да |
✓ |
— |
— |
— |
✓ |
✓ |
| 010 |
нет |
да |
нет |
✓ |
— |
— |
— |
✓ |
✓ |
| 011 |
нет |
да |
да |
✓ |
— |
— |
— |
✓ |
✓ |
| 100 |
да |
нет |
нет |
✓ |
— |
— |
— |
✓ |
✓ |
| 101 |
да |
нет |
да |
✓ |
— |
— |
— |
✓ |
✓ |
| 110 |
да |
да |
нет |
✓ |
— |
— |
— |
✓ |
✓ |
| 111 |
да |
да |
да |
✓ |
— |
— |
✓ |
— |
— |
Столбцы A∪B∪C и A∩B∩C совпадают, как и столбцы A∩B∩C и A∪B∪C.
Почему равенства верны
Возьмём произвольный x∈U. Для первого закона все переходы обратимы — каждый можно прочитать и слева направо, и справа налево:
x∈i=1⋃nAi⟺x∈/i=1⋃nAi⟺∀i∈{1,…,n}: x∈/Ai⟺x∈i=1⋂nAi.
Во втором законе достаточно одного множества, в котором x отсутствует:
x∈i=1⋂nAi⟺x∈/i=1⋂nAi⟺∃i∈{1,…,n}: x∈/Ai⟺x∈i=1⋃nAi.
Например, если x∈A1 и x∈A2, но x∈/A3, то x уже входит в A1∩A2∩A3: отсутствовать во всех трёх множествах не требуется. В каждой цепочке крайние условия равносильны для любого x∈U, поэтому оба равенства множеств доказаны.
Где это пригодится
Законы де Моргана нужны, чтобы считать элементы, не лежащие ни в одном из множеств: в принципе включений и исключений их число равно ∣S∣−∣S1∪⋯∪Sn∣.
Проверь себя
1. Отрицание утверждения «x лежит хотя бы в одном из A1,…,A5» — какое?
Решение
«x не лежит ни в одном из A1,…,A5», то есть x∈A1∩⋯∩A5. Это первый обобщённый закон де Моргана.
2. Пусть U={1,…,8}, A1={1,2,3}, A2={3,4,5}, A3={5,6}. Найдите A1∪A2∪A3 и проверьте закон.
Решение
A1∪A2∪A3={1,2,3,4,5,6}, дополнение {7,8}. Дополнения: A1={4,5,6,7,8}, A2={1,2,6,7,8}, A3={1,2,3,4,7,8}; их пересечение — {7,8}. Результаты равны.