2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12 ... 20  След.
 
 Re: Формула включений/исключений
Сообщение26.08.2024, 22:43 


22/11/22
605
Elijah96 в сообщении #1651725 писал(а):
Просто первые четыре единицы,вторые четыре единицы и третьи две единицы*

Почти. Но вы забываете про доказательство формулы. Это равенство. От того, что вы просто посчитаете единицы, равенство не получится. Хотя вы на верном пути и это уже хорошо.
А подсказка-то была, как равенство получить.
В вашем случае.

-- 26.08.2024, 21:49 --

Elijah96 в сообщении #1651725 писал(а):
Еще одна неудачная попытка

$|A \cup B| = |A| + |B| - |A \cap B| \Rightarrow |A \cup B| - |B| + |A \cap B| = |A| \Rightarrow |A| = |A \cup B| - |B| + |A \cap B|$


Это правильно (ерунду и повторы копировать не буду), но незачем. Множества у вас сейчас конкретные, элементы у них известны, мощности посчитать можно, равенство обычное числовое. Его и нужно было получить из вашего столбика равенств для всех элементов.

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


09/01/24
274
Combat Zone в сообщении #1651814 писал(а):
Почти. Но вы забываете про доказательство формулы. Это равенство. От того, что вы просто посчитаете единицы, равенство не получится. Хотя вы на верном пути и это уже хорошо.
А подсказка-то была, как равенство получить.
В вашем случае.


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

Возьму свои же примеры:

Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B|$ то он посчитан нуль раз

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|A \cap B|$ то он посчитан один раз

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз

Если элемент $x$ принадлежит $|A \cap B|$ то он принадлежит и $|A|$ и $|B|$ и посчитан ровно $|A| + |B| - |A \cap B|$ раз

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$

$A \cup B \quad A \auad \quad B \quad A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 $ $\quad \quad \quad$ Элемент 2

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 $ $\quad \quad \quad$ Элемент 8

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 $ $\quad \quad \quad$ Элемент 7

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 $ $\quad \quad \quad$ Элемент 9

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 $ $\quad \quad \quad$ Элемент 1

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 $ $\quad \quad \quad$ Элемент 6

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз

Если элемент $x$ принадлежит $|A \cap B|$ то он принадлежит и $|A|$ и $|B|$ и посчитан ровно $|A| + |B| - |A \cap B|$ раз

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит А но не принадлежит B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит B но не принадлежит A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B \cup C|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B \cup C|$ то он посчитан нуль раз

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|C|$ , $|A \cap B|$ , $|A \cap C|$ то он посчитан один раз

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|C|$ , $|A \cap B|$ , $|B \cap C|$ то он посчитан один раз

Если элемент $x$ принадлежит только $|C|$ и не принадлежит $|A|$ , $|B|$ , $|A \cap C|$ , $|B \cap C|$ то он посчитан один раз

Если элемент $x$ принадлежит $|A \cap B|$ то он принадлежит и $|A|$ и $|B|$ и посчитан ровно $|A| + |B| - |A \cap B|$ раз

Если элемент $x$ принадлежит $|A \cap C|$ то он принадлежит и $|A|$ и $|C|$ и посчитан ровно $|A| + |C| - |A \cap C|$ раз

Если элемент $x$ принадлежит $|B \cap C|$ то он принадлежит и $|B|$ и $|C|$ и посчитан ровно $|B| + |C| - |B \cap C|$ раз

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он принадлежит и $|A|$ и $|B|$ и $|C|$ и посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap 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$

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

$A \cup B \quad A \quad B \quad C \quad A \cap B \quad  A \cap C \quad B \cap C \quad  A \cap B \cap C$

$ \quad 1 \quad = \quad 1  + 0 +  0  -  \quad 0 \quad - \quad 0 \quad - \quad 0 \quad + \quad \quad 0 $ $\qqquad$ Элемент 2

$ \quad 1 \quad = \quad 0  + 0 +  1  -  \quad 0 \quad - \quad 0 \quad - \quad 0 \quad + \quad \quad 0 $ $\qqquad$ Элемент 5

$ \quad 1 \quad = \quad 1  + 1 +  0  -  \quad 1 \quad - \quad 0  \quad -\quad 0 \quad + \quad \quad 0 $ $\qqquad$ Элемент 6

$ \quad 1 \quad = \quad 0  + 1 +  0  -  \quad 0 \quad - \quad 0 \quad - \quad 0 \quad + \quad \quad 0 $ $\qqquad$ Элемент 7

