2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Математическая логика, теория множеств.
Сообщение08.10.2013, 14:22 
Как доказать ,что $(A\cup B)\cap C=(A\cap B)\cup (A\cap C)$

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

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 14:32 
Tosha в сообщении #772450 писал(а):
Как доказать ,что $(A\cup B)\cap C=(A\cap B)\cup (A\cap C)$
Никак. Увы, это неверно. Надо поменять буквы немного.

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 15:13 
Аватара пользователя
Я сам ещё не волшебник, а только учусь. :) Но по-моему, решается как-то так:

$\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 писал(а):
Доказать можно рассматривая какой-нибудь произвольный элемент принадлежащий множеству и строя рассуждения исходя из определений указанных вами операций.

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

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 16:44 
Аватара пользователя

(Оффтоп)

Denis Russkih в сообщении #772485 писал(а):
Точнее, у меня в голове возникло бы вариантов десять различных толкований.

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

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 18:22 
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}$

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 18:38 
Тут произошла дистрибутивность $\wedge$ относительно $\vee$: $(a\vee b)\wedge c \Leftrightarrow a\wedge c\vee b\wedge c$.

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 18:45 
arseniiv в сообщении #772582 писал(а):
Тут произошла дистрибутивность $\wedge$ относительно $\vee$: $(a\vee b)\wedge c \Leftrightarrow a\wedge c\vee b\wedge c$.

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

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 21:52 
Tosha в сообщении #772450 писал(а):
Можно ли рисование через круги Эйлера считать доказательством?
Если в доказываемом соотношении участвует не более трех различных множеств (и взаимное расположение кругов правильное), то можно.

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

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 21:56 
Аватара пользователя
VAL в сообщении #772707 писал(а):
Разве что кляксы какие-нибудь использовать.
Без клякс никак. Рекорд, если не ошибаюсь, на данный момент составляет $n=11$.

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 22:16 
Аватара пользователя
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$

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение08.10.2013, 23:03 

(Оффтоп)

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

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

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение09.10.2013, 12:01 
Denis Russkih, спасибо огромнейшее, все понял!

 
 
 
 Re: Математическая логика, теория множеств.
Сообщение09.10.2013, 17:19 
Хочу добавить, что есть еще метод характеристических функций, он в определенном смысле посильнее (в отличие от метода "$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$ от правой и от левой части. Потом просто проверить, получается тождество или нет.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group