ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 15249
Скачиваний: 187
11
Если два множества состоят из одних и тех же элементов, то они называ-
ются
равными
. По [33, с. 5], в этом заключается интуитивный
принцип объём-
ности
, а согласно [25, с. 20], так формулируется
аксиома объёмности
,
экстен-
сиональности
. Например, множества
1
C
и
2
C
, представленные в виде
{
}
{
}
1
1
1, 2, 3, 4 ;
2,1, 4, 3 ,
C
C
=
=
состоят из одних и тех же элементов, следовательно, они равны.
Число элементов, образующих множество, называется его
кардинальным
числом
, или
мощностью
. Обозначается кардинальное число двумя вертикаль-
ными чертами, между которыми записывается множество [50]. Например:
{
}
1, 2, 3, 4, 5
5.
C =
=
Два множества
A
и
B
называются
эквивалентными
, если
=
A
B
. Оче-
видно, что равные множества одновременно являются и эквивалентными.
Завершим параграф замечанием о повторяемости элементов множества.
Элементы, входящие в множество, повторяться не могут. Каждый элемент
должен входить в множество не более одного раза. Например, запись вида:
{
}
1, 2, 2, 3, 4, 4, 4, 5, 6
D =
является множеством, но состоит оно лишь из шести элементов, а не из девяти,
и его кардинальное число равно 6.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Найдите кардинальное число множеств:
1)
{
}
| 4
15
целое число ;
A
x
x
x
=
≤ ≤
∧ −
2)
{
}
|
100
целое неотрицательное число ;
A
x x
x
=
≤
∧ −
3)
{
}
|10
50
целое число .
A
x
x
x
=
≤ ≤
∧ −
2. Найдите кардинальное число множеств:
1)
{
}
1,11, 2, 22, 3 ;
A =
2)
{
}
,
,
;
A = ∅ ∅∅ ∅∅∅∅
3)
{
}
1, ,1, 2 .
A =
+ =
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
12
1.2 Понятие подмножества
Если все элементы множества
1
A
являются элементами множества
A
, то
множество
1
A
называется
подмножеством
множества
A
. Пусть множество
A
состоит из четырёх элементов
, , , ,
a b c d
т. е.
{
}
, , ,
.
=
A
a b c d
Тогда примерами его подмножеств могут служить выражения:
{ }
{ }
{ }
{ }
{
}
1
2
3
4
5
, ;
,
;
;
;
, ,
.
=
=
=
=
=
A
b c
A
a d
A
d
A
a
A
b c d
Множество
{
}
6
, ,
=
A
c d e
не является подмножеством множества
A
, по-
скольку в множество
6
A
входит элемент e , которого нет в множестве
A
.
Пустое множество является подмножеством любого множества.
Множество всех подмножеств множества
A
называется его
булеаном
[4;
14; 35; 40]. Например, булеан множества
{
}
1, 2, 3
A =
имеет вид:
( )
{ } { } { } { } { } { } {
}
{
}
, 1 , 2 , 3 , 1,2 , 1,3 , 2,3 , 1,2,3 ,
= ∅
B A
где
( )
B A
– обозначение булеана множества
A
.
Очевидно, что в общем случае булеан
( )
B A
содержит
2
A
элементов, то
есть подмножеств множества
A
. Пустое множество и само множество
A
назы-
ваются
несобственными подмножествами. Все остальные 2
A
– 2 подмножеств
называются собственными подмножествами множества A .
Для обозначения принадлежности подмножества заданному множеству
применяется знак включения вида
⊆
. Например:
{ }
{
}
1
1
если
, ;
, , ,
, то
.
=
=
⊆
A
b c
A
a b c d
A
A
Эта запись читается следующим образом: «
1
A является подмножеством
множества A , так как все элементы
1
A являются элементами множества A ».
Теоретико-множественные знаки «∈» и «
⊆
» необходимо строго разли-
чать. Первый из них задает отношение между элементами и множествами, а
второй – между множествами.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Дано множество:
{
}
1, 2, 3, 4, 6, 7, 8
A =
. Укажите номера
множеств, являющихся подмножествами множества A :
13
1)
{
}
3, 4, 6, 7, 8 ;
B =
4)
{
}
, 2, 3, 4, 6, 7, 8 ;
B = ∅
2)
{
}
3, 4, 5, 6, 7 ;
B =
5)
{
}
6, 7, 8 ;
B =
3)
{
}
1, 2, 3, 4, 6 ;
B =
6)
{ }
8 .
=
B
2.
Сколько
элементов
содержит
булеан
множе-
ства
{
}
1, 2, 3, 4, 5
A =
?
3.
Булеан множества A содержит 64 элемента. Сколько суще-
ствует подмножеств множества A , являющихся синглетонами?
4.
Дано множество:
{
}
1, 2, 3, 4, 6, 7
A =
.
а. Сколько существует подмножеств множества A , содержа-
щих только нечётные цифры?
б. Из булеана множества A удалили все те подмножества, в
которых содержится хотя бы одна чётная цифра. Сколько элементов
осталось в булеане?
в. Из булеана множества A удалили все синглетоны. Сколько
элементов осталось?
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
1.3 Объединение, пересечение и дополнение множеств
Для построения новых множеств на основе заданных применяются теоре-
тико-множественные операции. Главными из них являются объединение, пере-
сечение и дополнение [35].
Объединение множеств A и B – это множество C , содержащее все эле-
менты множества A и все элементы множества B :
,
= ∪
C
A
B
где знак ∪ обозначает операцию объединения. Возможна и такая запись:
{
}
|
или
.
=
∈
∈
∪
A
B
x x
A
x
B
Читается: «объединение множеств A и B – это все те значения
x
, кото-
рые принадлежат множеству A или принадлежат множеству B ».
Например, если к множествам
{
}
{
}
1, 2, 3, 4, 5 ,
3, 4, 5, 6, 7, 8
A
B
=
=
(1.3)
применить операцию объединения, то получим новое множество:
{
} {
} {
}
1, 2, 3, 4, 5
3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8 .
C
=
=
∪
Операция объединения может быть применена и к большему числу мно-
жеств, например, к четырём:
14
{
}
|
, или
, или
, или
.
=
∈
∈
∈
∈
∪
∪
∪
A
B
C
D
x x
A
x
B
x
C
x
D
Для операции объединения справедливы следующие соотношения:
;
; если
, то
.
=
∅ =
⊆
=
∪
∪
∪
A
A
A
A
A
A
B
A
B
B
Пересечение множеств A и B – это такое множество C , в которое входят
все элементы, принадлежащие одновременно обоим множествам A и B :
{
}
|
и
,
=
∈
∈
∩
A
B
x x
A
x
B
где ∩ – знак, обозначающий операцию пересечения. Читается запись следую-
щим образом: «пересечение множеств A и B – это все те значения
x
, которые
принадлежат и множеству A , и множеству B ». Найдём, например, пересечение
множеств (1.3):
{
} {
} {
}
1, 2, 3, 4, 5
3, 4, 5, 6, 7, 8
3, 4, 5 .
C
A
B
=
=
=
∩
∩
Операция пересечения применима и к большему числу множеств:
{
}
|
и
и
и
.
=
∈
∈
∈
∈
∩
∩
∩
A
B
C
D
x x
A
x
B
x
C
x
D
Для операции пересечения справедливы следующие соотношения:
;
; если
, то
.
=
∅ = ∅
⊆
=
∩
∩
∩
A
A
A
A
A
B
A
B
A
Операции объединения и пересечения коммутативны:
;
;
=
=
∪
∪
∩
∩
A
B
B
A
A
B
B
A
и ассоциативны:
(
)
(
)
;
=
=
∪
∪
∪
∪
∪
∪
A
B
C
A
B
C
A
B
C
(
)
(
)
.
=
=
∩
∩
∩
∩
∩
∩
A
B
C
A
B
C
A
B
C
Кроме того, имеет место дистрибутивность пересечения относительно
объединения:
(
) (
) (
)
,
=
∩
∪
∩
∪
∩
A
B
C
A
B
A
C
а также дистрибутивность объединения относительно пересечения:
(
) (
) (
)
.
=
∪
∩
∪
∩
∪
A
B
C
A
B
A
C
Чтобы в записях множеств исключить лишние скобки, в теории множеств
принято: сначала выполняются операции пересечения, а затем – объединения,
если выражение представлено в виде объединения пересечений. Например:
(
) (
)
.
=
∩
∪
∩
∩
∪
∩
A
B
C
D
A
B
C
D
Скобки применяются лишь при необходимости изменения порядка вы-
полнения операций, например:
(
) (
)
.
∪
∩
∪
A
B
C
D
15
Здесь первыми выполняются операции в скобках, т. е. объединения, а за-
тем – пересечения.
Третья операция из основных – дополнение. Но прежде чем её рассмат-
ривать, необходимо ввести понятие универсального множества (универсума, со-
гласно [35; 40]).
Универсальным называется множество
U
, все элементы которого участ-
вуют в данном рассуждении [20; 433]. Обычно множество
U
считается задан-
ным. Пусть в универсуме дано множество A . Дополнение множества A – это
новое множество А , все элементы которого принадлежат универсуму
U
, но ни
один из них не принадлежит множеству A :
{
}
|
и
,
=
∉
∈
A
x x
A
x U
где чертой над буквой обозначена операция дополнения (произносится
«не A »):
U
– универсальное множество.
Читается: «множество А – это все те значения
x
, которые не принадле-
жат множеству A , но являются элементами множества
U
».
Допустим, что универсальное множество задано десятичными цифрами:
{
}
0,1, 2, 3, 4, 5, 6, 7, 8, 9 ,
U
=
и пусть заданы множества
{
}
{
}
1, 2, 3, 4, 5 ;
3, 4, 5, 6, 7, 8 .
A
B
=
=
Тогда их дополнения представятся в виде
{
}
{
}
0, 6, 7, 8, 9 ;
0,1, 2, 9 .
A
B
=
=
В теоретико-множественных преобразованиях широко применяются сле-
дующие тождества:
1) законы поглощения:
(
)
;
;
=
=
∪
∩
∩
∪
A
A
B
A
A
A
B
A
2) законы склеивания:
(
)
(
)
;
;
=
=
∩
∪
∩
∪
∩
∪
A
B
A
B
A
A
B
A
B
A
3) теорема 1 де Моргана: дополнение объединения есть пересечение до-
полнений:
;
=
∪
∩
A
B
А
B