ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.12.2020
Просмотров: 2164
Скачиваний: 53
Вычитание множеств
35
Вычитание множеств
Полицейский-инспектор Варнике осмотрел сейф, закурил свою
трубку и сказал: «Электродрелью вскрывают сейфы только пять
взломщиков: Алек Кунце, Фриц Шмидт, Густав Хойгер, Генрих
Кунтцман и Томас Мюллер. Но Алек, Фриц и Густав сейчас нахо-
дятся в тюрьме Моабит. Придется спросить Генриха и Томаса, где
они провели прошлую ночь...»
Метод, которым воспользовался инспектор Варнике, основан
на операции вычитания множеств. Он имел дело с двумя множества-
ми — множеством
A
взломщиков, пользовавшихся электродрелью,
и множеством
B
всех обитателей тюрьмы Моабит. Удалив из множе-
ства
A
все элементы, принадлежащие множеству
B
, он сузил круг
подозреваемых преступников.
Вообще,
разностью
двух множеств
A
и
B
называют новое множе-
ство, обозначаемое
A
−
B
или
A
\
B
, в которое входят все элементы
множества
A
, не принадлежащие
B
.
Мы видим, что для того, чтобы из множества
A
можно было вы-
честь множество
B
, совершенно не обязательно, чтобы множество
B
было частью множества
A
— вычитание
B
из
A
сводится к удалению
из
A
общей части
A
и
B
:
A
−
B
=
A
−
AB.
Например, инспектору Варнике надо было из числа пяти взломщи-
ков отбросить трех — тех, что пользовались электродрелью и в то же
Рис. 14
время находились в данный момент
в тюрьме. Если
A
— множество то-
чек первого круга на рис. 14, а
B
—
множество точек второго круга, то их
разностью является множество точек
заштрихованной серповидной фигуры
(без дуги
M N
). Если
A
— множе-
ство всех учеников данного класса ка-
кой-либо школы, а
B
— множество
всех девочек, учащихся в этой школе,
то
A
−
B
— множество всех мальчи-
ков, которые учатся в данном классе этой школы. В случае, ко-
гда
B
является частью множества
A
,
A
−
B
называют
дополнением
к множеству
B
в
A
и обозначают
B
0
A
(разумеется, oдно и то же
36
Глава I. Множества и действия над ними
множество
B
имеет разные дополнения в разных содержащих его
множествах
A
). Например, дополнением множества четных чисел
в множестве всех целых чисел является множество нечетных чисел.
Дополнением множества всех квадратов в множестве прямоуголь-
ников является множество всех прямоугольников с неравными сто-
ронами. А дополнением того же множества квадратов в множестве
всех ромбов является множество ромбов с неравными диагоналями.
Если все множества рассматриваются как подмножества универ-
сального множества
I
, то обычно под дополнением множества
B
понимают его дополнение в
I
. В этом случае вместо
B
0
I
пишут про-
сто
B
0
.
Алгебра множеств
F
Мы познакомились с основными действиями над множествами —
сложением, вычитанием и умножением (пересечением) множеств.
Эти действия обладают целым рядом свойств, напоминающих свой-
ства действий над числами. Как известно, вся алгебра многочленов
построена на немногих законах действий над числами, которые
выражаются следующими равенствами:
а)
a
+
b
=
b
+
a
(коммутативность сложения),
б)
(
a
+
b
) +
c
=
a
+ (
b
+
c
)
(ассоциативность сложения),
в)
a
+ 0 =
a
(свойство нуля),
г)
a
+ (
−
a
) =
a
−
a
= 0
(свойство противоположного элемента),
д)
ab
=
ba
(коммутативность умножения),
е)
(
ab
)
c
=
a
(
bc
)
(ассоциативность умножения),
ж)
a
(
b
+
c
) =
ab
+
ac
(дистрибутивность умножения относительно
сложения),
з)
a
·
1 =
a
(свойство единицы).
Большинство этих свойств действий над числами сохраняется и для
действий над множествами. Например, ясно, что для любых двух
множеств имеем
A
+
B
=
B
+
A
(
A
+
B
и
B
+
A
обозначают одно
и то же множество, в которое входят все элементы из
A
и из
B
и не входят никакие другие элементы). Точно так же ясно, что
(
A
+
B
) +
C
=
A
+ (
B
+
C
)
— оба множества составлены из всех элементов, входящих хотя бы
в одно из множеств
A
,
B
и
C
. Так же доказывается, что
AB
=
BA
и
(
AB
)
C
=
A
(
BC
)
(множества
AB
и
BA
состоят из общих элементов
Алгебра множеств
37
множеств
A
и
B
, а множества
(
AB
)
C
и
A
(
BC
)
— из общих элементов
множеств
A
,
B
и
C
).
Несколько сложнее доказать дистрибутивность умножения мно-
жеств относительно сложения, то есть выполнение равенства
A
(
B
+
C
) =
AB
+
AC.
(1)
Строгое логическое доказательство этого равенства несложно,
но несколько кропотливо. Мы ограничимся поэтому двумя ри-
сунками, поясняющими это равенство (рис. 15). На первом из этих
рисунков заштриховано пересечение множества
A
с множеством
B
+
C
, а на втором — пересечения
A
с
B
и
A
с
C
.
Рис. 15
Роль нуля и единицы в действиях над множествами играют мно-
жества
∅
(пустое множество) и
I
(универсальное множество). Имен-
но, справедливы равенства
A
+
∅
=
A,
A
·
∅
=
∅
,
A
·
I
=
A,
соответствующие равенствам
a
+ 0 =
a,
a
·
0 = 0
,
a
·
1 =
a
для чисел.
Таким образом, сложение и умножение множеств обладают теми
же свойствами, что и сложение и умножение чисел.
Поэтому все формулы алгебры многочленов, в которые входят
лишь действия сложения и умножения, остаются справедливыми
и для множеств. Например, тождеству
(
a
+
b
)
2
=
a
2
+
b
2
+ 2
ab
соответствует тождество
(
A
+
B
)
2
=
A
2
+
B
2
+ 2
AB,
(2)
где положено
A
2
=
A
·
A
и
2
AB
=
AB
+
AB
.
38
Глава I. Множества и действия над ними
Но алгебра множеств имеет и своеобразные черты. Ее основ-
ное своеобразие состоит в том, что если одно из множеств
A
и
B
Рис. 16
является подмножеством другого, то фор-
мулы
для
суммы
и
произведения
мно-
жеств упрощаются, а именно: если
A
⊂
B
,
то
A
+
B
=
B
и
AB
=
A
. Это сразу становит-
ся ясно из рис. 16.
В частности, так как
A
⊂
A
, то
A
+
A
=
=
AA
=
A
, а так как
A
⊂
I
, то
A
+
I
=
I
.
Это позволяет упростить формулы ал-
гебры множеств. Например, так как
A
2
=
A
,
B
2
=
B
,
AB
⊂
A
, то
A
2
+ 2
AB
=
A
+ 2
AB
=
A
и формула (2) прини-
мает вид
(
A
+
B
)
2
=
A
+
B
. Вообще, в алгебре множеств не имеет
смысла говорить о степенях, так как для любого
n
имеем
A
n
=
A
.
Покажем теперь, что для множеств есть и второй «распредели-
тельный закон», которого нет для чисел. Он выражается формулой
A
+
BC
= (
A
+
B
)(
A
+
C
)
.
Чтобы доказать его, достаточно раскрыть справа скобки по прави-
лу (1) и заметить, что множества
AB
и
AC
являются подмножества-
ми в
A
:
AC
⊂
A
и
AB
⊂
A
. Кроме того,
AA
=
A
, а поэтому
AA
+
AC
+
BA
+
BC
=
A
+
BC.
Отметим, далее, что операция вычитания множеств уже не похожа
по своим свойствам на операцию вычитания чисел. Для любых трех
чисел
a
,
b
,
c
верно равенство
a
+ (
b
−
c
) = (
a
+
b
)
−
c
. А для трех мно-
жеств
A
,
B
,
C
, вообще говоря,
A
+ (
B
−
C
)
6
= (
A
+
B
)
−
C.
Дело в том, что при сложении множеств повторяющиеся элементы
берутся только один раз, а вычитать можно и множество, не со-
держащееся в уменьшаемом. Поэтому, если, например, все три
множества
A
,
B
,
C
совпадают,
A
=
B
=
C
, то
A
+
B
=
A
и пото-
му
(
A
+
B
)
−
C
=
A
−
A
=
∅
— пустое множество, а
A
+ (
B
−
C
) =
=
A
+
∅
=
A
.
В теории множеств есть еще операция, отсутствующая в обыч-
ной алгебре. Это операция перехода от данного множества
A
к его
дополнению
A
0
=
I
−
A
. Ясно, что множества
A
и
A
0
не пересека-
ются, а в сумме составляют все универсальное множество
I
. Таким
Алгебра множеств
39
образом,
AA
0
=
∅
и
A
+
A
0
=
I
. Кроме того, ясно, что
∅
0
=
I
(допол-
нение пустого множества совпадает с универсальным множеством)
Рис. 17
и
I
0
=
∅
. Далее, имеет место равенство
(
A
0
)
0
=
A
(рис. 17).
Покажем теперь, что если
A
⊂
B
,
то
A
0
⊃
B
0
. В самом деле, чем больше
само множество, тем меньше элементов
останется в его дополнении. На рис. 18
универсальное множество
I
изображено
в виде прямоугольника, а множества
A
и
B
— в виде кругов. Дополнение к мно-
жеству
A
состоит из точек прямоуголь-
ника, лежащих вне меньшего круга, а дополнение к множеству
B
—
из точек прямоугольника, лежащих вне большого круга. Ясно, что
A
0
⊃
B
0
.
Рис. 18
Рис. 19
Несколько сложнее доказываются следующие формулы:
(
A
+
B
)
0
=
A
0
B
0
и
(
AB
)
0
=
A
0
+
B
0
.
На рис. 19 дополнение к множеству
A
заштриховано горизонтальны-
ми линиями, а дополнение к множеству
B
— вертикальными линия-
ми. Дополнение к множеству
A
+
B
состоит из точек прямоугольни-
ка, не попавших ни в один из кругов. Это как раз точки, лежащие
в области, покрытой обеими штриховками, то есть точки из
A
0
B
0
.
Поэтому ясно, что
(
A
+
B
)
0
=
A
0
B
0
. Точно так же этот рисунок ил-
люстрирует и формулу
(
AB
)
0
=
A
0
+
B
0
.
Мы установили ряд свойств действий над множествами. Ра-
ди удобства приведем список этих свойств (как обычно, через
∅