2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 20  След.
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 21:11 


22/11/22
605
Лево-право )

-- 25.08.2024, 20:13 --

Elijah96 в сообщении #1651507 писал(а):
Но в левой то части формулы элемент 6 посчитан трижды,или так и должно быть?

Лучше избегать таких фраз. Что такое посчитан трижды? Ну я так телепатически улавливаю, что на месте каждого из трех слагаемых будет стоять единица, потому что 6 входит во все три множества ) Да?

Плохо то, что это я что-то там понимаю, то есть это мои домыслы, а что при этом думаете вы - совершенно непонятно.

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


09/01/24
274
Combat Zone в сообщении #1651508 писал(а):
Но в левой то части формулы элемент 6 посчитан трижды,или так и должно быть?


Я уже исправил)
Там должно быть право)

-- 25.08.2024, 21:27 --

Combat Zone в сообщении #1651508 писал(а):
Ну я так телепатически улавливаю, что на месте каждого из трех слагаемых будет стоять единица, потому что 6 входит во все три множества ) Да?


Да,ведь элемент 6 входит в A,в B и в пересечение AB

-- 25.08.2024, 21:30 --

То есть нужно доказать что взяв любой элемент,он будет учтен ровно один раз?(либо 0 если он никуда не входит)

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


22/11/22
605
Ну тогда так и надо писать. Потому что "посчитан трижды" в обиходе три.

Что еще вы не поняли? Тут понятно стало?

-- 25.08.2024, 20:33 --

Elijah96 в сообщении #1651511 писал(а):
То есть нужно доказать что взяв любой элемент,он будет учтен ровно один раз?(либо 0 если он никуда не входит)

А это нуждается в доказательстве? Любой элемент из любого множества учитывается один раз.
А мы доказываем равенство. И его и хотели доказать. То самое, вкл-искл.

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


09/01/24
274
Combat Zone в сообщении #1651512 писал(а):
Ну тогда так и надо писать. Потому что "посчитан трижды" в обиходе три.


Извините,не так написал(

Combat Zone в сообщении #1651512 писал(а):
Что еще вы не поняли? Тут понятно стало?


Да вроде все понял
Просто уточнил

Combat Zone в сообщении #1651512 писал(а):
То есть нужно доказать что взяв любой элемент,он будет учтен ровно один раз?(либо 0 если он никуда не входит)

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


22/11/22
605
Elijah96 в сообщении #1651514 писал(а):
Просто уточнил

См.выше.

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


09/01/24
274
Combat Zone в сообщении #1651512 писал(а):
А мы доказываем равенство


Все
Дошло

В левой части формулы элементы всегда будут учитываться по одному разу(так как это объединение)
И в правой части формулы элементы тоже будут учитываться по одному разу(вне зависимости от того какой элемент и из какого множества рассматривается),так как это равенство

Возьму Вашу запись:
1=1+0-0 Здесь элемент $x$ принадлежит A но не принадлежит B и AB
1=0+1-0 Здесь элемент $x$ принадлежит B но не принадлежит A и AB
1=1+1-1 Здесь элемент $x$ принадлежит и A и B и AB
0=0+0-0 Здесь элемент $x$ не принадлежит ни A ни B ни AB

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

-- 25.08.2024, 21:54 --

dgwuqtj в сообщении #1651371 писал(а):
Вообще давайте введём обозначение $\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|}.$$
А дальше можете угадать формулу и попробовать её доказать...


А если получиться доказать по такой же логике как в формуле включений/исключений этот пример,то можно ли такое доказательство использовать если множеств n?

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


22/11/22
605
Вы, как смогли, разобрали текст dgwuqtj. Попробуем теперь доказать основную формулу (вкл-искл), у меня нет уверенности, что вы видите связь.

Давайте я вам часть напишу, с остальным попробуйте сами разобраться.

Напомню, слева у нас стоит 1, если икс лежит в объединении, ноль иначе.
То есть если выписать все такие равенства для всех элементов из объединения и сложить их построчно, то слева получится сумма из единичек, равная количеству элементов объединения, то есть число $|A\cup B|$.
На месте первого слагаемого в правой части будет в сумме стоять столько же единичек, сколько элементов в множестве $A$, то есть $|A|$

Это понятно?
Если понятно, попробуйте продолжить для след. слагаемых.

Вот так прямо столбиком и складываем.

-- 25.08.2024, 21:04 --

Elijah96 в сообщении #1651518 писал(а):
А если получиться доказать по такой же логике как в формуле включений/исключений этот пример,то можно ли такое доказательство использовать если множеств n?

Погодите пока с этим. Ни к чему торопиться.

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


09/01/24
274
Попытаюсь вкратце

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

$A = \lbrace 1,2,6,8 \rbrace , B = \lbrace 1,9,6,7 \rbrace , C = \lbrace 1,5,8,9 \rbrace , A \cap B = \lbrace 1,6 \rbrace , A \cap C = \lbrace 1,8 \rbrace , B \cap C = \lbrace 1,9 \rbrace , A \cap B \cap C = \lbrace 1 \rbrace $

