Задача. Кострикин 1.5

[Alexander__]

Здравствуйте!

Условие задачи: какое максимальное число подмножеств можно бразовать из данных n помножеств фиксированного множества с помощью операций пересечения, объединения и дополнения?

Насколько я понял, на количество применений операций ограничений не накладывается. Поэтому максимальное число подмножеств зависит не от n, а от количества элементов фиксированного, которые с их помощью возможно получить (понятно, что можно получить не все элементы). Если можно получить k элементов, то число возможных подмножеств равно 2^k.

Пожалуйста, помогите понять условие задачи.

[SpBTimes]

Так $2^n$ и можете. Разность у вас ведь тоже есть.

[Alexander__]

Видимо, я не до конца понимаю.

Пусть есть множество $\{1,2,3,4\}$. Даны $n=3$ его подмножеств: $\{1,2,3\}, \{3\}, \{1,2\}$. Из этих подмножеств можно дополнительно получить только пустое подмножество. Всего 4 множества получилось потому, что "атомарных" подмножеств (т.е. таких, которые не разбиваются на подмножества) среди исходных подмножеств всего 2. Поэтому ответ $2^2$, а не $2^3$. Или как-то еще можно получить еще 4 подмножества?

[Nimza]

Alexander__ в сообщении #699104 писал(а):

Из этих подмножеств можно дополнительно получить только пустое подмножество.

Почему только пустое? Вы же можете взять дополнение к $\{1,2,3\}$, например.

[VAL]

SpBTimes в сообщении #696720 писал(а):

Так $2^n$ и можете. Разность у вас ведь тоже есть.

Не $2^n$, а $2^{2^n}$.

[Alexander__]

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

SpBTimes в сообщении #696720 писал(а):

Так $2^n$ и можете. Разность у вас ведь тоже есть.

Не $2^n$, а $2^{2^n}$.

Если каждое подмножество соответствует каждому элементу исходного множества, то по-вашему можно получить $2^{2^n}$ подмножеств, когда у множества всего $2^n$ подмножеств?

[VAL]

Alexander__ в сообщении #699933 писал(а):

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

SpBTimes в сообщении #696720 писал(а):

Так $2^n$ и можете. Разность у вас ведь тоже есть.

Не $2^n$, а $2^{2^n}$.

Если каждое подмножество соответствует каждому элементу исходного множества, то по-вашему можно получить $2^{2^n}$ подмножеств, когда у множества всего $2^n$ подмножеств?

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

-- 22 мар 2013, 18:29 --

Прокомментирую.
Возьмем $n=2$. Нарисуйте диаграмму Эйлера из двух пересекающихся кругов. Картинка разобьет плоскость на 4 части (это уже $2^n$). А вот эти части уже можно отождествить с элементами.

Я тут недавно уже проводил параллель между этой задачкой и подсчетом количества классов эквивалентных формул исчисления высказываний, если используется $n$ высказывательных букв. Только обратите внимание: аналог элементарных высказываний - это не наши множества, а утверждения типа $x \in A$.

[Alexander__]

VAL,

благодарю вас за подсказку про формулы исчисления высказываний. Я правильно вас понимаю, что вы говорите об аналогии с СДНФ? Тогда действительно число всевозможных конъюнкций $2^n$; и число всевозможных дизъюнкций равно $2^{2^n}$. Верно?

Подскажите как устроено такое множество, для которого все СДНФ различны?

[AV_77]

Alexander__ в сообщении #703236 писал(а):

Подскажите как устроено такое множество, для которого все СДНФ различны?

Например, для $n = 2$. Пусть $A = \{ 1, 2, 3, 4 \}$. Положим $X_1 = \{ 1, 2 \}$ и $X_2 = \{ 1, 3 \}$. Тогда $X_1 \cap X_2 = \{ 1 \}$, $X_1 \cap \bar X_2 = \{ 2 \}$, $\bar X_1 \cap X_2 = \{ 3 \}$, $\bar X_1 \cap \bar X_2 = \{ 4 \}$.