Тождества алгебры множеств

[eugensk]

Справедливы тождества:

\align{A \cup A = A \cap A}

\align{(A \cup B) \cap (B \cup C) \cap (C \cup A) = (A \cap B) \cup (B \cap C) \cup (C \cap A)}

Есть ли еще выражения, содержащие только буквы для множеств и операции $\cup$ и $\cap$,
которые не меняются от замены $\cup$ на $\cap$ и наоборот?

[arseniiv]

Поглощение: $A\cup(A\cap B) = A = A\cap(A\cup B)$. Как перечислить все, не думал.

[eugensk]

Спасибо! Я его прошляпил :)
Удастся ли найти еще какое-нибудь, кроме этих трёх?

[arseniiv]

Видно, что эти выражения представляют самодвойственные булевы функции — такие, что $\neg f(\neg x_1,\ldots,\neg x_n) = f(x_1,\ldots,x_n)$, хотя, конечно, не обязательно все возможные (отрицания/дополнения-то не входят). Набор значений такой функции для значений аргументов, равных двоичным записям последовательных натуральных чисел, при обращении порядка обращается, что позволяет перечислить все такие функции моментально (но, конечно, не все соответствующие им выражения, а тем более содержащие только $\cup$ и $\cap$): например, функции двух переменных имеют наборы значений 0011, 0101, 1010 и 1100 — это отрицание первого аргумента, второй, отрицание второго и первый, притом отрицания мы не можем представить, а остальные имеют много представлений кроме простого атома: упомянутая вами первая пара, моя пара, всякие скучные конструкции из них.

eugensk в сообщении #1286485 писал(а):

Удастся ли найти еще какое-нибудь, кроме этих трёх?

А ваше второе не обобщается на произвольное количество переменных?

[eugensk]

eugensk в сообщении #1286489 писал(а):

всякие скучные конструкции из них.

Я не сообразил про подстановки, то есть с тремя переменными A,B,C сколько угодно выражений.

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

А ваше второе не обобщается на произвольное количество переменных?

Нет, контрпример это $A$ пересекает $B$, $C$ пересекает $D$, $A \cup B$ не пересекает $C \cup D$

Остаётся вопрос, есть ли вообще такие выражения с 4-мя и больше переменными?

[arseniiv]

Пусть $\binom Ak$ обозначает множество подмножеств $A$ мощности $k$, и пусть $[n)$ — какое-нибудь $n$-элементное множество. Тогда

$$\bigcup_{S\in\binom{[2n-1)}n} \bigcap_{a\in S} a = \bigcap_{S\in\binom{[2n-1)}n} \bigcup_{a\in S} a.$$

[eugensk]

Здорово! Попробую проверить для 5-ти букв

$a_1a_2a_3+a_1a_2a_4+a_1a_2a_5+a_1a_3a_4+a_1a_3a_5+a_2a_3a_4+a_2a_3a_5+a_3a_4a_5 = (a_1+a_2+a_3)(a_1+a_2+a_4)(a_1+a_2+a_5)(a_1+a_3+a_4)(a_1+a_3+a_5)(a_2+a_3+a_4)(a_2+a_3+a_5)(a_3+a_4+a_5)$

да, всё работает.

[mihaild]

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

хотя, конечно, не обязательно все возможные (отрицания/дополнения-то не входят)

Можно выразить ровно все монотонные функции. Правда непонятно, можно ли их как-то красиво все задать.