Доказать равенство множеств – Как доказать равенство множеств. Пример решения задачи на Викиматик

Как доказать равенство множеств. Пример решения задачи на Викиматик

Очень часто в задачах по дискретной математике, а именно в теории множеств, требуется доказать равенство множеств. Напомним, что равенство множеств $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).$$  Соотношение верно.

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

Да Нет

wikimatik.ru

Как доказывать равенство множеств?

Многие математические утверждения, в том числе и многие теоремы в этой книге, имеют следующую форму. Даны разные определения двух множеств A и B. Требуется доказать, что A = B.

Стандартный способ доказательства такого утверждения состоит в доказательстве двух утверждений о включениях:

1. и

2.

Доказательства этих включений проводятся по такой схеме: рассматривается произвольный элемент, удовлетворяющий определению меньшего

множества (слева от знака ), и устанавливается, что он удовлетворяет также определению большего множества (справа от знака ).

В качестве примера докажем одно из свойств (законов) дистрибутивности для операций объединения и пересечения:

1. Пусть a — произвольный элемент из Тогда по определению операции имеем или В первом случае из того же определения выводим, что и Но тогда по определению операции получаем, что Во втором случае из определения следует, что и Из этого и из определения снова следует, что и и Таким образом, мы установили, что

2. Пусть теперь Тогда по определению операции имеем и Если то оба эти включения выполнены. Но тогда Если же то из первого включения следует, что а из второго — Следовательно, и Таким образом, и наше утверждение доказано.

Используя эту же схему, можно установить много других свойств введенных выше операций над множествами и связей между ними.

 

Похожие статьи:

poznayka.org

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

Доказать равенство множеств (11,12 задания)

Прикрепленные файлы:

Поступил ответ 8 Апреля 2017 от Викиматика

$\overline{A\cup B}\times C=\left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right).$

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

1) Покажем выполнение включения $\overline{A\cup B}\times C\subseteq \left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)$. Пусть $\left(x,\ y\right)\in \overline{A\cup B}\times C$, тогда по определению декартова произведения $x\in \overline{A\cup B}$, $y\in C$. Отсюда $x\notin A\cup B$, $y\in C\Rightarrow x\notin A$ и $x\notin B$, $y\in C\Rightarrow x\in \overline{A}$ и $x\in \overline{B}$, $y\in C$. Если $x\in \overline{A},\ y\in C$, то $\left(x,\ y\right)\in \overline{A}\times C$, а если $x\in \overline{B},\ y\in C$, то $\left(x,\ y\right)\in \overline{B}\times C$. Итак, $\left(x,\ y\right)\in \overline{A}\times C$ и $\left(x,\ y\right)\in \overline{B}\times C$. По определению операции пресечения получаем, что $\left(x,\ y\right)\in \left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)$. Что доказывает то, что $\overline{A\cup B}\times C\subseteq \left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)$.

2) Покажем выполнение включения $\left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)\subseteq \overline{A\cup B}\times C$. Пусть $\left(x,\ y\right)\in \left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)$, тогда по определению операции пресечения $\left(x,\ y\right)\in \overline{A}\times C$ и $\left(x,\ y\right)\in \overline{B}\times C$. Отсюда (по определению декартова произведения) $x\in \overline{A},\ y\in C$ и $x\in \overline{B},\ y\in C$ $\Rightarrow x\notin \overline{A}$ и $x\notin B$, $y\in C$. Если $x\notin \overline{A}$ и $x\notin B$, то $x\notin A\cup B\Rightarrow x\in \overline{A\cup B}$. Получаем, что $x\in \overline{A\cup B}$, $y\in C$, следовательно, $\left(x,\ y\right)\in \overline{A\cup B}\times C$. Что доказывает то, что $\left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)\subseteq \overline{A\cup B}\times C$.

Из доказанных включений следует равенство $\overline{A\cup B}\times C=\left(\overline{A}\times C\right)\cap \left(\overline{B}\times C\right)$.

Равенство $B\cap \left(\overline{A}\triangle \left(A\cap C\right)\right)=B\cap \left(\overline{A}\cup C\right)$ можно доказать, используя законы и равносильности алгебры множеств. Операцию «симметрическая разность» $X\triangle Y$ произвольных множеств $X$ и $Y$ можно записать следующим образом:

$$X\triangle Y=\overline{X}Y\cup X\overline{Y}.$$ 

Знак операции пересечения $\cap $ для удобства будем опускать, заменяя его обычным умножениям. Тогда для левой части равенства имеем:

$B\cap \left(\overline{A}\triangle \left(A\cap C\right)\right)=B\left(\overline{\overline{A}}AC\cup \overline{A}\ \overline{A\cap C}\right)=$ $\{$по закону двойного отрицания $\overline{\overline{A}}=A$, а по закону де Моргана $\overline{A\cap C}=\overline{A}\cup \overline{C}$$\}$ $=B\left(AC\cup \overline{A}\underbrace{\left(\overline{A}\cup \overline{C}\right)}_{поглощается\ \overline{A}}\right)=B\left(AC\cup \overline{A}\right)=$ $\{$используем дистрибутивный закон объединения относительно пересечения $X\cup YZ=\left(X\cup Y\right)\left(X\cup Z\right)$$\}$ $=B\left(\overline{A}\cup A\right)\left(\overline{A}\cup C\right)=$ $\{$по закону исключения третьего $\overline{A}\cup A=U$$\}$ $=B\left(\overline{A}\cup C\right)$.

wikimatik.ru

Помогите решить / разобраться (М)

Хочу высказаться еще раз вот по такой теме, хоть со мной наверное большинство участвовавших в обсуждении и не согласятся. Я думаю, что для решения задач по элементарной теории множеств лучше пользоваться естественным языком, а не символами из матлогики , , . Оно как-то гораздо органичнее.

Вот например. В прошлой теме надо было доказать эквивалентность утверждений и . На естественном языке можно было написать так.
«Допустим, . Тогда любой элемент из лежит в , а потому он лежит в обоих и , т.е. лежит в пересечении . С другой стороны, любой элемент из лежит в . Значит, множества и состоят из одних и тех же элементов, т.е. . Обратно, допустим, что . Поскольку для любых множеств и пересечение — подмножество в , то ввиду равенства получаем, что . Итак, соотношения и эквивалентны.»
Мне кажется, так гораздо яснее и проще.

Если открыть любую книгу или статью, можно увидеть, что математики пользуются не матлогикой и символами из нее, а обыкновенной логикой и обыкновенным языком. А писать все символами — это только самому себе мешать думать, а читателю понимать. gogoshik, попробуйте рассуждать (и главное, думать!) обычным образом — и сразу многое прояснится. Вы увидите, что все эти задачи очень просты, практически тривиальны.
Такое, в общем, у меня мнение…

dxdy.ru

No related posts.