bulgakov

07. Обобщённые законы де Моргана

Что пригодится из прошлого: законы де Моргана для двух множеств и объединение и пересечение нескольких множеств. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Все дополнения берутся относительно одного фиксированного универсального множества UU; A1,…,An⊆UA_1,\ldots,A_n\subseteq U, n≥1n\ge1.

Для двух множеств мы уже знаем:

A∪B‾=A‾∩B‾.\overline{A\cup B}=\overline A\cap\overline B. A∩B‾=A‾∪B‾.\overline{A\cap B}=\overline A\cup\overline B.

Та же мысль работает для любого конечного числа множеств. Сначала вспомним запись: например,

⋃i=14Ai=A1∪A2∪A3∪A4.\bigcup_{i=1}^{4}A_i=A_1\cup A_2\cup A_3\cup A_4. ⋂i=14Ai=A1∩A2∩A3∩A4.\bigcap_{i=1}^{4}A_i=A_1\cap A_2\cap A_3\cap A_4.

Главное — правильно отрицать условие принадлежности. «Попасть хотя бы в одно множество» отрицается как «не попасть ни в одно». А «попасть в каждое» отрицается как «найдётся хотя бы одно, куда не попал». Поэтому:

⋃i=1nAi‾=⋂i=1nAi‾.\boxed{ \overline{\bigcup_{i=1}^{n}A_i} = \bigcap_{i=1}^{n}\overline{A_i} }. ⋂i=1nAi‾=⋃i=1nAi‾.\boxed{ \overline{\bigcap_{i=1}^{n}A_i} = \bigcup_{i=1}^{n}\overline{A_i} }.

Например, при n=3n=3 получаем:

A∪B∪C‾=A‾∩B‾∩C‾.\overline{A\cup B\cup C} = \overline A\cap\overline B\cap\overline C. A∩B∩C‾=A‾∪B‾∪C‾.\overline{A\cap B\cap C} = \overline A\cup\overline B\cup\overline C.

В левых частях черта стоит над всем объединением или пересечением: сначала выполняем операцию, затем берём дополнение результата. В правых частях дополнение берём у каждого AiA_i отдельно, а уже потом соединяем их. Именно равенство этих двух способов и нужно доказать.

Карта для трёх множеств

Для n=3n=3 каждый элемент описывается кодом из трёх цифр: на ii-м месте 11, если он лежит в AiA_i (здесь для краткости A,B,CA,B,C). Вне объединения лежит только элемент с кодом 000000 — и ровно он лежит в каждом из дополнений; вне пересечения лежат все, кроме кода 111111:

Код В AA? В BB? В CC? A∪B∪CA\cup B\cup C A∪B∪C‾\overline{A\cup B\cup C} A‾∩B‾∩C‾\overline A\cap\overline B\cap\overline C A∩B∩CA\cap B\cap C A∩B∩C‾\overline{A\cap B\cap C} A‾∪B‾∪C‾\overline A\cup\overline B\cup\overline C
000 нет нет нет — ✓ ✓ — ✓ ✓
001 нет нет да ✓ — — — ✓ ✓
010 нет да нет ✓ — — — ✓ ✓
011 нет да да ✓ — — — ✓ ✓
100 да нет нет ✓ — — — ✓ ✓
101 да нет да ✓ — — — ✓ ✓
110 да да нет ✓ — — — ✓ ✓
111 да да да ✓ — — ✓ — —

Столбцы A∪B∪C‾\overline{A\cup B\cup C} и A‾∩B‾∩C‾\overline A\cap\overline B\cap\overline C совпадают, как и столбцы A∩B∩C‾\overline{A\cap B\cap C} и A‾∪B‾∪C‾\overline A\cup\overline B\cup\overline C.

Почему равенства верны

Возьмём произвольный x∈Ux\in U. Для первого закона все переходы обратимы — каждый можно прочитать и слева направо, и справа налево:

x∈⋃i=1nAi‾  ⟺  x∉⋃i=1nAi  ⟺  ∀i∈{1,…,n}: x∉Ai  ⟺  x∈⋂i=1nAi‾.\begin{aligned} x\in\overline{\bigcup_{i=1}^{n}A_i} &\iff x\notin\bigcup_{i=1}^{n}A_i\\ &\iff \forall i\in\{1,\ldots,n\}:\ x\notin A_i\\ &\iff x\in\bigcap_{i=1}^{n}\overline{A_i}. \end{aligned}

Во втором законе достаточно одного множества, в котором xx отсутствует:

x∈⋂i=1nAi‾  ⟺  x∉⋂i=1nAi  ⟺  ∃i∈{1,…,n}: x∉Ai  ⟺  x∈⋃i=1nAi‾.\begin{aligned} x\in\overline{\bigcap_{i=1}^{n}A_i} &\iff x\notin\bigcap_{i=1}^{n}A_i\\ &\iff \exists i\in\{1,\ldots,n\}:\ x\notin A_i\\ &\iff x\in\bigcup_{i=1}^{n}\overline{A_i}. \end{aligned}

Например, если x∈A1x\in A_1 и x∈A2x\in A_2, но x∉A3x\notin A_3, то xx уже входит в A1∩A2∩A3‾\overline{A_1\cap A_2\cap A_3}: отсутствовать во всех трёх множествах не требуется. В каждой цепочке крайние условия равносильны для любого x∈Ux\in U, поэтому оба равенства множеств доказаны.

Где это пригодится

Законы де Моргана нужны, чтобы считать элементы, не лежащие ни в одном из множеств: в принципе включений и исключений их число равно ∣S∣−∣S1∪⋯∪Sn∣|S|-|S_1\cup\dots\cup S_n|.

Проверь себя

1. Отрицание утверждения «xx лежит хотя бы в одном из A1,…,A5A_1,\dots,A_5» — какое?

Решение

«xx не лежит ни в одном из A1,…,A5A_1,\dots,A_5», то есть x∈A1‾∩⋯∩A5‾x\in\overline{A_1}\cap\dots\cap\overline{A_5}. Это первый обобщённый закон де Моргана.

2. Пусть U={1,…,8}U=\{1,\dots,8\}, A1={1,2,3}A_1=\{1,2,3\}, A2={3,4,5}A_2=\{3,4,5\}, A3={5,6}A_3=\{5,6\}. Найдите A1∪A2∪A3‾\overline{A_1\cup A_2\cup A_3} и проверьте закон.

Решение

A1∪A2∪A3={1,2,3,4,5,6}A_1\cup A_2\cup A_3=\{1,2,3,4,5,6\}, дополнение {7,8}\{7,8\}. Дополнения: A1‾={4,5,6,7,8}\overline{A_1}=\{4,5,6,7,8\}, A2‾={1,2,6,7,8}\overline{A_2}=\{1,2,6,7,8\}, A3‾={1,2,3,4,7,8}\overline{A_3}=\{1,2,3,4,7,8\}; их пересечение — {7,8}\{7,8\}. Результаты равны.

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