bulgakov

06. Дополнение множества и законы де Моргана

Что пригодится из прошлого: объединение и пересечение множеств, разность — дополнение есть разность U∖AU\setminus A. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

1. Универсальное множество и дополнение

Прежде чем сказать «всё, что не входит в AA», нужно уточнить: всё — среди чего? Выбираем универсальное множество UU; рассматриваемые множества, в том числе AA и BB, считаем его подмножествами. В задаче о целых числах можно взять U=ZU=\mathbb Z, в задаче о точках плоскости — все точки этой плоскости.

Дополнение AA — это элементы UU, которых нет в AA:

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

Черта сверху обозначает дополнение относительно выбранного UU.

Например, если U={1,2,3,4,5,6}U=\{1,2,3,4,5,6\} и A={1,2,3,4}A=\{1,2,3,4\}, то A‾={5,6}\overline A=\{5,6\}. Числа 77 в дополнении нет, хотя его нет и в AA: оно лежит за пределами UU. Если взять U={1,2,3,4,5,6,7}U=\{1,2,3,4,5,6,7\}, дополнение того же AA станет {5,6,7}\{5,6,7\}.

Свойства дополнения

Во всех строках UU одно и то же, A,B⊆UA,B\subseteq U:

Свойство Причина
A‾‾=A\overline{\overline A}=A Среди элементов UU вне дополнения находятся именно элементы AA.
∅‾=U\overline\varnothing=U, U‾=∅\overline U=\varnothing Вне пустого множества остаётся всё UU; вне самого UU — ничего.
A∩A‾=∅A\cap\overline A=\varnothing, A∪A‾=UA\cup\overline A=U Элемент UU либо в AA, либо вне AA, но не одновременно там и там.
A⊆B⇒B‾⊆A‾A\subseteq B\Rightarrow\overline B\subseteq\overline A Вне большего BB может остаться только то, что и вне меньшего AA.

В последней строке направление включения меняется. Пусть A⊆BA\subseteq B и x∈B‾x\in\overline B. Тогда x∈Ux\in U и x∉Bx\notin B. В AA его тоже нет: иначе из A⊆BA\subseteq B следовало бы x∈Bx\in B. Значит, x∈A‾x\in\overline A, что и доказывает B‾⊆A‾\overline B\subseteq\overline A.

2. Законы де Моргана

Для A,B⊆UA,B\subseteq U верно:

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

Все дополнения здесь берутся относительно одного UU.

Первый закон. Чтобы быть вне объединения, нужно отсутствовать в обоих множествах. Отсюда пересечение дополнений:

не в A∪B⟺не в A и не в B.\text{не в }A\cup B \quad\Longleftrightarrow\quad \text{не в }A\text{ и не в }B.

Докажем равенство в обе стороны. Если x∈A∪B‾x\in\overline{A\cup B}, то x∈Ux\in U, x∉A∪Bx\notin A\cup B; значит, x∉Ax\notin A и x∉Bx\notin B. Поэтому x∈A‾∩B‾x\in\overline A\cap\overline B. Обратно, если x∈A‾∩B‾x\in\overline A\cap\overline B, то x∈Ux\in U, но его нет ни в AA, ни в BB. Следовательно, x∉A∪Bx\notin A\cup B и x∈A∪B‾x\in\overline{A\cup B}. Оба включения доказаны.

Второй закон. Чтобы быть вне пересечения, достаточно отсутствовать хотя бы в одном множестве. Отсюда объединение дополнений:

не в A∩B⟺не в A или не в B.\text{не в }A\cap B \quad\Longleftrightarrow\quad \text{не в }A\text{ или не в }B.

Здесь «или» включает и отсутствие сразу в обоих. Если x∈A∩B‾x\in\overline{A\cap B}, то x∈Ux\in U и он отсутствует хотя бы в одном из A,BA,B; значит, x∈A‾∪B‾x\in\overline A\cup\overline B. Обратно, если x∈A‾∪B‾x\in\overline A\cup\overline B, то x∈Ux\in U и он отсутствует хотя бы в одном из A,BA,B, поэтому x∉A∩Bx\notin A\cap B и x∈A∩B‾x\in\overline{A\cap B}. Доказаны оба включения.

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

Та же «карта» с дополнениями, для U={1,…,6}U=\{1,\dots,6\}, A={1,2,3,4}A=\{1,2,3,4\}, B={3,4,5}B=\{3,4,5\}:

Область Элементы в AA? в BB? A∪B‾\overline{A\cup B} A‾∩B‾\overline A\cap\overline B A∩B‾\overline{A\cap B} A‾∪B‾\overline A\cup\overline B
только в AA 1, 2 да нет — — ✓ ✓
и в AA, и в BB 3, 4 да да — — — —
только в BB 5 нет да — — ✓ ✓
ни в AA, ни в BB 6 нет нет ✓ ✓ ✓ ✓

Столбцы A∪B‾\overline{A\cup B} и A‾∩B‾\overline A\cap\overline B совпадают в каждой строке — это первый закон де Моргана. Столбцы A∩B‾\overline{A\cap B} и A‾∪B‾\overline A\cup\overline B совпадают — это второй закон.

3. Проверка на одном примере

Пусть U={1,2,3,4,5,6}U=\{1,2,3,4,5,6\}, A={1,2,3,4}A=\{1,2,3,4\}, B={3,4,5}B=\{3,4,5\}. Тогда

A‾={5,6},B‾={1,2,6}.\overline A=\{5,6\},\qquad \overline B=\{1,2,6\}.

Для первого закона A∪B={1,2,3,4,5}A\cup B=\{1,2,3,4,5\}, и обе части дают {6}\{6\}:

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

Для второго A∩B={3,4}A\cap B=\{3,4\}, и обе части дают {1,2,5,6}\{1,2,5,6\}:

A∩B‾={1,2,5,6}=A‾∪B‾.\overline{A\cap B}=\{1,2,5,6\}=\overline A\cup\overline B.

Пример проверяет вычисление; доказательства выше объясняют, почему равенства верны для любых A,B⊆UA,B\subseteq U.

Проверь себя

1. Пусть U={1,2,…,8}U=\{1,2,\dots,8\}, A={2,4,6,8}A=\{2,4,6,8\}, B={1,2,3,4}B=\{1,2,3,4\}. Найдите A∪B‾\overline{A\cup B} и A‾∩B‾\overline A\cap\overline B.

Решение

A∪B={1,2,3,4,6,8}A\cup B=\{1,2,3,4,6,8\}, поэтому A∪B‾={5,7}\overline{A\cup B}=\{5,7\}. Дополнения: A‾={1,3,5,7}\overline A=\{1,3,5,7\}, B‾={5,6,7,8}\overline B=\{5,6,7,8\}; их пересечение A‾∩B‾={5,7}\overline A\cap\overline B=\{5,7\}. Результаты равны.

2. Запишите словами, что значит x∈A∩B‾x\in\overline{A\cap B}.

Решение

Элемент не принадлежит пересечению, то есть не лежит сразу в обоих множествах: он отсутствует хотя бы в одном из них. Поэтому x∈A‾∪B‾x\in\overline A\cup\overline B — второй закон де Моргана.

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