МОЩНОСТЬ КОНЕЧНОГО МНОЖЕСТВА

Пусть задано некоторое множество А. Количество элементов данного множества называется его мощностью и обозначается символом ç А ç.

Очевидно, что пустое множество имеет мощность, равную нулю, то есть çÆç= 0.

Как могут меняться мощности множеств при операциях, производимых над ними? Точного ответа на этот вопрос нет, так как всё будет зависеть от взаимного расположения множеств.

Рассмотрим три возможных случая расположения двух непустых множеств А и В.

Рассмотрим множество, равное объединению А È В. Какова же будет его мощность в каждом из возможных трёх случаях.

Случай 1. Множества не пересекаются, то есть çАÇВç= 0. Тогда çАÈВç£ çАç + çВç. Иными словами, мощность объединения (суммы) множеств не превышает суммы их мощностей.

Случай 2. Множества пересекаются. Тогда çАÈВç= çАç + çВç- çАÇВç, то есть мощность объединения двух пересекающихся множеств равна сумме их мощностей без мощности их общей части (их пересечения).

Эта формула носит название формулы включений и исключений. С её помощью можно вычислить мощность любого множества.

Случай 3. Множество В включено в множество А, то есть имеет место включение В Ì А. Очевидно, что здесь çАÈВç = çАç, то есть мощность объединения подмножества и множества будет равно мощности самого множества. В случае, если А Ì В, то çАÈВç = çВç.

Обобщая эти три случая, получаем для объединения: çАÈВç £çАç + çВ.ç

Рассмотрим множество, равное пересечению А Ç В. Какова же будет его мощность в каждом из возможных трёх случаях.

Случай 1. çАÇВç = çÆç = 0.

Случай 2. çАÇВç = çАÈВç- çАç- çВç.

Случай 3. çАÇВç = çВç.

Обобщая эти три случая, получаем для пересечения: 0 £ çАÇВç £ çВç.

Рассмотрим множество, равное дополнению множества А. Поскольку Ā; = V\А, то çĀç = çVç - çАç.

Рассмотрим множество, равное разности А \ В.

Случай 1. Здесь А\В = А, тогда и çА\Вç = çАç.

Случай 2. çА\Вç = çAÈBç - çBç.

Случай 3. çА\Вç = çAç - çВç.

Рассмотрим множество, равное симметрической разности А ¸ В.

Случай 1. Здесь А¸В = АÈB, тогда и çА¸Вç = çАÈBç= |A| + |B|.

Случай 2. çА¸Вç = çА\Bç + çВ\Aç = çAç + çBç -2çAÇBç=

= 2çAÈBç - (çAç + çBç).

Случай 3. Здесь А¸В = А\В, поэтому çА¸Вç = çAç - çВç.

 

Задача 4.1.1. А = {1, 2, 3, 4, 5}; B = {4, 5, 6, 7}. Найти мощности указанных множеств.

Решение.

çAç = 5, çBç = 4, AÇB = {4, 5}, çAÇBç = 2, тогда

çAÈBç= çАç + çВç- çАÇВ| = 5 + 4 – 2 = 7.

A\B = {1, 2, 3}, |A\B| = |A| - |AÇB| = 5 – 2 = 3. B\A = {6, 7},

|B\A| = |B| - |AÇB| = 4 – 2 = 2.

A¸B = {1, 2, 3, 6, 7}, |A¸B| = çА\Вç - çВ\Аç = 3 + 2 = 5.

 

Задача 4.1.2. В одном канадском городе жители говорят на английском и французском языках. На английском говорят 90% жителей, на французском ‑ 80%. Сколько процентов жителей города говорят на обоих языках и на одном языке?

Решение. Пусть множество А – множество говорящих по-английски, В – говорящих по-французски. Тогда А\В – это множество жителей, которые говорят только по-английски, В\А – по-французски, а АÇВ – на обоих языках. АÈВ – это множество всех жителей города.

Из условия задачи получаем:

çAç = 90, çВç = 80, çАÈВç= 100.

Так как çAÈBç = çАç + çВç - çAÇBç. Отсюда çAÇBç = çАç + çВç- çAÈBç, и çAÇBç = 90 + 80 - 100 = 70. На обоих языках говорят 70% жителей.

На одном английском говорят çA\Вç= çAç- çAÇBç= 90 - 70 = 20 процентов, только на французском çB\Аç= çBç- çAÇBç = 80 - 70 = 10 процентов жителей.

 

