2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Теория множеств: сколько формул можно составить
Сообщение01.04.2013, 20:08 
Аватара пользователя


08/02/12
246
Условие задачи: Сколько различных выражений для множеств можно составить из 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, а это и значит, что мы сопоставим ей эту последовательность.
Ч.Т.Д

 Профиль  
                  
 
 Re: Теория множеств: сколько формул можно составить
Сообщение01.04.2013, 21:55 
Заслуженный участник


08/04/08
8556
Идея: $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$ подмножеств.

 Профиль  
                  
 
 Re: Теория множеств: сколько формул можно составить
Сообщение02.04.2013, 10:24 
Заслуженный участник
Аватара пользователя


06/04/10
3152
AnDe в сообщении #704487 писал(а):
Сколько различных выражений для множеств можно составить

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group