Формула включений/исключений

[dgwuqtj]

Elijah96 в сообщении #1652095 писал(а):

Если $x$ $\in$ $A \cap B$ то он посчитан ровно $|A| + |B| - |A \cap B|$ раз ( в $|A|$ , в $|B|$ и в $|A \cap B|$ )

Ну нет же!

[Elijah96]

dgwuqtj в сообщении #1652097 писал(а):

Ну нет же!

В чем опять ошибка?

[dgwuqtj]

Вот с чего вы взяли, что он будет посчитан только в этих трёх слагаемых?

[Elijah96]

dgwuqtj в сообщении #1652099 писал(а):

Вот с чего вы взяли, что он будет посчитан только в этих трёх слагаемых?

Потому что есть только A,B и AB

И если $x$ $\in$ $A \cap B$ то следовательно он есть в А и есть в В

Не так?

[dgwuqtj]

Речь идёт про формулу для $|A \cup B \cup C|$. Есть ещё $C$, $A \cap C$, $B \cap C$ и $A \cap B \cap C$.

[Elijah96]

dgwuqtj в сообщении #1652101 писал(а):

Речь идёт про формулу для $|A \cup B \cup C|$. Есть ещё $C$, $A \cap C$, $B \cap C$ и $A \cap B \cap C$.

А
Я думал про формулу $|A \cup B| = |A| + |B| - |A \cap B|$

[dgwuqtj]

Elijah96 в сообщении #1652102 писал(а):

Я думал про формулу $|A \cup B| = |A| + |B| - |A \cap B|$

С ней вроде всё нормально.

[Elijah96]

Если $x$ только $x$ $\in$ $A \cap B$ то в других слагаемых его быть не может

Если $x$ еще и $x$ $\in$ $C$ то тогда уже $x$ $\in$ $A \cap B \cap C$

[dgwuqtj]

Elijah96 в сообщении #1652104 писал(а):

Если $x$ только $x$ $\in$ $A \cap B$

Что это должно значить? Элемент $x$ не может принадлежать только одному-единственному множеству $A \cap B$, он как минимум принадлежит $\{x\}$, $A$ и $B$...

[Elijah96]

dgwuqtj в сообщении #1652105 писал(а):

Что это должно значить? Элемент $x$ не может принадлежать только одному-единственному множеству $A \cap B$, он как минимум принадлежит $\{x\}$, $A$ и $B$...

Ну если $x$ $\in$ $A \cap B$ то $x$ $\in$ $A$ и $B$

Тогда $x$ $\notin$ $C$

Ведь если $x$ $\in$ $A$ , $B$ и $C$

То $x$ $\in$ $A \cap B \cap C$

[dgwuqtj]

Из истинного утверждения

Elijah96 в сообщении #1652106 писал(а):

если $x$ $\in$ $A$ , $B$ и $C$

То $x$ $\in$ $A \cap B \cap C$

не следует ложное утверждение

Elijah96 в сообщении #1652106 писал(а):

если $x$ $\in$ $A \cap B$ то $x$ $\in$ $A$ и $B$

Тогда $x$ $\notin$ $C$

. Ровно потому что $x \in A \cap B$ может всё-таки попасть в $C$.

Вообще, если уж доказывать перебором случаев, то удобнее такие варианты рассматривать:
1. $x \in A$, $x \in B$ и $x \in C$;
2. $x \in A$, $x \in B$ и $x \notin C$;
3. $x \in A$, $x \notin B$ и $x \in C$;
4. $x \in A$, $x \notin B$ и $x \notin C$;
5. $x \notin A$, $x \in B$ и $x \in C$;
6. $x \notin A$, $x \in B$ и $x \notin C$;
7. $x \notin A$, $x \notin B$ и $x \in C$;
8. $x \notin A$, $x \notin B$ и $x \notin C$.
Во-первых, сразу видно, что это все возможные случаи. То есть для любого элемента $x$ какой-то из этих случаев реализуется (на самом деле ровно один). А во-вторых, для каждого из этих случаев легко проверить, каким множествам, сконструированным из $A$, $B$, $C$, будет принадлежать $x$. Просто по определению, например, в третьем случае $x \notin A \cap B$ (потому что $x \notin B$) и $x \in A \cap C$ (потому что $x \in A$ и $x \in C$).

[Elijah96]

dgwuqtj в сообщении #1652107 писал(а):

Из истинного утверждения

Elijah96 в сообщении #1652106 писал(а):

если $x$ $\in$ $A$ , $B$ и $C$

То $x$ $\in$ $A \cap B \cap C$

не следует ложное утверждение

Elijah96 в сообщении #1652106 писал(а):

если $x$ $\in$ $A \cap B$ то $x$ $\in$ $A$ и $B$

Тогда $x$ $\notin$ $C$

. Ровно потому что $x \in A \cap B$ может всё-таки попасть в $C$.