$ \quad 1 \quad = \quad 1  + 0 +  1  -  \quad 0 \quad - \quad 0 \quad - \quad 1 \quad + \quad \quad 0 $ $\qqquad$ Элемент 8

$ \quad 1 \quad = \quad 0  + 1 +  1  -  \quad 0 \quad - \quad 0 \quad - \quad 1 \quad + \quad \quad 0 $ $\qqquad$ Элемент 9

$ \quad 1 \quad = \quad 1  + 1 +  1  -  \quad 1 \quad - \quad 1 \quad - \quad 1 \quad + \quad \quad 1 $ $\qqquad$ Элемент 1

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|C|$ , $|A \cap B|$ , $|A \cap C|$ то он посчитан один раз

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|C|$ , $|A \cap B|$ , $|B \cap C|$ то он посчитан один раз

Если элемент $x$ принадлежит только $|C|$ и не принадлежит $|A|$ , $|B|$ , $|A \cap C|$ , $|B \cap C|$ то он посчитан один раз

Если элемент $x$ принадлежит $|A \cap B|$ то он принадлежит и $|A|$ и $|B|$ и посчитан ровно $|A| + |B| - |A \cap B|$ раз

Если элемент $x$ принадлежит $|A \cap C|$ то он принадлежит и $|A|$ и $|C|$ и посчитан ровно $|A| + |C| - |A \cap C|$ раз