Задача 4.1.3. В отряде из сорока ребят 30 умеют плавать, 27 умеют играть в шахматы и только пятеро не умеют ни того, ни другого. Сколько ребят умеют плавать и играть в шахматы?

Решение. Пусть А – множество умеющих плавать, В – множество играющих в шахматы. Универсальное множество V – это весь отряд. Те же, кто не умеет ни того, ни другого – это множество, равное дополнению к АÈВ или V\(АÈВ). Имеем: çАç=30, çВç=27, çVç=40, çV\(AÈBç=5.

çĀç= çVç-çAç=40-30=10 – это те, кто не плавает (играет в шахматы или ничего не умеет); – это те, кто не играет в шахматы (плавает или ничего не умеет). Те, кто только играет в шахматы – множество В\А мощностью 10-5=5, множество А\В – это умеющие плавать. Их количество равно 13-5=8.Так как çV\(AÈBç=çVç-çAÈBç=5, отсюда çAÈBç=çVç-5=40-5=35. По формуле включений и исключений çАÈВç= çАç + çВç- çАÇВç получим, что 35=5+8-çАÇВç, откуда çАÇВç=22.

Задача 4.1.4. Из 100 деталей на первом станке обработано 42 штуки, на втором – 30, на третьем – 28 шт. При этом на первом и втором станках обработано всего 5 деталей, на первом и третьем – 10, на втором и третьем – 8. На всех трёх станках обработано 3 детали.

Сколько деталей обработано на первом станке и сколько деталей не обработано ни на одном станке?

Решение. Пусть А – множество деталей, обработанных на 1-м станке; В – на 2-м; С – на 3-м. Универсум V – множество всех деталей в задаче. Очевидно, что |V| = 100, |A| = 42, |B| = 30, |C| = 28.

Метка 1 соответствует множеству АÇВÇС – это детали, обработанные хотя бы на одном станке (либо на одном, либо на двух, либо на трёх). Мощность его çАÇВÇСç = 3.

Метки 1 и 2– детали, обработанные на 1 и 2-м станках. Это множество АÇВ. Его мощность по условию çАÇВç= 5.

Метки 1 и 3 – детали, обработанные на 2-м и 3-м станках, множество АÇС, çАÇСç= 10, а метки 1 и 4 – на 2-м и 3-м станках, множество ВÇС, çВÇСç= 8.

Метка 2 соответствует множеству деталей, которые обработаны только на 1-м и 2-м станках. Это множество (АÇВ)\С, мощность которого находим так: çАÇВç-çАÇВÇСç= 5-3=2.

Метка 3 – детали, обработанные на 1-м и 3-м станках. Это множество (АÇС)\В, мощность которого равна çАÇСç- çАÇВÇС ç= 10-3=7.

Метка 4 - множество деталей, обработанных на 2-м 3-м станках. Это множество (ВÇС)\А. Его мощность çВÇСç- çАÇВÇСç= 8-3=5.

Детали, которые обрабатывались только на одном первом станке ‑ множество с меткой 5, равное разности множества А и множеств с метками 1, 2 и 3. Мощность этого множества (метка 5) равна çАç-(çм.1ç+çм.2ç+çм.3ç) = 42-(3+2+7) = 30.

Множество с меткой 6 – детали, обработанные только на втором станке. Его мощность равна çВç-(çм.1ç+çм.2ç+çм.4ç) = 30-(3+2+5) = 20.

Множество с меткой 7 – детали, обработанные только на третьем станке. Его мощность равна çСç-(çм.1ç+çм.3ç+çм.4ç) = 28-(3+7+5) = 13.

АÈВÈС – множество всех обработанных деталей. Его мощность можно найти как сумму мощностей всех семи множеств: çАÇВÇСç = 3+2+7+5++30+20+13 = 80.

– множество всех необработанных деталей. Его мощность вычислим так:

.

Итак, на 1-м станке обработано 30 деталей, вообще не обрабатывалось 20 деталей.

Задачи для самостоятельного решения.

1. В классе 40 учеников. 30 из них могут плавать, 27 – играть в шахматы, а пятеро не умеют ни того, ни другого. Сколько учеников могут плавать и играть в шахматы? (ответ:22).

2. На протяжении недели в кинотеатре демонстрировались фильмы А, В и С. Из 40 учеников каждый посмотрел либо все три фильма, либо только один из трёх. Фильм А посмотрели 13 человек, фильм В – 16, фильм С – 19. Сколько учеников посмотрели все три фильма? (ответ: 3).