2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 20  След.
 
 Формула включений/исключений
Сообщение24.08.2024, 21:00 


09/01/24
274
Здравствуйте,помогите пожалуйста с формулой включений/исключений

Имеется четыре множества
Тогда объединением четырех множеств будет:

$(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$

Вопрос в следующем:
Во всех тройных пересечениях ( $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$ ) оказывается посчитано четыре раза(по одному в каждом тройном пересечении),а в конце формулы четверное пересечение вычитается один раз,значит оно останется посчитанным ровно 3 раза,а должно быть посчитано 1 раз.

P.S.Знаю что формула включений\исключений правильная,но в чем моя ошибка?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:10 
Заслуженный участник


07/08/23
1099
Вы опять складываете и вычитаете множества... Так что формула не то что неправильная, она бессмысленная.

А вообще четверное пересечение ещё входит в двойные пересечения и в одинарные (т.е. в сами $A, B, C, D$).

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:15 


09/01/24
274
dgwuqtj в сообщении #1651303 писал(а):
А вообще четверное пересечение ещё входит в двойные пересечения и в одинарные (т.е. в сами $A, B, C, D$).


В одинарных пересечениях четверное пересечение складывается,в двойных вычитается,в тройных опять складывается(и складывается 4 раза),а вот вычитается потом один раз

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:16 
Заслуженный участник


07/08/23
1099
$4 - 6 + 4 - 1 = 1$

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:25 


09/01/24
274
dgwuqtj в сообщении #1651306 писал(а):
$4 - 6 + 4 - 1 = 1$


Вы из одинарных множеств(их 4)вычли количество попарных пересечений(их 6),затем прибавили количество тройных пересечений(их 4)а затем вычли количество четверных пересечений(их одно)
В таком случае получается правильный результат

Но вопрос в другом
После сложениях тройных пересечений,зона четверного пересечения посчитана 4 раза,а вычитается один раз
На это вообще не стоит обращать внимание и следовать логике которую Вы привели?(то есть считать количество одинарных множеств,двойных,тройных...и т.д. пересечений,а затем считать все по формуле включений/исключений)

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:28 
Заслуженный участник


07/08/23
1099
А для трёх множеств вы эту формулу понимаете? И вообще умеете её правильно записывать?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:40 


09/01/24
274
dgwuqtj в сообщении #1651310 писал(а):
А для трёх множеств вы эту формулу понимаете?


Для трех множеств как раз таки все более понятно
После сложения одинарных множеств,вычитаются попарные,после вычитания попарных,зона тройного пересечения оказывается пуста,и поэтому прибавляется тройное пересечение

dgwuqtj в сообщении #1651310 писал(а):
И вообще умеете её правильно записывать?


В интернете такое написание формулы:

$ \mid A \cup B \cup C \cup D \mid = \mid A \mid + \mid B \mid + \mid C \mid + \mid D \mid - \mid A \cap B \mid - \mid A \cap C \mid - \mid A \cap D \mid - \mid B \cap C \mid - \mid B \cap D \mid - \mid C \cap D \mid + \mid A \cap B \cap C \mid + \mid A \cap B \cap D \mid + \mid A \cap C \cap D \mid + \mid B \cap C \cap D \mid - \mid A \cap B \cap C \cap D \mid $

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 21:49 
Заслуженный участник


07/08/23
1099
Ну и теперь посмотрите, сколько каждый элемент $x \in A \cap B \cap C \cap D$ будет посчитан в левой и в правой части.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 22:10 


09/01/24
274
dgwuqtj в сообщении #1651312 писал(а):
Ну и теперь посмотрите, сколько каждый элемент $x \in A \cap B \cap C \cap D$ будет посчитан в левой и в правой части.


Погодите,я попробую:

Предположим что в $ \mid A \cap B \cap C \cap D \mid $ есть три элемента(1,2,3)

Тогда эти три элемента будут посчитаны:
В множестве А один раз
В множестве В один раз
В множестве С один раз
В множестве D один раз
(Так как эти элементы(1,2,3)есть в каждом множестве(А,B,C,D))
А раз они есть в каждом множестве(A,B,C,D)по отдельности,то они есть и во всех пересечениях этих множеств,и в каждом пересечении этих множеств,эти элементы будут посчитаны по одному разу(сказал что сам не понял,надеюсь Вы поймете что я написал)

И получается следующее:
1+1+1+1-1-1-1-1-1-1+1+1+1+1-1 = 4-6+4-1=1
(Единица это количество раз,сколько посчитаны элементы 1,2,3 в множествах)
Первые четыре единицы это одинарные множества
Вторые шесть единиц это попарные пересечения
Третьи четыре единицы это тройные пересечения
Четвертая единица это четверное пересечение

(Я видимо опять не туда думаю?)

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 22:16 
Заслуженный участник


20/04/10
1878
Есть такой метод, называется математическая индукция. Может помочь.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение24.08.2024, 23:37 
Заслуженный участник


07/08/23
1099
Elijah96 в сообщении #1651315 писал(а):
А раз они есть в каждом множестве(A,B,C,D)по отдельности,то они есть и во всех пересечениях этих множеств,и в каждом пересечении этих множеств,эти элементы будут посчитаны по одному разу(сказал что сам не понял,надеюсь Вы поймете что я написал)

Вот вам бы ещё понять, что вы написали, а так всё правильно.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 12:30 


09/01/24
274
dgwuqtj в сообщении #1651322 писал(а):
Elijah96 в сообщении #1651315 писал(а):
А раз они есть в каждом множестве(A,B,C,D)по отдельности,то они есть и во всех пересечениях этих множеств,и в каждом пересечении этих множеств,эти элементы будут посчитаны по одному разу(сказал что сам не понял,надеюсь Вы поймете что я написал)

Вот вам бы ещё понять, что вы написали, а так всё правильно.


Вроде бы логику понял
Можно ли тогда в таком случае сказать что:
Чтобы найти мощность объединения множеств,нужно из количества одиночных множеств вычесть количество попарных пересечений,затем прибавить количество тройных пересечений и т.д.

И еще вопрос
Можно ли найти мощность объединения всех пересечений множеств по такое же логике как на примере выше(посчитать количество того сколько раз элемент $x$ учтен в правой части)

Например верна ли формула для мощности объединения всех пересечений множеств?

$ \mid A \cap B \cup A \cap C \cup A \cap D \cup B\cap C \cup B \cap D \cup C \cap D \cup A \cap B \cap C \cup A \cap B \cap D \cup A \cap C \cap D \cup B \cap C \cap D \cup A \cap B \cap C \cap D \mid = \mid A \cap B \mid + \mid A \cap C \mid + \mid A \cap D \mid + \mid B \cap C \mid + \mid B \cap D \mid + \mid C \cap D \mid - \mid A \cap B \cap C \mid - \mid A \cap B \cap D \mid - \mid A \cap C \cap D \mid - \mid B \cap C \cap D \mid  + \mid A \cap B \cap C \cap D\mid $

P.S.Я не знаю как обозначить мощность объединения всех пересечений множеств,поэтому обозначил ее так громоздко $ \mid A \cap B \cup A \cap C \cup A \cap D \cup B\cap C \cup B \cap D \cup C \cap D \cup A \cap B \cap C \cup A \cap B \cap D \cup A \cap C \cap D \cup B \cap C \cap D \cup A \cap B \cap C \cap D \mid $

Смысл в том чтобы найти мощность объединения всех пересечений множеств нужно сначала сложить все попарные пересечения,затем вычесть все тройные пересечения,затем прибавить четверное пересечение

Верна ли мысль?

И верно ли что если из суммы мощностей множеств A,B,C,D вычесть мощность объединения всех пересечений множеств,то получится мощность объединения множеств A,B,C,D?

То есть(на примере множеств выше):
6-4+1=3(это,если можно так выразиться,мощность объединения всех пересечений множеств)
Далее из суммы мощностей множеств A,B,C,D вычитаем мощность объединения всех пересечений множеств,

Выходит:
4-3=1
Будет ли это мощностью объединения множеств A,B,C,D?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 13:08 
Заслуженный участник


07/08/23
1099
Elijah96 в сообщении #1651366 писал(а):
Чтобы найти мощность объединения множеств,нужно из количества одиночных множеств вычесть количество попарных пересечений,затем прибавить количество тройных пересечений и т.д

Нет, вы так всегда будете получать 1.
Elijah96 в сообщении #1651366 писал(а):
Можно ли найти мощность объединения всех пересечений множеств по такое же логике как на примере выше

Наверное, можно, но я вам формулу не назову.
Elijah96 в сообщении #1651366 писал(а):
Верна ли мысль?

Нет, проверьте сами на простом примере типа $A = B = C = D = \{x\}$.
Elijah96 в сообщении #1651366 писал(а):
И верно ли что если из суммы мощностей множеств A,B,C,D вычесть мощность объединения всех пересечений множеств,то получится мощность объединения множеств A,B,C,D?

Нет, тот же контрпример.

-- 25.08.2024, 13:20 --

Вообще давайте введём обозначение $\cup_{\geq 2}(A_1, \ldots, A_n) = \bigcup_{1 \leq i < j \leq n} (A_i \cap A_j)$, то есть множество тех элементов, которые входят в хотя бы два множества из $A_1, \ldots, A_n$ (вам вроде именно это надо). Можно руками получить такие формулы: $|\cup_{\geq 2}(A)| = 0$, $|\cup_{\geq 2}(A, B)| = |A \cap B|$, $|\cup_{\geq 2}(A, B, C)| = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$,
$$\substack{|\cup_{\geq 2}(A, B, C, D)| = |A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|\\ - 2 |A \cap B \cap C| - 2 |A \cap B \cap D| - 2 |A \cap C \cap D| - 2 |B \cap C \cap D| + 3 |A \cap B \cap C \cap D|}.$$
А дальше можете угадать формулу и попробовать её доказать...

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 15:25 


09/01/24
274
dgwuqtj в сообщении #1651371 писал(а):
А дальше можете угадать формулу и попробовать её доказать...


Я могу попытаться доказать формулу для трех множеств,потому что для четырех у меня не сходиться

Например есть три множества A,B,C

Тогда мощностью объединения всевозможных их пересечений будет:

$|\cup_{\geq 2}(A, B, C)| = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$

То есть сначала складываются всевозможные попарные пересечения
Затем нужно вычесть дважды тройное пересечение,так как оно учитывается три раза( в пересечении AB,в пересечении AC и в пересечении BC)

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 15:40 
Заслуженный участник


07/08/23
1099
Доказывайте тогда для трёх множеств.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 298 ]  На страницу 1, 2, 3, 4, 5 ... 20  След.

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



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

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


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

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