Если элемент $x$ принадлежит $|B \cap C|$ то он принадлежит и $|B|$ и $|C|$ и посчитан ровно $|B| + |C| - |B \cap C|$ раз

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он принадлежит и $|A|$ и $|B|$ и $|C|$ и посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(Принадлежит C но не принадлежит A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит AB но не принадлежит C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит AC но не принадлежит B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит BC но не принадлежит A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано".

-- 27.08.2024, 14:07 --

Таблицу для трех множест щас попробую выравнить

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


09/01/24
274
Чуть-чуть подредактировал

Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|A \cap B|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз ( в $|B|$ )

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

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$


$A \cup B \quad A \auad \quad B \quad A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - 0 \quad \quad Element \quad 2 $

$ \quad 1 \quad = \quad 1 + 0 \quad - 0 \quad \quad Element \quad 8 $

$ \quad 1 \quad = \quad 0 + 1 \quad - 0 \quad \quad Element \quad 7 $

$ \quad 1 \quad = \quad 0 + 1 \quad - 0 \quad \quad Element \quad 9 $

$ \quad 1 \quad = \quad 1 + 1 \quad - 1 \quad \quad Element \quad 1 $

$ \quad 1 \quad = \quad 1 + 1 \quad - 1 \quad \quad Element \quad 6 $

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз ( в $|B|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит А но не принадлежит B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит B но не принадлежит A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B \cup C|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B \cup C|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|C|$ , $|A \cap B|$ , $|A \cap C|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|C|$ , $|A \cap B|$ , $|B \cap C|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ принадлежит только $|C|$ и не принадлежит $|A|$ , $|B|$ , $|A \cap C|$ , $|B \cap C|$ то он посчитан один раз (в $|C|$ )

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

Если элемент $x$ принадлежит $|A \cap C|$ то он принадлежит и $|A|$ и $|C|$ и посчитан ровно $|A| + |C| - |A \cap C|$ раз ( в $|A|$ , в $|C|$ и в $|A \cap C|$ )

Если элемент $x$ принадлежит $|B \cap C|$ то он принадлежит и $|B|$ и $|C|$ и посчитан ровно $|B| + |C| - |B \cap C|$ раз ( в $|B|$ , в $|C|$ и в $|B \cap C|$ )

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он принадлежит и $|A|$ и $|B|$ и $|C|$ и $|A \cap B|$ и $|A \cap C|$ и $|B \cap C|$ и посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


$A \cup B \cup C \quad A \quad B \quad C \quad A \cap B \quad  A \cap C \quad B \cap C \quad  A \cap B \cap C$

$ \quad \quad 1 \quad = \quad \quad \quad 1 +  0 +  0  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 2$

$ \quad \quad 1 \quad = \quad \quad \quad 0 +  0 +  1  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad0 \quad + \quad \quad 0 \quad \quad Element \quad 5$

$ \quad \quad 1 \quad = \quad \quad \quad 1  +  1 +  0  -  \quad \quad 1 \quad - \quad \quad 0 \quad - \quad \quad0 \quad + \quad \quad 0 \quad \quad Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad 0  +  1 +  0  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 7 $

$ \quad \quad 1 \quad = \quad \quad \quad 1  +  0 +  1  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad 0  +  1 +  1  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad 1  +  1 +  1  -  \quad \quad 1 \quad - \quad \quad 1 \quad - \quad \quad 1 \quad + \quad \quad 1 \quad \quad Element \quad 1$

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|C|$ , $|A \cap B|$ , $|A \cap C|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|C|$ , $|A \cap B|$ , $|B \cap C|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ принадлежит только $|C|$ и не принадлежит $|A|$ , $|B|$ , $|A \cap C|$ , $|B \cap C|$ то он посчитан один раз (в $|C|$ )

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

Если элемент $x$ принадлежит $|A \cap C|$ то он принадлежит и $|A|$ и $|C|$ и посчитан ровно $|A| + |C| - |A \cap C|$ раз ( в $|A|$ , в $|C|$ и в $|A \cap C|$ )

Если элемент $x$ принадлежит $|B \cap C|$ то он принадлежит и $|B|$ и $|C|$ и посчитан ровно $|B| + |C| - |B \cap C|$ раз ( в $|B|$ , в $|C|$ и в $|B \cap C|$ )

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он принадлежит и $|A|$ и $|B|$ и $|C|$ и $|A \cap B|$ и $|A \cap C|$ и $|B \cap C|$ и посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap C|$ )

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(Принадлежит C но не принадлежит A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит AB но не принадлежит C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит AC но не принадлежит B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит BC но не принадлежит A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано".

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


09/01/24
274
Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|A \cap B|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз ( в $|B|$ )

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

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$


$A \cup B \quad A \auad \quad B \quad A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - 0 \quad \quad Element \quad 2 $

$ \quad 1 \quad = \quad 1 + 0 \quad - 0 \quad \quad Element \quad 8 $

$ \quad 1 \quad = \quad 0 + 1 \quad - 0 \quad \quad Element \quad 7 $

$ \quad 1 \quad = \quad 0 + 1 \quad - 0 \quad \quad Element \quad 9 $

$ \quad 1 \quad = \quad 1 + 1 \quad - 1 \quad \quad Element \quad 1 $

$ \quad 1 \quad = \quad 1 + 1 \quad - 1 \quad \quad Element \quad 6 $

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|A \cap B|$ то он посчитан один раз ( в $|B|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит А но не принадлежит B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит B но не принадлежит A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B \cup C|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B \cup C|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|C|$ , $|A \cap B|$ , $|A \cap C|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|C|$ , $|A \cap B|$ , $|B \cap C|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ принадлежит только $|C|$ и не принадлежит $|A|$ , $|B|$ , $|A \cap C|$ , $|B \cap C|$ то он посчитан один раз (в $|C|$ )

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

Если элемент $x$ принадлежит $|A \cap C|$ то он принадлежит и $|A|$ и $|C|$ и посчитан ровно $|A| + |C| - |A \cap C|$ раз ( в $|A|$ , в $|C|$ и в $|A \cap C|$ )

Если элемент $x$ принадлежит $|B \cap C|$ то он принадлежит и $|B|$ и $|C|$ и посчитан ровно $|B| + |C| - |B \cap C|$ раз ( в $|B|$ , в $|C|$ и в $|B \cap C|$ )

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он принадлежит и $|A|$ и $|B|$ и $|C|$ и $|A \cap B|$ и $|A \cap C|$ и $|B \cap C|$ и посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


[$A \cup B \cup C \quad A \quad B \quad C \quad A \cap B \quad  A \cap C \quad B \cap C \quad  A \cap B \cap C$

$ \quad \quad 1 \quad = \quad \quad \quad 1 +  0 +  0  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 2$

$ \quad \quad 1 \quad = \quad \quad \quad 0 +  0 +  1  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad0 \quad + \quad \quad 0 \quad \quad Element \quad 5$

$ \quad \quad 1 \quad = \quad \quad \quad 1  +  1 +  0  -  \quad \quad 1 \quad - \quad \quad 0 \quad - \quad \quad0 \quad + \quad \quad 0 \quad \quad Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad 0  +  1 +  0  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 7 $

$ \quad \quad 1 \quad = \quad \quad \quad 1  +  0 +  1  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad 0  +  1 +  1  -  \quad \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad 1  +  1 +  1  -  \quad \quad 1 \quad - \quad \quad 1 \quad - \quad \quad 1 \quad + \quad \quad 1 \quad \quad Element \quad 1$

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ и не принадлежит $|B|$ , $|C|$ , $|A \cap B|$ , $|A \cap C|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ и не принадлежит $|A|$ , $|C|$ , $|A \cap B|$ , $|B \cap C|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ принадлежит только $|C|$ и не принадлежит $|A|$ , $|B|$ , $|A \cap C|$ , $|B \cap C|$ то он посчитан один раз (в $|C|$ )

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

Если элемент $x$ принадлежит $|A \cap C|$ то он принадлежит и $|A|$ и $|C|$ и посчитан ровно $|A| + |C| - |A \cap C|$ раз ( в $|A|$ , в $|C|$ и в $|A \cap C|$ )

Если элемент $x$ принадлежит $|B \cap C|$ то он принадлежит и $|B|$ и $|C|$ и посчитан ровно $|B| + |C| - |B \cap C|$ раз ( в $|B|$ , в $|C|$ и в $|B \cap C|$ )

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он принадлежит и $|A|$ и $|B|$ и $|C|$ и $|A \cap B|$ и $|A \cap C|$ и $|B \cap C|$ и посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap C|$ )

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(Принадлежит C но не принадлежит A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит AB но не принадлежит C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит AC но не принадлежит B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит BC но не принадлежит A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано"

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


07/08/23
1055
Elijah96 в сообщении #1651957 писал(а):
принадлежит $|A \cap B|$ то он принадлежит и $|A|$ и $|B|$ и посчитан ровно $|A| + |B| - |A \cap B|$ раз

Нет, потому что неизвестно, посчитан ли он в оставшихся слагаемых.

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


09/01/24
274
Так правильно будет?

Я воспользовался Вашим примером

dgwuqtj в сообщении #1651407 писал(а):
Наконец, если $x \in A \cap B$, то слева он посчитан 1 раз, а справа он будет учтён во всех трёх слагаемых, итого $1 + 1 - 1 = 1$. То есть тут перебор всех возможных случаев.


Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ то он посчитан один раз ( в $|B|$ )

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

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$


$A \cup B = A + B - A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 2 $

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 8 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 7 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 9 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 1 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 6 $

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ то он посчитан один раз ( в $|B|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит А но не принадлежит B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит B но не принадлежит A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ принадлежит $|A \cup B \cup C|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ не принадлежит $|A \cup B \cup C|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ принадлежит только $|A|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ принадлежит только $|C|$ то он посчитан один раз (в $|C|$ )

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

Если элемент $x$ принадлежит $|A \cap C|$ то он посчитан ровно $|A| + |C| - |A \cap C|$ раз ( в $|A|$ , в $|C|$ и в $|A \cap C|$ )

Если элемент $x$ принадлежит $|B \cap C|$ то он посчитан ровно $|B| + |C| - |B \cap C|$ раз ( в $|B|$ , в $|C|$ и в $|B \cap C|$ )

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он посчитан ровно ( $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


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

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1 +  0 +  0  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad  +\quad \quad 0 \quad \quad Element \quad 2$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0 +  0 +  1  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 5$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  0 \quad - \quad 1 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  0 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 7 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  0 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  1 \quad - \quad 1 \quad - \quad \quad 1 \quad - \quad \quad 1 \quad + \quad \quad 1 \quad \quad Element \quad 1$

Из таблицы видно что:

Если элемент $x$ принадлежит только $|A|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ принадлежит только $|B|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ принадлежит только $|C|$ то он посчитан один раз (в $|C|$ )

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

Если элемент $x$ принадлежит $|A \cap C|$ то он посчитан ровно $|A| + |C| - |A \cap C|$ раз ( в $|A|$ , в $|C|$ и в $|A \cap C|$ )

Если элемент $x$ принадлежит $|B \cap C|$ то он посчитан ровно $|B| + |C| - |B \cap C|$ раз ( в $|B|$ , в $|C|$ и в $|B \cap C|$ )

Если элемент $x$ принадлежит $|A \cap B \cap C|$ то он посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap C|$ )

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(Принадлежит А но не принадлежит B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(Принадлежит C но не принадлежит A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(Принадлежит AB но не принадлежит C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(Принадлежит B но не принадлежит A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(Принадлежит AC но не принадлежит B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(Принадлежит BC но не принадлежит A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(Принадлежит A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано"

А верна ли будет формула для n множеств по типу Вашей?

dgwuqtj в сообщении #1651371 писал(а):
$$\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: Формула включений/исключений
Сообщение27.08.2024, 18:42 
Заслуженный участник


07/08/23
1055
Уже лучше, но обороты в духе "$x$ принадлежит $|A \cap B|$" надо убирать.
Elijah96 в сообщении #1651977 писал(а):
А верна ли будет формула для n множеств по типу Вашей?

Так проверьте, вдруг докажется...

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


09/01/24
274
dgwuqtj в сообщении #1651981 писал(а):
Уже лучше, но обороты в духе "$x$ принадлежит $|A \cap B|$" надо убирать.


Подредактировал

Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ $\in$ $|A \cup B|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ $\notin$ $|A \cup B|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ только $x$ $\in$ $|A|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ только $x$ $\in$ $|B|$ то он посчитан один раз ( в $|B|$ )

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

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$


$A \cup B = A + B - A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 2 $

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 8 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 7 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 9 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 1 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 6 $

Из таблицы видно что:

Если элемент $x$ только $x$ $\in$ $|A|$ то он посчитан один раз ( в $|A|$ )

Если элемент $x$ только $x$ $\in$ $|B|$ то он посчитан один раз ( в $|B|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(2 $\in$ А и 2 $\notin$ B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ А и 8 $\notin$ B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(7 $\in$ B и 7 $\notin$ A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ B и 9 $\notin$ A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько каждый элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если элемент $x$ $\in$ $|A \cup B \cup C|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ $\notin$ $|A \cup B \cup C|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ только $x$ $\in$ $|A|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ только $x$ $\in$ $|B|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ только $x$ $\in$ $|C|$ то он посчитан один раз (в $|C|$ )

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

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

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

Если элемент $x$ $\in$ $|A \cap B \cap C|$ то он посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


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

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1 +  0 +  0  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad  +\quad \quad 0 \quad \quad Element \quad 2$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0 +  0 +  1  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 5$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  0 \quad - \quad 1 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  0 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 7 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  0 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  1 \quad - \quad 1 \quad - \quad \quad 1 \quad - \quad \quad 1 \quad + \quad \quad 1 \quad \quad Element \quad 1$

Из таблицы видно что:

Если элемент $x$ только $x$ $\in$ $|A|$ то он посчитан один раз (в $|A|$ )

Если элемент $x$ только $x$ $\in$ $|B|$ то он посчитан один раз (в $|B|$ )

Если элемент $x$ только $x$ $\in$ $|C|$ то он посчитан один раз (в $|C|$ )

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

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

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

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(2 $\in$ А и 2 $\notin$ B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(5 $\in$ C и 5 $\notin$ A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ AB и 6 $\notin$ C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(7 $\in$ B и 7 $\notin$ A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ AC и 8 $\notin$т B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ BC и 9 $\notin$ A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано"

dgwuqtj в сообщении #1651981 писал(а):
Так проверьте, вдруг докажется...


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

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


09/01/24
274
Дана формула для трех множеств

$|\cup \cap (A,B,C)| = |A \cap B| + |A \cap C| + |B \cap C| - 2|A \cap B \cap C|$

Где:

$|\cup \cap (A,B,C)|$ - Мощность объединения всевозможных пересечений множеств A,B,C

В левой части равенства:

Если элемент $x$ $\in$ $|\cup \cap (A,B,C)|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если элемент $x$ $\notin$ $|\cup \cap (A,B,C)|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если элемент $x$ $\in$ $|A \cap B|$ то он посчитан ровно один раз ( в $|A \cap B|$ )

Если элемент $x$ $\in$ $|A \cap C|$ то он посчитан ровно один раз ( в $|A \cap C|$ )

Если элемент $x$ $\in$ $|B \cap C|$ то он посчитан ровно один раз ( в $|B \cap C|$ )

Если элемент $x$ $\in$ $|A \cap B \cap C|$ то он посчитан ровно $|A \cap B| + |A \cap C| + |B \cap C| - 2|A \cap B \cap C|$ раз ( в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


$\cup \cap (A,B,C) =  A \cap B +  A \cap C + B \cap C -  2 A \cap B \cap C$


$ \quad \quad 1 \quad = \quad \quad \quad \quad \quad \; 1   \quad + \quad 0 \quad + \quad \quad 0 \quad - \quad \quad 0 \quad \quad \quad  Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad \quad \quad \; 0  \quad + \quad 1 \quad + \quad \quad 0 \quad - \quad \quad 0 \quad  \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad \quad \; 0  \quad + \quad 0 \quad + \quad \quad 1 \quad - \quad \quad 0 \quad \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad \quad \quad \;1   \quad + \quad 1 \quad + \quad \quad 1 \quad - \quad \quad 0 \quad  \quad \quad Element \quad 1$

Из таблицы видно что:

Если элемент $x$ $\in$ $|A \cap B|$ то он посчитан ровно один раз ( в $|A \cap B|$ )

Если элемент $x$ $\in$ $|A \cap C|$ то он посчитан ровно один раз ( в $|A \cap C|$ )

Если элемент $x$ $\in$ $|B \cap C|$ то он посчитан ровно один раз ( в $|B \cap C|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0+0-0=0 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ AB)
1=0+1+0-0-0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ AC)
1=0+0+1-0-0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ BC)
1=1+1+1+1-2=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1=1+1+1+1 $\Rightarrow$ 4=4

Значит мощность объединения $|\cup \cap (A,B,C)|$ в левой части равенства,равна слагаемым мощностям $|A \cap B| + |A \cap C| + |B \cap C| - 2|A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано"

(Только непонятно откуда 2 перед $2|A \cap B \cap C|$ )

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


07/08/23
1055
Elijah96 в сообщении #1651988 писал(а):
Чтобы проверить Вашу формулу то нужно доказать формулу включений\исключений,что у меня мягко говоря,пока не получается

Для трёх множеств ведь получилось. Но для $n$ множеств придётся использовать что-то вроде индукции, вы ведь не будете писать бесконечно много таких рассуждений для каждого $n$.
Elijah96 в сообщении #1652084 писал(а):
Если элемент $x$ $\notin$ $|A \cup B \cup C|$

Ну не могут элементы принадлежать числам.
Elijah96 в сообщении #1652084 писал(а):
В правой части равенства:

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

В правой части этого равенства я не вижу $|A|$ и $|B|$.
Elijah96 в сообщении #1652084 писал(а):
$ \quad \quad 1 \quad = \quad \quad \quad  0  \quad + \quad 0 \quad + \quad \quad 0 \quad - \quad \quad 1 \quad  \quad \quad Element \quad 8 $

Вы коэффициент 2 забыли...
Elijah96 в сообщении #1652084 писал(а):
Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства

В левой части нет $|A \cup B \cup C|$.

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


09/01/24
274
dgwuqtj в сообщении #1652086 писал(а):
В правой части этого равенства я не вижу $|A|$ и $|B|$.
Elijah96 в сообщении #1652084

писал(а):
$ \quad \quad 1 \quad = \quad \quad \quad  0  \quad + \quad 0 \quad + \quad \quad 0 \quad - \quad \quad 1 \quad  \quad \quad Element \quad 8 $
Вы коэффициент 2 забыли...
Elijah96 в сообщении #1652084

писал(а):
Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства
В левой части нет $|A \cup B \cup C|$.


Это откуда Вы взяли?
Я запутался

-- 28.08.2024, 13:09 --

dgwuqtj в сообщении #1652086 писал(а):
Для трёх множеств ведь получилось. Но для $n$ множеств придётся использовать что-то вроде индукции, вы ведь не будете писать бесконечно много таких рассуждений для каждого $n$.


Следовательно доказать я ее не смогу,как и говорил раннее

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


07/08/23
1055
Elijah96 в сообщении #1652088 писал(а):
Это откуда Вы взяли?

Из вашего последнего сообщения и взял. Прочитайте его сами, вдумчиво.
Elijah96 в сообщении #1652088 писал(а):
Следовательно доказать я ее не смогу,как и говорил раннее

Или можно освоить математическую индукцию. Это полезно.

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


09/01/24
274
Так лучше?

Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если $x$ $\in$ $|A \cup B|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если $x$ $\notin$ $|A \cup B|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если $x$ только $x$ $\in$ $|A|$ то он посчитан один раз ( в $|A|$ )

Если $x$ только $x$ $\in$ $|B|$ то он посчитан один раз ( в $|B|$ )

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

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$


$A \cup B = A + B - A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 2 $

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 8 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 7 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 9 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 1 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 6 $

Из таблицы видно что:

Если $x$ только $x$ $\in$ $|A|$ то он посчитан один раз ( в $|A|$ )

Если $x$ только $x$ $\in$ $|B|$ то он посчитан один раз ( в $|B|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(2 $\in$ А и 2 $\notin$ B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ А и 8 $\notin$ B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(7 $\in$ B и 7 $\notin$ A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ B и 9 $\notin$ A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если $x$ $\in$ $|A \cup B \cup C|$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если $x$ $\notin$ $|A \cup B \cup C|$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если $x$ только $x$ $\in$ $|A|$ то он посчитан один раз (в $|A|$ )

Если $x$ только $x$ $\in$ $|B|$ то он посчитан один раз (в $|B|$ )

Если $x$ только $x$ $\in$ $|C|$ то он посчитан один раз (в $|C|$ )

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

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

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

Если $x$ $\in$ $|A \cap B \cap C|$ то он посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


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

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1 +  0 +  0  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad  +\quad \quad 0 \quad \quad Element \quad 2$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0 +  0 +  1  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 5$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  0 \quad - \quad 1 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  0 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 7 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  0 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  1 \quad - \quad 1 \quad - \quad \quad 1 \quad - \quad \quad 1 \quad + \quad \quad 1 \quad \quad Element \quad 1$

Из таблицы видно что:

Если $x$ только $x$ $\in$ $|A|$ то он посчитан один раз (в $|A|$ )

Если $x$ только $x$ $\in$ $|B|$ то он посчитан один раз (в $|B|$ )

Если $x$ только $x$ $\in$ $|C|$ то он посчитан один раз (в $|C|$ )

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

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

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

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(2 $\in$ А и 2 $\notin$ B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(5 $\in$ C и 5 $\notin$ A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ AB и 6 $\notin$ C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(7 $\in$ B и 7 $\notin$ A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ AC и 8 $\notin$т B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ BC и 9 $\notin$ A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано"

-- 28.08.2024, 13:16 --

dgwuqtj в сообщении #1652086 писал(а):
В правой части этого равенства я не вижу $|A|$ и $|B|$.


А зачем там $|A|$ и $|B|$ ?

Ведь элемент 8 принадлежит $|A \cap C|$

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


07/08/23
1055
К этим доказательствам у меня только одна претензия: что вы путаете множества и их мощности, пишите везде эти странные $x \in |A|$... Таблицу, конечно, в доказательство включать не надо, это вас просили сделать, чтобы вы сами поняли рассуждения.
Elijah96 в сообщении #1652091 писал(а):
А зачем там $|A|$ и $|B|$ ?

Не знаю, они там были до исправления зачем-то...

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


09/01/24
274
dgwuqtj в сообщении #1652094 писал(а):
Elijah96 в сообщении #1652091

писал(а):
А зачем там $|A|$ и $|B|$ ?
Не знаю, они там были до исправления зачем-то...


Я таблицу сделал,а потом исправлял ошибки,чтобы было видно что,где и как

-- 28.08.2024, 13:30 --

dgwuqtj в сообщении #1652094 писал(а):
К этим доказательствам у меня только одна претензия: что вы путаете множества и их мощности, пишите везде эти странные $x \in |A|$... Таблицу, конечно, в доказательство включать не надо, это вас просили сделать, чтобы вы сами поняли рассуждения.


Все
Дошло
Сейчас

Дано равенство для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Для "доказательства" равенства для двух множеств нужно посчитать,сколько каждый $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если $x$ $\in$ $A \cup B$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если $x$ $\notin$ $A \cup B$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если $x$ только $x$ $\in$ $A$ то он посчитан один раз ( в $|A|$ )

Если $x$ только $x$ $\in$ $B$ то он посчитан один раз ( в $|B|$ )

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

Нарисуем таблицу чтобы было проще разобраться:

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

$A \cap B = \lbrace 1,6 \rbrace $

$A \cup B = \lbrace 1,2,6,7,8,9 \rbrace$


$A \cup B = A + B - A \cap B$

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 2 $

$ \quad 1 \quad = \quad 1 + 0 \quad - \quad 0 \quad \quad Element \quad 8 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 7 $

$ \quad 1 \quad = \quad 0 + 1 \quad - \quad 0 \quad \quad Element \quad 9 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 1 $

$ \quad 1 \quad = \quad 1 + 1 \quad - \quad 1 \quad \quad Element \quad 6 $

Из таблицы видно что:

Если $x$ только $x$ $\in$ $A$ то он посчитан один раз ( в $|A|$ )

Если $x$ только $x$ $\in$ $B$ то он посчитан один раз ( в $|B|$ )

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 2(2 $\in$ А и 2 $\notin$ B и AB)
1=1+0-0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ А и 8 $\notin$ B и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 7(7 $\in$ B и 7 $\notin$ A и AB)
1=0+1-0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ B и 9 $\notin$ A и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ и A и B и AB)
1=1+1-1=1 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ и A и B и AB)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1=1+1+1+1+1+1 $\Rightarrow$ 6=6

Значит мощность объединения $|A \cup B|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| - |A \cap B|$ в правой части равенства.

Равенство для двух множеств "доказано".

Дано равенство для трех множеств:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Для "доказательства" равенства для трех множеств нужно посчитать,сколько элемент $x$ посчитан в мощностях множеств в левой и правой части равенства.

В левой части равенства:

Если $x$ $\in$ $A \cup B \cup C$ то он посчитан один раз(поскольку в объединении,каждый элемент учитывается по одному разу)

Если $x$ $\notin$ $A \cup B \cup C$ то он посчитан нуль раз(поскольку его нет в объединении)

В правой части равенства:

Если $x$ только $x$ $\in$ $A$ то он посчитан один раз (в $|A|$ )

Если $x$ только $x$ $\in$ $B$ то он посчитан один раз (в $|B|$ )

Если $x$ только $x$ $\in$ $C$ то он посчитан один раз (в $|C|$ )

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

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

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

Если $x$ $\in$ $A \cap B \cap C$ то он посчитан ровно $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ раз ( в $|A|$ , в $|B|$ , в $|C|$ , в $|A \cap B|$ , в $|A \cap C|$ ,
в $|B \cap C|$ и в $|A \cap B \cap 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$

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


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

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1 +  0 +  0  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad  +\quad \quad 0 \quad \quad Element \quad 2$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0 +  0 +  1  \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 5$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  0 \quad - \quad 1 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 6$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  0 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 0 \quad + \quad \quad 0 \quad \quad Element \quad 7 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  0 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 8 $

$ \quad \quad 1 \quad = \quad \quad \quad \quad 0  +  1 +  1 \quad - \quad 0 \quad - \quad \quad 0 \quad - \quad \quad 1 \quad + \quad \quad 0 \quad \quad Element \quad 9$

$ \quad \quad 1 \quad = \quad \quad \quad \quad 1  +  1 +  1 \quad - \quad 1 \quad - \quad \quad 1 \quad - \quad \quad 1 \quad + \quad \quad 1 \quad \quad Element \quad 1$

Из таблицы видно что:

Если $x$ только $x$ $\in$ $A$ то он посчитан один раз (в $|A|$ )

Если $x$ только $x$ $\in$ $B$ то он посчитан один раз (в $|B|$ )

Если $x$ только $x$ $\in$ $C$ то он посчитан один раз (в $|C|$ )

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

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

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

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

Что подтверждает то,что написано выше для правой части формулы

Тогда:

1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 2(2 $\in$ А и 2 $\notin$ B,C,AB,AC,BC,ABC)
1=1+0+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 5(5 $\in$ C и 5 $\notin$ A,B,AB,AC,BC,ABC)
1=1+1+0-1-0-0+0=1 $\Rightarrow$ 1=1 Элемент 6(6 $\in$ AB и 6 $\notin$ C,AC,BC,ABC)
1=0+1+0-0-0-0+0=1 $\Rightarrow$ 1=1 Элемент 7(7 $\in$ B и 7 $\notin$ A,C,AB,AC,BC,ABC)
1=1+0+1-0-1-0+0=1 $\Rightarrow$ 1=1 Элемент 8(8 $\in$ AC и 8 $\notin$т B,AB,BC,ABC)
1=0+1+1-0-0-1+0=1 $\Rightarrow$ 1=1 Элемент 9(9 $\in$ BC и 9 $\notin$ A,AB,AC,ABC)
1=1+1+1-1-1-1+1=1 $\Rightarrow$ 1=1 Элемент 1(1 $\in$ A,B,C,AB,AC,BC,ABC)

Далее складываем все единицы в левой и правой части:

Получается:
1+1+1+1+1+1+1=1+1+1+1+1+1+1 $\Rightarrow$ 7=7

Значит мощность объединения $|A \cup B \cup C|$ в левой части равенства,равна слагаемым мощностям $|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ в правой части равенства.

Равенство для трех множеств "доказано"

Так?

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

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



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

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


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

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