bulgakov

04. Распределительные законы и число элементов объединения

Что пригодится из прошлого: объединение и пересечение множеств; двоичные коды — для проверки по областям. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

1. Распределительные законы

Для любых множеств A,B,CA,B,C верны два равенства:

A∪(B∩C)=(A∪B)∩(A∪C),\boxed{A\cup(B\cap C)=(A\cup B)\cap(A\cup C)}, A∩(B∪C)=(A∩B)∪(A∩C).\boxed{A\cap(B\cup C)=(A\cap B)\cup(A\cap C)}.

Мысль за первой формулой: элемент AA проходит в обе части сразу. Если элемента нет в AA, ему нужно находиться одновременно в BB и CC. Во второй формуле элемент должен быть в AA и хотя бы в одном из B,CB,C; значит, он окажется в одном из двух пересечений справа.

Например, при A={1}A=\{1\}, B={2,3}B=\{2,3\}, C={3,4}C=\{3,4\} получаем

B∩C={3},A∪(B∩C)={1,3},B\cap C=\{3\},\qquad A\cup(B\cap C)=\{1,3\},

а справа:

A∪B={1,2,3},A∪C={1,3,4},(A∪B)∩(A∪C)={1,3}.A\cup B=\{1,2,3\},\quad A\cup C=\{1,3,4\},\quad (A\cup B)\cap(A\cup C)=\{1,3\}.

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

Доказательство первого закона

Возьмём произвольный x∈A∪(B∩C)x\in A\cup(B\cap C). Если x∈Ax\in A, он входит и в A∪BA\cup B, и в A∪CA\cup C. Если x∉Ax\notin A, его принадлежность левой части означает x∈B∩Cx\in B\cap C; тогда он снова входит в оба объединения. Следовательно,

A∪(B∩C)⊆(A∪B)∩(A∪C).A\cup(B\cap C)\subseteq(A\cup B)\cap(A\cup C).

Для обратного включения возьмём x∈(A∪B)∩(A∪C)x\in(A\cup B)\cap(A\cup C). Если x∈Ax\in A, он уже в A∪(B∩C)A\cup(B\cap C). Если x∉Ax\notin A, из x∈A∪Bx\in A\cup B следует x∈Bx\in B, а из x∈A∪Cx\in A\cup C следует x∈Cx\in C. Значит, x∈B∩Cx\in B\cap C, а потому x∈A∪(B∩C)x\in A\cup(B\cap C). Обратное включение доказано; множества равны.

Доказательство второго закона

Если x∈A∩(B∪C)x\in A\cap(B\cup C), то xx обязательно находится в AA, а внутри скобок требуется хотя бы одно: x∈Bx\in B или x∈Cx\in C. Если он в BB, получаем x∈A∩Bx\in A\cap B; если в CC, получаем x∈A∩Cx\in A\cap C. Даже если он в обоих, условие объединения справа выполнено. Значит, x∈(A∩B)∪(A∩C)x\in(A\cap B)\cup(A\cap C).

Обратно, если xx входит в одно из пересечений A∩BA\cap B, A∩CA\cap C, то x∈Ax\in A и одновременно x∈B∪Cx\in B\cup C. Следовательно, x∈A∩(B∪C)x\in A\cap(B\cup C). Оба включения доказаны.

Ещё одна проверка: по областям

Три множества делят все элементы на 88 областей — по тому, в каких из множеств лежит элемент. Код 110110 означает «в AA и в BB, но не в CC» (это та же идея кодов, что в первой главе). Для каждой области проверим обе части обоих законов; если в каждой строке отметки совпадают, множества равны:

Код В AA? В BB? В CC? A∪(B∩C)A\cup(B\cap C) (A∪B)∩(A∪C)(A\cup B)\cap(A\cup C) A∩(B∪C)A\cap(B\cup C) (A∩B)∪(A∩C)(A\cap B)\cup(A\cap C)
000 нет нет нет — — — —
001 нет нет да — — — —
010 нет да нет — — — —
011 нет да да ✓ ✓ — —
100 да нет нет ✓ ✓ — —
101 да нет да ✓ ✓ ✓ ✓
110 да да нет ✓ ✓ ✓ ✓
111 да да да ✓ ✓ ✓ ✓

Первые два столбца совпадают во всех восьми строках — это первый закон; два последних — второй закон. Каждый элемент попадает ровно в одну область, поэтому этой проверки достаточно.

2. Число элементов объединения

Для конечных множеств действует формула

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣.\boxed{|A\cup B|=|A|+|B|-|A\cap B|}.

Здесь ∣A∣|A| — число элементов AA. При сложении ∣A∣+∣B∣|A|+|B| каждый общий элемент посчитан дважды. Вычитая ∣A∩B∣|A\cap B|, убираем только лишний подсчёт: сам общий элемент остаётся в объединении.

Например, если A={1,2,3,4}A=\{1,2,3,4\}, B={3,4,5}B=\{3,4,5\}, то ∣A∣=4|A|=4, ∣B∣=3|B|=3, A∩B={3,4}A\cap B=\{3,4\}. Поэтому

∣A∪B∣=4+3−2=5,|A\cup B|=4+3-2=\boxed{5},

что совпадает с A∪B={1,2,3,4,5}A\cup B=\{1,2,3,4,5\}. Если общих элементов нет, ∣A∩B∣=0|A\cap B|=0 и получаем ∣A∪B∣=∣A∣+∣B∣|A\cup B|=|A|+|B|.

Эта формула — начало принципа включений и исключений: для трёх множеств и для любого числа множеств он разобран в главах про два и три множества и формулу для nn множеств.

Проверь себя

1. Для конечных множеств ∣A∣=12|A|=12, ∣B∣=9|B|=9, ∣A∩B∣=4|A\cap B|=4. Найдите ∣A∪B∣|A\cup B|.

Решение

В сумме 12+912+9 четыре общих элемента посчитаны дважды; вычитаем одно из этих повторений: 12+9−4=1712+9-4=17.

2. Проверьте первый распределительный закон для A={1,2}A=\{1,2\}, B={2,3}B=\{2,3\}, C={3,4}C=\{3,4\}.

Решение

Слева: B∩C={3}B\cap C=\{3\}, поэтому A∪(B∩C)={1,2,3}A\cup(B\cap C)=\{1,2,3\}. Справа: A∪B={1,2,3}A\cup B=\{1,2,3\}, A∪C={1,2,3,4}A\cup C=\{1,2,3,4\}, их пересечение {1,2,3}\{1,2,3\}. Обе части равны {1,2,3}\{1,2,3\}.

ПрактикаЗагружаем тест…