Математическая логика, теория множеств.

[Tosha]

Как доказать ,что $(A\cup B)\cap C=(A\cap B)\cup (A\cap C)$

Можно ли рисование через круги Эйлера считать доказательством?

[FFMiKN]

Здравствуйте. Нам разрешалось рисовать кругами Эйлера, если не получалось аналитически доказать.
Но лучше все же уметь аналитически доказать.
Доказать можно рассматривая какой-нибудь произвольный элемент принадлежащий множеству и строя рассуждения исходя из определений указанных вами операций.

[arseniiv]

Tosha в сообщении #772450 писал(а):

Как доказать ,что $(A\cup B)\cap C=(A\cap B)\cup (A\cap C)$

Никак. Увы, это неверно. Надо поменять буквы немного.

[Denis Russkih]

Я сам ещё не волшебник, а только учусь. :) Но по-моему, решается как-то так:

$\begin{array}{l} x \in ((A \cup B) \cap C) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, x \in (A \cup B) \wedge x \in C \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (x \in A \vee x \in B) \wedge x \in C \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (x \in A \wedge x \in C) \vee (x \in B \wedge x \in C) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, x \in (A \cap C) \vee x \in (B \cap C) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, x \in ((A \cap C) \cup (B \cap C)) \,\Rightarrow\, \\ \,\Rightarrow\, ((A \cup B) \cap C = (A \cap C) \cup (B \cap C)) \end{array}$

Обратите внимание, что мы получаем совсем другой результат. То утверждение, которое приведено в первом посте темы, попросту неверно.

FFMiKN в сообщении #772454 писал(а):

Доказать можно рассматривая какой-нибудь произвольный элемент принадлежащий множеству и строя рассуждения исходя из определений указанных вами операций.

Наверное, я очень тупой, но я ни за что не смог бы извлечь из этой фразы, что конкретно нужно делать. :) Точнее, у меня в голове возникло бы вариантов десять различных толкований.

Лично мне кажется, что лучше один раз нормально показать человеку, как всё надо записывать и т.д. Вот если он будет приходить снова и снова с однотипными задачками, не пытаясь в них вникнуть — тогда уже можно напускать туману и склонять к самостоятельному шевелению мозгами. :)

[FFMiKN]

(Оффтоп)

Denis Russkih в сообщении #772485 писал(а):

Точнее, у меня в голове возникло бы вариантов десять различных толкований.

Лично мне кажется, что лучше один раз нормально показать человеку, как всё надо записывать и т.д. Вот если он будет приходить снова и снова с однотипными задачками, не пытаясь в них вникнуть — тогда уже можно напускать туману и склонять к самостоятельному шевелению мозгами. :)

Да, Вы правы, пожалуй.)

[Tosha]

Denis Russkih в сообщении #772485 писал(а):

Я сам ещё не волшебник, а только учусь. :) Но по-моему, решается как-то так:

$\begin{array}{l} x \in ((A \cup B) \cap C) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, x \in (A \cup B) \wedge x \in C \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (x \in A \vee x \in B) \wedge x \in C \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (x \in A \wedge x \in C) \vee (x \in B \wedge x \in C) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, x \in (A \cap C) \vee x \in (B \cap C) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, x \in ((A \cap C) \cup (B \cap C)) \,\Rightarrow\, \\ \,\Rightarrow\, ((A \cup B) \cap C = (A \cap C) \cup (B \cap C)) \end{array}$

Спасибо! А вот этот переход подразумевается очевидным? Я вот его не понимаю( Что тут именно произошло?

$\begin{array}{l} (x \in A \vee x \in B) \wedge x \in C \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (x \in A \wedge x \in C) \vee (x \in B \wedge x \in C) \end{array}$

[arseniiv]

Тут произошла дистрибутивность $\wedge$ относительно $\vee$: $(a\vee b)\wedge c \Leftrightarrow a\wedge c\vee b\wedge c$.

[Tosha]

arseniiv в сообщении #772582 писал(а):

Тут произошла дистрибутивность $\wedge$ относительно $\vee$: $(a\vee b)\wedge c \Leftrightarrow a\wedge c\vee b\wedge c$.

То есть это свойство такое, которое невозможно доказать?

[arseniiv]

Нет, его обычно доказывают (или говорят, что оно доказывается). Раньше, чем доходят до множеств, правда, так что сейчас вам его доказывать точно незачем, хотя знать о нём стоит.

[VAL]

Tosha в сообщении #772450 писал(а):

Можно ли рисование через круги Эйлера считать доказательством?

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

Но нарисовать $n$ кругов, так чтобы они разбили плоскость на $2^n$ областей при $n>3$ не получится. А без представленности всех $2^n$ возможных случаев принадлежности элемента рассматриваемым множествам не будет и доказательства.

PS: Разве что кляксы какие-нибудь использовать.
PPS: Многомерные шары не предлагаю.

[Aritaborian]

VAL в сообщении #772707 писал(а):

Разве что кляксы какие-нибудь использовать.

Без клякс никак. Рекорд, если не ошибаюсь, на данный момент составляет $n=11$.

[Denis Russkih]

Tosha в сообщении #772589 писал(а):

arseniiv в сообщении #772582 писал(а):

Тут произошла дистрибутивность $\wedge$ относительно $\vee$: $(a\vee b)\wedge c \Leftrightarrow a\wedge c\vee b\wedge c$.

То есть это свойство такое, которое невозможно доказать?

Можно показать при помощи таблицы истинности. :)

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline a & b & c & a \vee b & (a \vee b) \wedge c & a \wedge c & b \wedge c & (a \wedge c) \vee (b \wedge c) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array}$