Вообще, если уж доказывать перебором случаев, то удобнее такие варианты рассматривать:
1. $x \in A$, $x \in B$ и $x \in C$;
2. $x \in A$, $x \in B$ и $x \notin C$;
3. $x \in A$, $x \notin B$ и $x \in C$;
4. $x \in A$, $x \notin B$ и $x \notin C$;
5. $x \notin A$, $x \in B$ и $x \in C$;
6. $x \notin A$, $x \in B$ и $x \notin C$;
7. $x \notin A$, $x \notin B$ и $x \in C$;
8. $x \notin A$, $x \notin B$ и $x \notin C$.
Во-первых, сразу видно, что это все возможные случаи. То есть для любого элемента $x$ какой-то из этих случаев реализуется (на самом деле ровно один). А во-вторых, для каждого из этих случаев легко проверить, каким множествам, сконструированным из $A$, $B$, $C$, будет принадлежать $x$. Просто по определению, например, в третьем случае $x \notin A \cap B$ (потому что $x \notin B$) и $x \in A \cap C$ (потому что $x \in A$ и $x \in C$).

Ваш вариант перебора оказался даже более легкий и быстрый

-- 28.08.2024, 15:09 --

Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно
Все равно спасибо всем что попытались помочь с этой формулой

[dgwuqtj]

Elijah96 в сообщении #1652115 писал(а):

Но к доказательству формулы вкл\искл я так и не приблизился

Там, если делать в лоб, надо для каждого $n$ написать перебор $2^n$ вариантов. Чтобы не писать бесконечно много текста, используют какие-то общие рассуждения. Можете прочитать доказательство в какой-нибудь книжке, типа Дж. Андерсон, Дискретная математика и комбинаторика, теорема 12.7. Разумеется, там возникают какие-то суммы с биномиальными коэффициентами, их надо уметь считать. Вам вообще стоило бы прочитать побольше всяких теорем с доказательствами из дискретной математики (и порешать задач!), опыта набраться.

[lel0lel]

Elijah96 в сообщении #1652115 писал(а):

Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно

Может так: посчитав сумму мощностей объединяемых множеств, все области с чисто двойным пересечением учли дважды. Поэтому, вычитаем мощности всевозможных двойных пересечений, но вместе с этим выкинули мощности чисто тройных пересечений, так как $3-\binom{3}{2}=3-3=0$, поэтому добавляем мощности всевозможных тройных пересечений. Теперь у нас чисто единичные , чисто двойные и чисто тройные учтены правильно. А что с чисто четвертыми? Так как $4-\binom{4}{2}+\binom{4}{3}=4-6+4=2$, оказывается, они учтены дважды. Чтобы справедливость восторжествовала, выкидываем всевозможные четверные, теперь с чисто четверными полный порядок! Но не накосячили ли мы с чисто пятерными (это хорошо если их нет, а вдруг есть). Проверяем $5-\binom{5}{2}+\binom{5}{3}-\binom{5}{4}=5-30+30-5=0$, накосячили, они не учтены в мощности объединения! Ворочаем их назад добавлением мощностей всевозможных пятерых пересечений. И т.д.

[Elijah96]

dgwuqtj в сообщении #1652127 писал(а):

Elijah96 в сообщении #1652115 писал(а):

Но к доказательству формулы вкл\искл я так и не приблизился

Там, если делать в лоб, надо для каждого $n$ написать перебор $2^n$ вариантов. Чтобы не писать бесконечно много текста, используют какие-то общие рассуждения. Можете прочитать доказательство в какой-нибудь книжке, типа Дж. Андерсон, Дискретная математика и комбинаторика, теорема 12.7. Разумеется, там возникают какие-то суммы с биномиальными коэффициентами, их надо уметь считать. Вам вообще стоило бы прочитать побольше всяких теорем с доказательствами из дискретной математики (и порешать задач!), опыта набраться.

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

-- 28.08.2024, 17:16 --

lel0lel в сообщении #1652131 писал(а):

Elijah96 в сообщении #1652115 писал(а):

Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно

Может так: посчитав сумму мощностей объединяемых множеств, все области с чисто двойным пересечением учли дважды. Поэтому, вычитаем мощности всевозможных двойных пересечений, но вместе с этим выкинули мощности чисто тройных пересечений, так как $3-\binom{3}{2}=3-3=0$, поэтому добавляем мощности всевозможных тройных пересечений. Теперь у нас чисто единичные , чисто двойные и чисто тройные учтены правильно. А что с чисто четвертыми? Так как $4-\binom{4}{2}+\binom{4}{3}=4-6+4=2$, оказывается, они учтены дважды. Чтобы справедливость восторжествовала, выкидываем всевозможные четверные, теперь с чисто четверными полный порядок! Но не накосячили ли мы с чисто пятерными (это хорошо если их нет, а вдруг есть). Проверяем $5-\binom{5}{2}+\binom{5}{3}-\binom{5}{4}=5-30+30-5=0$, накосячили, они не учтены в мощности объединения! Ворочаем их назад добавлением мощностей всевозможных пятерых пересечений. И т.д.

Это сочетания без повторений?

И как в таком случае доказать для n множеств?