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  След.

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



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

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


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

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