Как видите, соответствующие столбцы совпадают. Значит, $(a \vee b) \wedge c \,\Leftrightarrow\, (a \wedge c) \vee (b \wedge c)$.

Поскольку $\wedge$ имеет больший приоритет, чем $\vee$, то можно записать без скобочек:

$(a \vee b) \wedge c \,\Leftrightarrow\, a \wedge c \vee b \wedge c$


Аналогичным образом можно проверить и другие интересные штуки. :) Вот самый минимум, который полезно знать:

$\begin{array}{l} \neg \neg A \,\Leftrightarrow\, A \\ A \wedge B \,\Leftrightarrow\, B \wedge A \\ A \vee B \,\Leftrightarrow\, B \vee A \\ A \wedge (B \wedge C) \,\Leftrightarrow\, (A \wedge B) \wedge C \\ A \vee (B \vee C) \,\Leftrightarrow\, (A \vee B) \vee C \\ A \wedge (B \vee C) \,\Leftrightarrow\, (A \wedge B) \vee (A \wedge C) \\ A \vee (B \wedge C) \,\Leftrightarrow\, (A \vee B) \wedge (A \vee C) \\ A \wedge A \,\Leftrightarrow\, A \\ A \vee A \,\Leftrightarrow\, A \\ \neg A \vee A \,\Leftrightarrow\, True \\ \neg A \wedge A \,\Leftrightarrow\, False \\ \neg (A \wedge B) \,\Leftrightarrow\, \neg A \vee \neg B \\ \neg (A \vee B) \,\Leftrightarrow\, \neg A \wedge \neg B \\ (A \Rightarrow B) \,\Leftrightarrow\, \neg A \vee B \\ \neg (A \Rightarrow B) \,\Leftrightarrow\, A \wedge \neg B \\ (A \Rightarrow B) \,\Leftrightarrow\, (\neg B \Rightarrow \neg A) \\ A \wedge B \,\Leftrightarrow\, A \wedge (A \Rightarrow B) \end{array}$

Очередность логических операций:

$\neg \, \wedge \, \vee \, \Rightarrow \,\, \Leftrightarrow$

(Чтобы не писать лишние скобки. Хотя лично мне нравится их использовать, с ними всё выглядит гораздо яснее.)

[Joker_vD]

(Оффтоп)

VAL в сообщении #772707 писал(а):

PS: Разве что кляксы какие-нибудь использовать.

Ну, зачем же. Кэррол в своей "Символической логике", в параграфе 7 "Мой метод диаграмм" (идет после параграфов "Метод кругов Эйлера" и "Метод диаграмм Венна" замечания для преподавателей рисует довольно симпатичные квадратные диаграммы для $n\leqslant 10$. Вообще, довольно интересная работа — "метод индексов" до боли напоминает правило резолюций Робинсона, но последнее было разработано-то лишь в 1965.

[Tosha]

Denis Russkih, спасибо огромнейшее, все понял!

[Sonic86]

Хочу добавить, что есть еще метод характеристических функций, он в определенном смысле посильнее (в отличие от метода "$x\in M\Leftrightarrow ...$"), а с другой стороны удобнее для доказательства, но при этом о нем обычно не упоминают.
Т.е. $X=Y\Leftrightarrow \chi_X(t)=\chi_Y(t)$, а далее используются простые свойства: $\chi_{X\wedge Y}(t)=\chi_X(t) \chi_Y(t), \chi_{\bar X}(t)=1-\chi_X(t), \chi^2_X(t)=\chi_X(t)$. Характеристические функции - обычные многочлены.
В данном случае достаточно вычислить $\chi$ от правой и от левой части. Потом просто проверить, получается тождество или нет.