ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.12.2020
Просмотров: 2161
Скачиваний: 53
40
Глава I. Множества и действия над ними
мы обозначаем пустое множество, через
I
— универсальное мно-
жество, через
A
0
— дополнение множества
A
в универсальном
множестве).
1)
A
⊂
A
.
2) Если
A
⊂
B
и
B
⊂
A
, то
A
=
B
.
3) Если
A
⊂
B
и
B
⊂
C
, то
A
⊂
C
.
4)
∅
⊂
A
.
5)
A
⊂
I
.
6)
A
+
B
=
B
+
A
.
7)
AB
=
BA
.
8)
A
+ (
B
+
C
) = (
A
+
B
) +
C
.
9)
A
(
BC
) = (
AB
)
C
.
10)
A
+
A
=
A
.
11)
AA
=
A
.
12)
A
(
B
+
C
) =
AB
+
AC
.
13)
A
+
BC
= (
A
+
B
)(
A
+
C
)
.
14)
A
+
∅
=
A
.
15)
AI
=
A
.
16)
A
+
I
=
I
.
17)
A
∅
=
∅
.
18) Соотношение
A
⊂
B
эквивалентно каждому из соотношений
A
+
B
=
B
,
AB
=
A
.
19)
A
+
A
0
=
I
.
20)
AA
0
=
∅
.
21)
∅
0
=
I
.
22)
I
0
=
∅
.
23)
(
A
0
)
0
=
A
.
24) Соотношение
A
⊂
B
эквивалентно
B
0
⊂
A
0
.
25)
(
A
+
B
)
0
=
A
0
B
0
.
26)
(
AB
)
0
=
A
0
+
B
0
.
Отметим следующее замечательное «соотношение двойственно-
сти». Если в каждом из свойств 1)–26) заменить друг на друга сим-
волы «
⊂
» и «
⊃
», «
∅
» и «
I
», «
+
» и «
·
», то в результате получится
снова одно из этих свойств. Например, таким путем из свойства 6)
получается свойство 7), из свойства 12) — свойство 13) и т. д.
Отсюда вытекает, что каждой теореме, которая может быть вы-
ведена из свойств 1)–26), соответствует другая «двойственная» ей
теорема, получающаяся из первой посредством указанных переста-
новок символов.
Планета мифов
41
Разумеется, запомнить все свойства 1)–26) не слишком легко.
Но это и не нужно. Дело в том, что можно ограничиться двумя
основными операциями: сложением множеств и образованием допол-
нения, потребовав, чтобы выполнялись следующие три соотношения:
а)
A
+
B
=
B
+
A
,
б)
(
A
+
B
) +
C
=
A
+ (
B
+
C
)
,
в)
(
A
0
+
B
0
)
0
+ (
A
0
+
B
)
0
=
A
.
Определим теперь действие умножения
AB
, соотношение вклю-
чения
A
⊂
B
и множества
I
,
∅
формулами
г)
AB
по определению равно
(
A
0
+
B
0
)
0
;
д)
A
⊂
B
по определению означает, что
A
+
B
=
B
;
е)
I
=
A
+
A
0
,
∅
=
I
0
.
Тогда все свойства 1)–26) вытекают из формул а)–е).
Планета мифов
Однажды во время беседы за чашкой кофе в клубе Межгалакти-
ческих путешественников знаменитый член этого клуба, Мюнхгаузен
космической эры, Йон Тихий
1
рассказал:
«Высадка на планету Гесиод была очень трудна. Но когда я ока-
зался на поверхности, то пожалел, что решил опуститься: на ней
жили чудовища, более страшные, чем описанные в древних мифах
греков. Навстречу мне вышла делегация из 1000 жителей планеты.
У 811 из них был один глаз, как у циклопа Полифема, у 752 — вместо
волос были змеи, как у Медузы Горгоны, а 418 имели рыбий хвост,
как нереиды. При этом 570 чудовищ были одноглазы и змееволосы,
356 — одноглазы и имели рыбий хвост, 348 — змееволосы и с ры-
бьим хвостом, а 297 — одноглазы, змееволосы и с рыбьим хвостом.
Старший из них обратился ко мне и сказал...»
Но члены клуба так и не узнали, что услышал Йон Тихий на пла-
нете чудовищ. Слушавший рассказ путешественника профессор Та-
рантога мгновенно произвел в уме какие-то выкладки и воскликнул:
«Дорогой Йон! Я готов поверить, что на этой планете жили суще-
ства с одним глазом, со змеями вместо волос и с рыбьими хвостами.
1
Путешествия Йона Тихого описаны известным польским писателем-фанта-
стом Станиславом Лемом в «Звездных дневниках Иона Тихого». Автор «Рас-
сказов о множествах» надеется, что С. Лем простит ему неумелую попытку
подражания, а читатели не будут обвинять С. Лема в литературных недочетах
изложения автора.
42
Глава I. Множества и действия над ними
Тебе приходилось встречать еще более страшных чудовищ — вспом-
ни о курдлях. Но я надеюсь, что законы математики на этой планете
не превратились в мифы».
И Тарантога взял со стола бумажную салфетку и нарисовал
на ней следующую схему (рис. 20). Он сказал:
«Обозначим через
I
множество всех членов делегации, через
A
—
множество одноглазых, через
B
— множество змееволосых делега-
Рис. 20
тов, а через
C
— имеющих рыбьи
хвосты. Эти множества изображены
на рис. 20 в виде кругов. Три круга де-
лят прямоугольник на 8 частей. Подсчи-
таем, сколько элементов входит в каж-
дую часть. По условию в множество
AB
(то есть одноглазых и змееволосых) вхо-
дило 570 существ, а в множество
ABC
(одноглазых, змееволосых и с рыбьими
хвостами) — 297. Значит, в множество
AB
−
ABC
входит 273 существа. Это
то самое множество, которое на рис. 20
заштриховано горизонтальными линия-
ми. Точно так же находим, что множе-
ство
AC
−
ABC
состоит из 59 существ (это множество на рис. 20
заштриховано вертикальными линиями), а множество
BC
−
ABC
—
из 51 существа (это множество заштриховано косыми линиями).
Теперь уже легко найти численность части множества
A
, не при-
надлежащей
B
+
C
. Для этого из 811 надо вычесть 570 (численность
множества
AB
) и еще 59 (численность множества
AC
−
ABC
). Оста-
нется 182 существа, которые одноглазы, но не имеют ни змей на голо-
ве, ни рыбьих хвостов. Точно так же устанавливаем, что численность
множества
B
−
(
A
+
C
)
равна 131, а множества
C
−
(
A
+
B
)
равна 11.
Результаты подсчетов изображены на рис. 21.
Подсчитаем теперь, сколько же членов делегации не были ни од-
ноглазыми, ни змееволосыми и не имели рыбьих хвостов, то есть
сколько элементов содержит множество
I
−
A
−
B
−
C
. Так как от-
дельные множества на рис. 21 не пересекаются, то для этого на-
до просто отнять от 1000 сумму
297 + 273 + 59 + 51 + 182 + 131 + 11
.
Но эта сумма равна 1004, и потому множество
I
−
A
−
B
−
C
насчи-
тывает
−
4
существа. Но согласись сам, дорогой Йон, даже на планете
мифов ни одно множество не может иметь отрицательной численно-
сти. Даже для тебя такие выдумки слишком невероятны».
Планета мифов
43
Рис. 21
Рис. 22
F
Оставим Йона Тихого объясняться с профессором Таран-
тогой (скоро мы снова встретимся с нашим героем) и сделаем
несколько замечаний. Мы разложили все множество
I
на 8 подмно-
жеств и нашли их численность. Смысл этого разложения состоял
в том, что полученные подмножества попарно не пересекались.
Но это же разложение можно было бы получить иначе. Мы знаем,
что
I
=
A
+
A
0
=
B
+
B
0
=
C
+
C
0
и потому
I
= (
A
+
A
0
)(
B
+
B
0
)(
C
+
C
0
) =
ABC
+
ABC
0
+
AB
0
C
+
+
AB
0
C
0
+
A
0
BC
+
A
0
BC
0
+
A
0
B
0
C
+
A
0
B
0
C
0
.
Получилось разложение множества
I
на 8 подмножеств. Это те же
самые подмножества, которые получил ранее профессор Тарантога
(рис. 22).
Из предыдущей формулы сразу вытекает, что
N
(
A
0
B
0
C
0
) =
N
(
I
)
−
N
(
ABC
)
−
N
(
ABC
0
)
−
N
(
AB
0
C
)
−
−
N
(
AB
0
C
0
)
−
N
(
A
0
BC
)
−
N
(
A
0
BC
0
)
−
N
(
A
0
B
0
C
)
,
где через
N
(
D
)
обозначена численность множества
D
. Эту формулу
можно преобразовать так, чтобы в нее не входили дополнения
A
0
,
B
0
,
C
0
множеств
A
,
B
,
C
. С этой целью заменим
C
0
на
I
−
C
. Мы
получим, что
ABC
0
=
AB
(
I
−
C
) =
AB
−
ABC
и потому
N
(
ABC
0
) =
N
(
AB
)
−
N
(
ABC
)
,
N
(
AB
0
C
0
) =
N
(
AB
0
)
−
N
(
AB
0
C
)
и т. д.
44
Глава I. Множества и действия над ними
Заменим потом
B
0
на
I
−
B
и, наконец,
A
0
на
I
−
A
, получим
в конце концов равенство
N
(
A
0
B
0
C
0
) =
N
(
I
)
−
N
(
A
)
−
N
(
B
)
−
N
(
C
) +
+
N
(
AB
) +
N
(
AC
) +
N
(
BC
)
−
N
(
ABC
)
.
Эта формула называется
формулой включений и исключений
и по-
зволяет решать многие задачи, аналогичные рассмотренной выше.
Например, Тарантога мог сразу подсчитать по этой формуле, что
N
(
A
0
B
0
C
0
) = 1000
−
811
−
752
−
418 + 570 + 356 + 348
−
297 =
−
4
.
F
Вот еще одна задача, связанная с подсчетом численности ко-
нечных множеств. Она принадлежит известному детскому писателю
Льюису Кэрроллу, автору «Алисы в стране чудес». Любопытно, что
под псевдонимом Льюис Кэрролл писал математик Доджсон.
В одной из повестей Кэрролла есть следующая задача:
«В ожесточенном бою 70 из 100 пиратов потеряли один глаз, 75 —
одно ухо, 80 — одну руку и 85 — одну ногу. Каково минимальное
число потерявших одновременно глаз, ухо, руку и ногу?»
Обозначим через
A
множество одноглазых, через
B
— множество
одноухих, через
C
— множество одноруких и через
D
— множе-
ство одноногих. В задаче требуется оценить численность множества
ABCD
. Ясно, что все универсальное множество
I
можно предста-
вить как сумму этого множества
ABCD
и множества пиратов, со-
хранивших либо оба глаза, либо оба уха, либо обе руки, либо обе
ноги. Поэтому
I
=
A
0
+
B
0
+
C
0
+
D
0
+
ABCD.
Отсюда следует, что численность множества
I
не больше суммы чис-
ленностей множеств
A
0
,
B
0
,
C
0
,
D
0
и
ABCD
(она была бы равна
этой сумме, если бы множества
A
0
,
B
0
,
C
0
и
D
0
попарно не пересе-
кались). Но численность множества
A
0
равна 30, множества
B
0
—
25, множества
C
0
— 20 и множества
D
0
— 15. Так как численность
универсального множества равна 100, то имеем
100
6
30 + 25 + 20 + 15 +
N
(
ABCD
)
.
Отсюда
N
(
ABCD
)
>
100
−
30
−
25
−
20
−
15 = 10
.
Итак, не менее 10 пиратов лишились и глаза, и уха, и руки, и ноги.