парочка задач по теории множеств

[BapuK]

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$ - множества, для которых это равенство неверно... А вот следующий шаг непонятен.
Ко второй задаче даже не знаю с какой стороны подступиться...
Натолкните на мысль

[Профессор Снэйп]

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$?

[BapuK]

Профессор Снэйп в сообщении #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$ множеств найти это число.
А по первой задачке спасибо за наводку

[gris]

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

[BapuK]

благодарю за помощч! :)

[chepiov]

Всем привет :)

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

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

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

[Профессор Снэйп]

chepiov в сообщении #578039 писал(а):

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

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