Всевозможные объединения пересечений я обозначу $ \cup_i \cap_i $

А мощность всевозможных объединений пересечений я обозначу $| \cup_i \cap_i |$

(Не будьте строги,я не знаю как правильно обозначить это,равно как и многое другое)

Тогда $ \cup_i \cap_i $ = {1,6,8,9}

А $| \cup_i \cap_i |$ = 4

Проверяем по формуле:

$| \cup_i \cap_i | = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$ = 2+2+2-(1*2)=4

Результаты совпали

Далее

Пусть есть четыре множества A,B,C,D

Тогда $ \cup_i \cap_i $ = {1,3,6,7,8}

А $| \cup_i \cap_i |$ = 5

$A = \lbrace 1,2,3,6,8 \rbrace , B = \lbrace 1,3,6,7,9 \rbrace , C = \lbrace 1,3,5,8,9 \rbrace , D = \lbrace 1,2,3,5,7 \rbrace  A \cap B = \lbrace 1,3,6 \rbrace , A \cap C = \lbrace 1,3,8 \rbrace , A \cap D = \lbrace 1,2,3 \rbrace , B \cap C = \lbrace 1,3,9 \rbrace , B \cap D = \lbrace 1,3,7 \rbrace , C \cap D = \lbrace 1,3,5 \rbrace , A \cap B \cap C = \lbrace 1,3 \rbrace , A \cap B \cap D = \lbrace 1,3 \rbrace , A \cap C \cap B = \lbrace 1,3 \rbrace , B \cap C \cap D = \lbrace 1,3 \rbrace ,  A \cap C \cap B \cap D = \lbrace 1 \rbrace $

Проверяем по формуле:

$| \cup_i \cap_i | = |A \cap B| + |A \cap C| + |B \cap C| - 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|$ = 3+3+3+3+3+3-(2*2)-(2*2)-(2*2)-(2*2)+(3*1) = 5

Результаты совпали

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


22/11/22
605
Вы, конечно, орел, столько писать ) я даже сейчас почитаю. Но все-таки вернитесь к моему предыдущему посту. Там было нужно другое. Попробуйте сделать.

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


09/01/24
274
Combat Zone в сообщении #1651525 писал(а):
Вы, конечно, орел, столько писать ) я даже сейчас почитаю. Но все-таки вернитесь к моему предыдущему посту. Там было нужно другое. Попробуйте сделать.


Я там накосячил,так что можете не читать,все равно не правильно получилось)

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


22/11/22
605
Elijah96 в сообщении #1651524 писал(а):
= 5

Сомневаюсь я.
Elijah96 в сообщении #1651526 писал(а):
Я там накосячил,так что можете не читать,все равно не правильно получилось)

Поздно. )

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


09/01/24
274
Combat Zone в сообщении #1651522 писал(а):
Напомню, слева у нас стоит 1, если икс лежит в объединении, ноль иначе.


Это понятно,то есть если элемента икс нет в объединении,то будет 0

Combat Zone в сообщении #1651522 писал(а):
То есть если выписать все такие равенства для всех элементов из объединения и сложить их построчно, то слева получится сумма из единичек, равная количеству элементов объединения, то есть число $|A\cup B|$.


Вы имеете ввиду что если перебрать все элементы и выписать все неравенства?

Combat Zone в сообщении #1651522 писал(а):
На месте первого слагаемого в правой части будет в сумме стоять столько же единичек, сколько элементов в множестве $A$, то есть $|A|$


Это вообще не понятно

А на месте второго слагаемого будет стоять столько же единичек сколько $|B|$

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


22/11/22
605
Elijah96 в сообщении #1651528 писал(а):
Это вообще не понятно

Ага. И значит, непонятно, при чем тут формула вкл-искл
Combat Zone в сообщении #1651522 писал(а):
То есть если выписать все такие равенства для всех элементов из объединения и сложить их построчно, то слева получится сумма из единичек, равная количеству элементов объединения, то есть число $|A\cup B|$.

А это понятно?

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


09/01/24
274
Combat Zone в сообщении #1651530 писал(а):
А это понятно?


Имеется ввиду что нужно найти все равенства для всех элементов из объединения?

-- 25.08.2024, 23:14 --

Elijah96 в сообщении #1651531 писал(а):
Ага. И значит, непонятно, при чем тут формула вкл-искл


Elijah96 в сообщении #1651528 писал(а):
На месте первого слагаемого в правой части будет в сумме стоять столько же единичек, сколько элементов в множестве $A$, то есть $|A|$


Столько единичек,это потому что каждый элемент множества А рассматривается отдельно?

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


22/11/22
605
Elijah96 в сообщении #1651528 писал(а):
Вы имеете ввиду что если перебрать все элементы и выписать все неравенства?

Все равенства для всех элементов, да.
Elijah96 в сообщении #1651531 писал(а):
Имеется ввиду что нужно найти все равенства для всех элементов из объединения?

Предположим, что вы их уже выписали. Сама по себе цитата моя понятна?

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

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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