Теория множеств: сколько формул можно составить

[AnDe]

Условие задачи: Сколько различных выражений для множеств можно составить из n переменных с помощью (многократно используемых) операций пересечения, объединения и разности?
Интерес состоит в том, чтобы решить её элементарными методами, она находится в первом пункте Верещагина.
У меня получилось, но слишком громоздко.


Лемма: Если какое-то равенство (содержащее переменные для множеств и операции пересечения, объединения, разности) неверно, то можно подобрать контрпример к нему, в котором все множества равны $\emptyset$ или $\{x\}$, где $x$ - некоторый объект.

Доказательство: Т.к. равенство неверно, то как минимум один контрпример существует : $A_1, ... , A_n$, при подстановке их вместо переменных получаем два множества (в правой и левой частях равенства), которые не равны, то есть существует некоторый объект $x$, который принадлежит одному из них и не принадлежит другому, рассмотрим множества $A'_1=A_1 \cap \{x\}, ... , A'_n=A_n \cap \{x\} $. Каждое из них равно либо $\emptyset$, либо $\{x\}$. Этот набор также является контрпримером, т.к. если в левой и правой частях объект $x$ будет тогда и только тогда, когда он был там до этого, поскольку $x \in A'_i \leftrightarrow x \in A_i$ (не знаю следует ли это доказывать строже, т.к. понятие формулы не как не определялось)
Ч.Т.Д.


Выберем произвольно объект $x$ и рассмотри все возможные наборы длины n состоящие из множеств $\emptyset$ и $\{x\}$. Как известно их всего $2^n$. Обозначим их произвольным образом через $\omega_1, ... , \omega_{2^n}$ так, чтобы набор из пустых множеств был обозначен через $\omega_1$. Обозначим $j$-ое множество $i$-ого набора через $A_j^i$. Опираясь на лемму можем сказать, что две формулы равны тогда и только тогда, когда они равны для всех указанных наборов. Каждому набору $\omega_i$, кроме $\omega_1$ сопоставим формулу, которая является пересечением $n$ формул, $j$-ая из которых равна $x_j$, если $A^i_j = \{x\}$ и $x_o \setminus x_j$ в противном случае, где$ A^i_o$ - произвольный элемент набора, отличный от пустого множества и обозначим ее через $A^i$. Ясно, что при подстановке в эту формулу любого набора, кроме $\omega_i$ в результате получится пустое мно-во, и только при подстановке $\omega_i$ в результате получится мно-во $\{x\}$.

Любой формуле сопоставим последовательность из единиц и нулей длины $2^n$, у которой на $i$-ом месте стоит единица, если при подстановке в эту формулу набора $\omega_i$ получиться мно-во $\{x\}$, и 0 в противном случае. Ясно, что на первом месте всегда будет стоять 0. Переформулируя, результат леммы, можем сказать, что формулы равны тогда и только тогда, когда равны сопоставленные им последовательности, а их не более $2^{2^n-1}$, значит и различных формул не больше этого числа.

Покажем, что их ровно столько, для этого для каждой последовательности длины $2^n$ из нулей и единиц, на первом месте которой стоит 0, укажем формулу, которой мы сопоставили эту последовательность. Это будет объединение некоторых формул $A^i$, а именно для таких $i$, что в выбранной последовательности на $i$-ом месте стоит 1. Ясно, что она будет принимать значение $\{x\}$ тогда и только тогда, когда мы поставим такой набор $\omega_i$, что в выбранной последовательности на $i$-ом месте стоит 1, а это и значит, что мы сопоставим ей эту последовательность.
Ч.Т.Д

[Sonic86]

Идея: $n$ переменных множеств общем случае разбивают универсум на $2^n$ деталей, из которых только $2^n-1$ можно выразить через операции пересечения и разности (даже объединение не нужно), а потом объединением из них можно собрать $2^{2^n-1}$ вариантов множеств (для каждой детали 2 варианта: либо включать ее в объединение, либо не включать).
(просто смотрим на диаграмму Эйлера-Венна и видим это)

И теперь это все формально строго расписать:
Пусть даны переменные множества $B_1,...,B_n$. Деталью назовем множество, получаемое через разность и пересечение всех данных $n$ множеств, детали существуют по определению. Детали никаким множеством $B_j$ не делится на 2 непустые части, другими словами, для каждого $B_j$ деталь либо целиком лежит в $B_j$, либо целиком не лежит в ней. Пусть $M_n$ - множество деталей, $k_n=|M_n|$, $M_1=\{B_1\}$, $M_{n+1}=M_n\cap B_{n+1}+M_n\setminus B_{n+1}+B_{n+1}\setminus (B_1\cup...\cup B_n)$ (а можно формулы для построения деталей перебрать) (а вот тут надо доказать, что все детали различны). Тогда $k_{n+1}=2k_{n}+1, k_n=2^n-1$, ну и в конце получаем $2^{k_n}$.

З.Ы. Задание надо целиком приводить, с пояснениями в скобках.

-- Пн апр 01, 2013 19:14:59 --

Sonic86 в сообщении #704554 писал(а):

Пусть даны переменные множества $B_1,...,B_n$. Деталью назовем множество, получаемое через разность и пересечение всех данных $n$ множеств, детали существуют по определению. Детали никаким множеством $B_j$ не делится на 2 непустые части, другими словами, для каждого $B_j$ деталь либо целиком лежит в $B_j$, либо целиком не лежит в ней. Пусть $M_n$ - множество деталей, $k_n=|M_n|$, $M_1=\{B_1\}$, $M_{n+1}=M_n\cap B_{n+1}+M_n\setminus B_{n+1}+B_{n+1}\setminus (B_1\cup...\cup B_n)$ (а можно формулы для построения деталей перебрать) (а вот тут надо доказать, что все детали различны). Тогда $k_{n+1}=2k_{n}+1, k_n=2^n-1$, ну и в конце получаем $2^{k_n}$.

Даже еще проще. Ясно, что мы с помощью объединения не выйдем за $B_1\cup...\cup B_n=U_1$. Но мы можем реализовать операцию дополнения в $U_1$: $\left.\bar{B_j}\right|_{U_1}=U_1\setminus B_j$. И тогда мы в $U_1$ имеем операции объединения, пересечения и дополнения, значит может построить все $2^n-1$ подмножеств.

[nikvic]

AnDe в сообщении #704487 писал(а):

Сколько различных выражений для множеств можно составить

Путаница.
Выражения суть слова, и понятие одинаковости слов делает вопрос тривиальным: до чёрта
Но Вас-то интересует эквивалентность выражений как "описателей" функций...