2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 16:16 
Я знаю как выглядит формула включения и исключения для 4-х множеств:
$|A\cup B\cup C \cup D|=|A|+|B|+|C|+|D|-|A\cap B|-|A\cap C|-|A\cap D|-|B\cap C|-|B\cap D|-|C\cap D|+
|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|-|A\cap B\cap C\cap D|$.
А как это доказать или обосновать не знаю. Подскажите, пожалуйста.

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 16:17 
Аватара пользователя
Круги рисовать умеете?

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 16:18 
Аватара пользователя
Marina в сообщении #297973 писал(а):
Я знаю как выглядит формула включения и исключения для 4-х множеств

Я тоже :)

Marina в сообщении #297973 писал(а):
А как это доказать или обосновать не знаю.

Взять формулу для $n$ множеств и подставить в неё $n=4$ :)

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 16:31 
ИСН, Вы имеете ввиду диаграмму ЭйлераИзображение

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 16:35 
Аватара пользователя

(Оффтоп)

Леонид Ильич, переверните страницу, это олимпийские кольца :)


-- Пн мар 15, 2010 19:40:27 --

Нарисуйте круги так, чтобы все возможные пересечения образовывали $15$ различных множеств.

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 16:45 
Цитата:
Взять формулу для $n$- множеств

Нужно объяснение без применения формулы $n$-множества.

-- Пн мар 15, 2010 16:50:38 --

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

(Оффтоп)

Если Вы своё пятое добавите для точности рисунка

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 17:26 
Аватара пользователя
Круги у Вас не очень хороши тем, что четверное пересечение пусто; но вообще-то они тут не нужны, это просто у меня такая catchphrase. На самом деле надо так:
- Посчитаем все. Теперь смотрим: входящие в два множества оказались посчитаны дважды, поэтому их вычитаем. Но теперь входящие в три множества оказались...

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 17:44 
Аватара пользователя
Посмотрите в книге Виленкина "Комбинаторика", там по-моему есть!

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение15.03.2010, 18:06 
Аватара пользователя
Да просто индукцию по числу множеств примените.

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение16.03.2010, 07:57 
bot
Индукцию по числу множеств не проходили. Может без её можно обойтись?

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение16.03.2010, 08:15 
Докажите формулу $|A \cup F|=|A|+|F|-|A \cap F|$. Затем, вместо $F$ возьмите $B \cup C$ и используйте доказанную формулу для доказательства $|A \cup B \cup C|$. Аналогично для четырёх множеств.

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение16.03.2010, 10:02 
Alexey1 Я Вас правильно поняла:
$|A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B| +|C|- |(A\cup B)\cap C|=|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|=|A|+|B|-|A\cap B|+|C|-|A\cap C|+|B\cap C|-|(A\cap C)|\cap (B\cap C)|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap C\cap B|$

|A\cup B\cup C\cup D|= |A\cup B| + |C\cup D|- |(A\cup B)\cap (C\cup D)|=|A| + |B|+|C| + |D| - |C\cap D|-|A\cap B|- |(A\cup B)\cap (C\cup D)|=

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение16.03.2010, 10:17 
В предпоследнем выражении первой цепочки скобки потеряны, но на выходе -- верно.

Общая теорема выглядит так: мощность объединения есть сумма единичных мощностей, минус сумма всех парных, плюс сумма всех троек, минус сумма всех четвёрок, и т.д. до мощности пересечения всех (с соответствующим знаком). И доказывается -- именно по индукции. Вот Вы сейчас эту индукцию и провели, только для конкретного $n=3$.

Для четырёх, соответственно -- Ваша стратегия не учень удачна. Разумнее раскрывать $|(A\cup B\cup C)\cup D|$.

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение16.03.2010, 11:34 
Аватара пользователя
Вывод по индукции здесь, наверное, самый правильный, но можно сделать напрямую и без него. Фактически это метод с помощью "кругов", но ничего рисовать не нужно. Все пространство представляется в виде попарно непересекающихся 16-ти множеств вида: $ABCD$, $ABC\overline{D}$, $AB\overline{C}D$, $AB\overline{C}\overline{D}$, ..., $\overline{A}\overline{B}\overline{C}\overline{D}$.

Левая часть тождества содержит 15 множеств (все, кроме последнего). Далее можно вручную выписать через эти множества все слагаемые в правой части. $A$ будет состоять из 8-ми множеств, $AB$ из четырех и так далее. Затем посокращать все, что получится, и должны придти к тому же, что написано слева.

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

 
 
 
 Re: формула включения и исключения для 4-х множеств
Сообщение16.03.2010, 12:29 
ewert,
Пошла по Вашему предложению, так как оно мне показалось более понятным:
$|(A\cup B\cup C)\cup D|=|A\cup B\cup C|+|D|-|(A\cup B\cup C)\cap D|=|A|+|B|+|C|+|D|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|- |(A\cup B\cup C)\cap D|$
Или я сделала, что-то не так?

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group