свойства операций над множествами

Равенство множеств доказывают через принадлежность произвольного элемента, а ложный закон опровергают одним контрпримером.

таблица законов

Законы действуют для любых $A,B,C\subseteq U$. Каждый имеет парную форму для $\cup$ и $\cap$.

ещё четыре опоры

$A\cup A=A$, $A\cap A=A$, $A\cup\overline A=U$, $A\cap\overline A=\varnothing$.

доказательство по элементам

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

два включения в законе де моргана

условие: Доказать $\overline{A\cup B}=\overline A\cap\overline B$.

ход решения

1. Включение $\subseteq$: пусть $x\in\overline{A\cup B}$. Тогда $x\notin A$ и $x\notin B$, значит, $x\in\overline A\cap\overline B$.

2. Получили $\overline{A\cup B}\subseteq\overline A\cap\overline B$.

3. Обратное включение $\supseteq$: пусть $x\in\overline A\cap\overline B$. Тогда $x\notin A$ и $x\notin B$, следовательно, $x\notin A\cup B$ и $x\in\overline{A\cup B}$.

4. Получили $\overline A\cap\overline B\subseteq\overline{A\cup B}$, то есть нужное включение в обратную сторону.

ответ: Два взаимных включения дают $\overline{A\cup B}=\overline A\cap\overline B$.

проверка: Обе части описывают область вне $A$ и вне $B$.

контрпример и упрощение

Похожая на числовую алгебру запись может быть ложной, поэтому её проверяют законами или по элементам.

опровергаем ложный закон

условие: Верно ли $A\setminus(B\cup C)=(A\setminus B)\cup(A\setminus C)$?

ход решения

1. Берём $A=\{1,2\}$, $B=\{1\}$, $C=\{2\}$

2. Слева получаем $\varnothing$

3. Справа получаем $\{2\}\cup\{1\}=\{1,2\}$

ответ: Неверно.

проверка: Верно: $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$.

$$(A\cup B)\cap(A\cup\overline B)=A\cup(B\cap\overline B)=A$$

что запомнить

• Коммутативность меняет операнды, ассоциативность — скобки.

• Есть два дистрибутивных закона.

• В законе де Моргана дополнение меняет $\cup$ на $\cap$.

• Для доказательства берут любой $x$; для опровержения хватает одного примера.

самопроверка

• Какой закон перегруппировывает $(A\cap B)\cap C$?

• Запишите оба закона поглощения.

• Как доказать равенство множеств по элементам?

• Приведите контрпример к $A\cup B=A\cap B$.

источники

• материал занятия: фотографии конспекта, страницы 84–87 — /materials/notes/discrete_math/photo_84@20-09-2026_10-16-53.jpg

• редакционная сверка: Discrete Mathematics: An Open Introduction — Sets — https://discrete.openmathbooks.org/dmoi2/sec_intro-sets.html