2014 dxdy logo

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

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




 
 парочка задач по теории множеств
Сообщение15.09.2010, 14:06 
Аватара пользователя
1) Докажите, что если какое-то равенство, содержащее переменные для множеств и операции $\cap, \cup$ и \ неверно, то можно найти контрпример к нему в котором множества пусты или состоят из одного элемента.
2) Сколько различных выражений для 2-ух множеств можно составить с помощью многократно используемых операций пересечения, объединения и разности. Тот же вопрос для $n$ множеств.

В первой задаче догадываюсь про начало доказательства: Пусть $t_1(A_1, \dots, A_n) = t_2(A_1, \dots, A_n)$ - некоторое равенство, и пусть $B_1,\dots, B_n$ - множества, для которых это равенство неверно... А вот следующий шаг непонятен.
Ко второй задаче даже не знаю с какой стороны подступиться...
Натолкните на мысль :oops:

 
 
 
 Re: парочка задач по теории множеств
Сообщение15.09.2010, 15:17 
Аватара пользователя
BapuK в сообщении #352698 писал(а):
В первой задаче догадываюсь про начало доказательства: Пусть $t_1(A_1, \dots, A_n) = t_2(A_1, \dots, A_n)$ - некоторое равенство, и пусть $B_1,\dots, B_n$ - множества, для которых это равенство неверно... А вот следующий шаг непонятен.

Выберите $b \in B_1 \cup \ldots \cup B_n$, принадлежащий одной части равенства и не принадлежащий другой. Затем убедитесь, что равенство не выполнено для $B_1', \ldots, B_n'$, где $B_i' = B_i \cap \{ b \}$.

-- Ср сен 15, 2010 19:22:02 --

BapuK в сообщении #352698 писал(а):
2) Сколько различных выражений для 2-ух множеств можно составить с помощью многократно используемых операций пересечения, объединения и разности. Тот же вопрос для множеств.

Какова минимальная подалгебра булевой алгебры $\mathcal{P}(B_1 \cup B_2)$, содержащая множества $B_1$ и $B_2$?

 
 
 
 Re: парочка задач по теории множеств
Сообщение16.09.2010, 04:48 
Аватара пользователя
Профессор Снэйп в сообщении #352720 писал(а):
BapuK в сообщении #352698 писал(а):
2) Сколько различных выражений для 2-ух множеств можно составить с помощью многократно используемых операций пересечения, объединения и разности. Тот же вопрос для множеств.

Какова минимальная подалгебра булевой алгебры $\mathcal{P}(B_1 \cup B_2)$, содержащая множества $B_1$ и $B_2$?

Ну для двух множеств я подсчитал, довольно таки легко увидеть, что всего элементов 8:
$1)\varnothing = A\backslash A$
$2)A$
$3)B$
$4)A\cup B$
$5)A\cap B$
$6)(A\cup B)\backslash A$
$7)(A\cup B) \backslash B$
$8) (A\cup B) \backslash (A\cap B)$
Т.е. непонятно как для $n$ множеств найти это число.
А по первой задачке спасибо за наводку

 
 
 
 Re: парочка задач по теории множеств
Сообщение16.09.2010, 07:57 
Аватара пользователя
По второй задаче: наглядно это видно на диаграммах Венна. Для двух множеств мы имеем ровно три непересекающихся "элементарных" множества, из которых с помощью наших операций можем формировать множества-ответы. Надо только показать, что ничего другого мы получить не можем. Из трёх непересекающихся множеств мы можем составить $2^3=8$ комбинаций.
Три множества в общем случае дают 7 таких "элементарных" множеств.
Ну и обобщаем.

 
 
 
 Re: парочка задач по теории множеств
Сообщение16.09.2010, 13:18 
Аватара пользователя
благодарю за помощч! :)

 
 
 
 Re: парочка задач по теории множеств
Сообщение29.05.2012, 17:54 
Аватара пользователя
Всем привет :)

Хоть уже столько времени прошло, может кто и ответит.

Вот хоть убей, не могу сделать первую задачу :(

Подскажите направление чуть более разжёванно пожалуйста.

 
 
 
 Re: парочка задач по теории множеств
Сообщение30.05.2012, 04:22 
Аватара пользователя
chepiov в сообщении #578039 писал(а):
Вот хоть убей, не могу сделать первую задачу :(

Индукция по длине равенства плюс указание из второго сообщения темы.

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


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