Поделиться
Как доказать равенство множеств
Опубликовал Wikimatik , 8 Января 2017 по предмету "Дискретная математика"

Очень часто в задачах по дискретной математике, а именно в теории множеств, требуется доказать равенство множеств. Напомним, что равенство множеств $M=N$ означает выполнение взаимного включения, то есть $M\subseteq N$ и $N\subseteq M$. Следовательно, для доказательства равенства $M=N$ множеств $M,\ N$ нужно показать выполнение этих включений. Делать это можно различными способами:

  1. по определению теоретико-множественных операций;
  2. с помощью законов алгебры множеств;
  3. построением диаграмм Эйлера-Венна;
  4. построением таблиц принадлежности;
  5. используя индикаторные функции.

Продемонстрируем каждый из этих способов на конкретном примере.

Доказать равенство множеств:

$$\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$$

1. Равенство двух множеств $M=N$ эквивалентно двум включениям $M\subseteq N,\ N\subseteq M$.

Докажем, что $\left(A\cap B\right)\backslash C\subseteq \left(A\backslash C\right)\cap \left(B\backslash C\right)$. Пусть $x\in \left(A\cap B\right)\backslash C$, тогда по определению разности множеств $x\in \left(A\cap B\right)$ и $x\notin C$. По определению пересечения множеств $x\in \left(A\cap B\right)$ тогда и только тогда, когда $x\in A$ и $x\in B$. Так как $x\in A$ и $x\notin C$, то $x\in A\backslash C$. Так как $x\in B$ и $x\notin C$, то $x\in B\backslash C$. По определению пересечения получаем, что $x\in \left(A\backslash C\right)\cap \left(B\backslash C\right)$. Что доказывает то, что $\left(A\cap B\right)\backslash C\subseteq \left(A\backslash C\right)\cap \left(B\backslash C\right)$.

Докажем, что $\left(A\backslash C\right)\cap \left(B\backslash C\right)\subseteq \left(A\cap B\right)\backslash C$. Пусть $x\in \left(A\backslash C\right)\cap \left(B\backslash C\right)$, тогда по определению пересечения множеств $x\in \left(A\backslash C\right)$ и $x\in \left(B\backslash C\right)$. По определению разности множеств $x\in A$, $x\notin C$ и $x\in B,\ x\notin C$. По определению пересечения получаем, что $x\in \left(A\cap B\right)\ и\ x\notin C$, то есть $x\in \left(A\cap B\right)\backslash C$. Что доказывает то, что $\left(A\backslash C\right)\cap \left(B\backslash C\right)\subseteq \left(A\cap B\right)\backslash C$. Из доказанных включений следует, что $A\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$.

2. Докажем справедливость соотношения $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$, используя основные законы алгебры множеств.

Операцию разность $X\backslash Y$ произвольных множеств $X,\ Y$ можно записать, как $X\backslash Y=X\cap \overline{Y}$. Тогда для левой части данного соотношения $\left(A\cap B\right)\backslash C=A\cap B\cap \overline{C}$. Для правой части: $\left(A\backslash C\right)\cap \left(B\backslash C\right)=A\cap \overline{C}\cap B\cap \overline{C}=A\cap B\cap \overline{C}$. Видим, что левая и правая части в результате преобразований совпали $A\cap B\cap \overline{C}=A\cap B\cap \overline{C}$. Соотношение верно.

3. Видим, что диаграммы множеств $\left(A\cap B\right)\backslash C$ и $\left(A\backslash C\right)\cap \left(B\backslash C\right)$ полностью совпадают, значит, равенство $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$ верно.

4. Построим таблицу принадлежности для левой и правой частей данного равенства $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$.

\begin{array}{|c|c|} \hline  A & B & C & A\cap B & \left(A\cap B\right)\backslash C & A\backslash C & B\backslash C & \left(A\backslash C\right)\cap \left(B\backslash C\right) \\ \hline  0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline  0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline  0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \hline  0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline  1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \hline  1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline  1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline  1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline \end{array}

Видим, что $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)=\left(00000010\right)$.

5. Докажем справедливость соотношения $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$ с помощью индикаторных функций. Индикаторная функция для левой части соотношения:

$$\ {\chi }_{\left(A\cap B\right)\backslash C}\left(x\right)={\chi }_{A\cap B}\left(x\right)-{\chi }_{A\cap B}\left(x\right){\chi }_C\left(x\right)={\chi }_A\left(x\right){\chi }_B\left(x\right)-{\chi }_A\left(x\right){\chi }_B\left(x\right){\chi }_C\left(x\right)={\chi }_A\left(x\right){\chi }_B\left(x\right)\cdot \left(1-{\chi }_C\left(x\right)\right)$$ Индикаторная функция для правой части:  $${\chi }_{\left(A\backslash C\right)\cap \left(B\backslash C\right)}\left(x\right)={\chi }_{\left(A\backslash C\right)}\left(x\right){\chi }_{\left(B\backslash C\right)}\left(x\right)=\left({\chi }_A\left(x\right)-{\chi }_A\left(x\right){\chi }_C\left(x\right)\right)\left({\chi }_B\left(x\right)-{\chi }_B\left(x\right){\chi }_C\left(x\right)\right)={\chi }_A\left(x\right){\chi }_B\left(x\right)-{\chi }_A\left(x\right){\chi }_B\left(x\right){\chi }_C\left(x\right)-{\chi }_A\left(x\right){\chi }_B\left(x\right){\chi }_C\left(x\right)+{\chi }_A\left(x\right){\chi }_B\left(x\right){\chi }_C\left(x\right)={\chi }_A\left(x\right){\chi }_B\left(x\right)-{\chi }_A\left(x\right){\chi }_B\left(x\right){\chi }_C\left(x\right)={\chi }_A\left(x\right){\chi }_B\left(x\right)\left(1-{\chi }_C\left(x\right)\right). $$  Видим, что индикаторные функции обеих частей совпали  $${\chi }_A\left(x\right){\chi }_B\left(x\right)\cdot \left(1-{\chi }_C\left(x\right)\right)={\chi }_A\left(x\right){\chi }_B\left(x\right)\cdot \left(1-{\chi }_C\left(x\right)\right).$$  Соотношение верно.

Данная статья полезна?
×