Материал: Дискретная математика. Методичка. Кацаран
ГЛАВА 1. МНОЖЕСТВА
§ 1. Определение и способы задания множеств
Множество — это любое собрание вполне определенных и разли-
чимых объектов нашей интуиции или интеллекта, мыслимое как еди-
ное целое,
— это описание множества принадлежит основателю теории
множеств Георгу Кантору (1845 — 1918).
Объекты, из которых состоит множество, называются его эле-
ментами
. Множества будем обозначать прописными буквами латинско-
го алфавита
(
A, B, C, X, Y, Z, . . .
)
, а элементы множеств — строчными
(
x, y, z, a, b, c, . . .
)
. Зафиксируем следующие обозначения для наиболее
важных числовых множеств:
N
— множество натуральных чисел,
Z
—
множество целых чисел,
R
— множество действительных чисел.
Множество
A
называется подмножеством множества
B
(
обо-
значается —
A
⊆
B
, знак
⊆
называется знаком включения
),
если каж-
дый элемент множества A является элементом множества
B
.
Множества
A
и
B
равны
(
A
=
B
),
если одновременно имеют ме-
сто включения
A
⊆
B
и
B
⊆
A
. Принадлежность элемента
x
множе-
ству
A
обозначается
x
∈
A
, непринадлежность элемента
x
множеству
A
обозначается
x /
∈
A
.
Множество, не содержащее элементов, называется пустым и обо-
значается
∅
.
Множество, включающее элементы всех рассматриваемых в кон-
кретной ситуации множеств, называется универсальным для данной
ситуации и обозначается
U
. Для любого множества
имеют место
включения:
∅
⊆
A
⊆
U
.
Рассмотрим способы задания множеств. Множество может быть за-
дано: а) описанием характеристического свойства его элементов, б) при
помощи списка или перечисления элементов множества, в) при помощи
порождающей процедуры и т. д.
При задании множества
A
при помощи его характеристического
свойства
P
(
x
)
пишут
A
=
{
x
|
P
(
x
)
}
.
При помощи списка могут задаваться только конечные множества,
т. е. множества, состоящие из конечного числа элементов.
Порождающая процедура описывает способ получения элементов
множества из уже полученных элементов или других объектов. Весьма
распространенной порождающей процедурой является образование мно-
жеств из других множеств при помощи операций, которые рассмотрим
ниже.
6
§ 2. Операции над множествами и их свойства
Объединением множеств
A
и
B
называется множество
A
∪
B
,
состоящее из тех и только тех элементов, которые принадлежат
хотя бы одному из множеств
A
или
B
:
A
∪
B
=
{
x
|
x
∈
A
или
x
∈
B
}
.
Пересечением множеств
A
и
B
называется множество
A
∩
B
,
состоящее из тех и только тех элементов, которые принадлежат
одновременно множествам
A
и
B
:
A
∩
B
=
{
x
|
x
∈
A
и
x
∈
B
}
.
Разностью множеств
A
и
B
называется множество
A
\
B
тех
и только тех элементов из
A
, которые не принадлежат множеству
B
:
A
\
B
=
{
x
|
x
∈
A
и
x /
∈
B
}
.
Дополнение
A
определяется равенством
A
=
U
\
A
, где
U
— уни-
версальное множество
.
Симметричной разностью множеств
A
и
B
называется множе-
ство:
A
4
B
= (
A
\
B
)
∪
(
B
\
A
)
.
Эти операции можно наглядно проиллюстрировать следующим об-
разом:
Рис. 1:
A
∪
B
Рис. 2:
A
∩
B
Рис. 3:
A
\
B
Рис. 4:
A
Рис. 5:
A
4
B
Приведенные здесь рисунки называются диаграммами Эйлера-Венна.
7
Операции над множествами обладают следующими свойствами:
1)
A
=
A
(закон двойного отрицания);
2)
A
∪
B
=
B
∪
A
(коммутативность объединения);
3)
A
∩
B
=
B
∩
A
(коммутативность пересечения);
4)
A
∪
(
B
∪
C
) = (
A
∪
B
)
∪
C
(ассоциативность объединения);
5)
A
∩
(
B
∩
C
) = (
A
∩
B
)
∩
C
(ассоциативность пересечения);
6)
A
∩
(
B
∪
C
) = (
A
∩
B
)
∪
(
A
∩
C
)
(1-й дистрибутивный закон);
7)
A
∪
(
B
∩
C
) = (
A
∪
B
)
∩
(
A
∪
C
)
(2-й дистрибутивный закон);
8)
A
∪
B
=
A
∩
B
(закон де Моргана);
9)
A
∩
B
=
A
∪
B
(закон де Моргана);
10)
A
∪
(
A
∩
B
) =
A
(закон поглощения);
11)
A
∩
(
A
∪
B
) =
A
(закон поглощения);
12)
A
∪
=
A
;
13)
A
∩
=
;
14)
A
∪
U
=
U
;
15)
A
∩
U
=
A
.
§ 3. Мощность конечного множества
Число элементов конечного множества
A
называется его мощно-
стью и обозначается
|
A
|
.
Говорят, что между множествами
A
и
B
установлено взаи-
мооднозначное соответствие, если задан закон, по которому каждо-
му элементу множества
A
соответствует один и тот же элемент
множества
B
.
Между конечным непустым множеством
A
мощности
n
и отрезком
натурального ряда
{
1
,
2
, . . . , n
}
существует взаимооднозначное соответ-
ствие.
Приведем очевидные свойства мощности конечных множеств:
1)
| |
= 0
;
2) из
A
⊆
B
следует
|
A
| ≤ |
B
|
, если при этом
A
6
=
B
, то
|
A
|
<
|
B
|
,
следует отметить, что обратное утверждение не верно;
3)
|
A
4
B
| ≤ |
A
|
+
|
B
|
;
4)
|
A
∩
B
| ≤
min
{|
A
|
,
|
B
|}
;
5)
|
A
∪
B
|
=
|
A
|
+
|
B
| − |
A
∩
B
|
;
6)
|
A
\
B
| ≤ |
A
|
;
7)
|
A
4
B
|
=
|
A
∪
B
| − |
A
∩
B
|
.
8
§ 4. Прямое произведение двух и более множеств
Прямым произведением двух множеств
A
=
{
a
1
, . . . , a
m
}
и
B
=
{
b
1
, . . . , b
n
}
называется множество
A
×
B
упорядоченных пар
вида
(
a
i
, b
j
)
, где
i
= 1
, m
,
j
= 1
, n
.
Прямым произведением
k
множеств
A
1
,
A
2
,
. . .
,
A
k
называется
множество
A
1
×
A
2
×
. . .
×
A
k
упорядоченных наборов
(
x
i
1
, x
i
2
, . . . , x
i
k
)
,
длины
k
, где
x
i
1
∈
A
1
,
x
i
2
∈
A
2
,
. . .
,
x
i
k
∈
A
k
.
Эти определения кратко можно записать так:
A
×
B
=
{
(
a, b
)
|
a
∈
A, b
∈
B
}
.
A
1
×
A
2
×
. . .
×
A
k
=
{
(
x
i
1
, x
i
2
, . . . , x
i
k
)
|
x
i
1
∈
A
1
, x
i
2
∈
A
2
, . . . , x
i
k
∈
A
k
}
.
Теорема о мощности прямого произведения.
Мощность пря-
мого произведения конечного числа конечных множеств равна произве-
дению мощностей этих множеств
|
A
1
×
A
2
×
. . .
×
A
k
|
=
|
A
1
| · |
A
2
| ·
. . .
· |
A
k
|
, k
∈
N
.
Доказательство. Рассмотрим вначале случай двух множеств и дока-
жем формулу
|
A
×
B
|
=
|
A
| · |
B
|
.
Пусть
A
=
{
a
1
, . . . , a
m
}
и
B
=
{
b
1
, . . . , b
n
}
, тогда элементы
A
×
B
множества можно расположить в виде следующей таблицы:
(
a
1
, b
1
)
(
a
1
, b
2
)
. . .
(
a
1
, b
n
)
. . .
. . .
. . .
. . .
(
a
m
, b
1
) (
a
m
, b
2
)
. . .
(
a
m
, b
n
)
,
которая содержит
m
строк и
n
столбцов. Поэтому число записанных в
таблице упорядоченных пар равно
mn
=
|
A
| · |
B
|
.
Для доказательства теоремы в случае произвольного
k
воспользу-
емся методом математической индукции. При
k
= 1
теорема, очевидно,
имеет место. Предположим, что она выполняется для случая
(
k
−
1)
-го
множества и докажем ее для случая
k
множеств. С этой целью устано-
вим взаимооднозначное соответствие между множествами:
A
1
×
A
2
×
. . .
×
A
k
и
(
A
1
×
A
2
×
. . .
×
A
k
−
1
)
×
A
k
по правилу: элементу
(
a
i
1
, . . . , a
i
k
)
∈
(
A
1
×
A
2
×
. . .
×
A
k
)
поставим в
соответствие элемент
((
a
i
1
, . . . , a
i
k
−
1
)
, a
i
k
)
∈
(
A
1
×
. . .
×
A
k
−
1
)
×
A
k
и
наоборот. В силу взаимооднозначного соответствия между множествами
A
1
×
A
2
×
. . .
×
A
k
и
((
A
1
×
A
2
×
. . .
×
A
k
−
1
)
×
A
k
)
9
их мощности совпадают; используя утверждение теоремы для случая
двух множеств, получаем:
|
A
1
×
A
2
×
. . .
×
A
k
|
=
|
(
A
1
×
A
2
×
. . .
×
A
k
−
1
)
×
A
k
|
=
|
A
1
×
A
2
×
. . .
×
A
k
−
1
||
A
k
|
.
В силу предположения индукции
|
A
1
×
. . .
×
A
k
−
1
|
=
|
A
1
|
. . .
|
A
k
−
1
|
,
что завершает доказательство теоремы.
Множество
A
k
=
A
×
. . .
×
A
|
{z
}
k
называется
k
-ой степенью мно-
жества
A
. Из теоремы о мощности прямого произведения следует:
|
A
k
|
=
|
A
|
k
.
Пусть
E
=
{
0
,
1
}
, тогда
E
n
=
{
(
α
i
1
, . . . , α
i
n
)
|
α
i
s
∈ {
0
,
1
}
, s
= 1
, . . . , n
}
,
откуда следует
|
E
n
|
=
|
E
|
n
= 2
n
, т. е. мощность множества всех наборов
длины
n
из нулей и единиц равна
2
n
.
§ 5. Булеан множества
Булеаном
Б
(
A
)
множества
A
называется множество всех под-
множеств этого множества
: Б
(
A
) =
{
X
|
X
⊆
A
}
,
если
A
=
{
a
1
, . . . , a
n
}
,
то
Б
(
A
) =
{
,
{
a
1
}
, . . . ,
{
a
n
}
, . . . ,
{
a
i
1
, . . . , a
i
s
}
, . . .
}
.
Теорема о мощности булеана
.
Пусть
A
— конечное множество
мощности
n
, тогда мощность его булеана равна
2
n
:
|
Б
(
A
)
|
= 2
n
.
Доказательство. Установим соответствие между множествами Б
(
A
)
и
E
n
по правилу: подмножеству
{
a
i
1
, . . . , a
i
s
} ∈
Б
(
A
)
поставим в со-
ответствие набор длины
n
из нулей и единиц, в котором на местах с
номерами
i
1
, . . . , i
s
стоят единицы, а на остальных местах нули. Это со-
ответствие является взаимооднозначным, поэтому
|
Б
(
A
)
|
=
|
E
n
|
= 2
n
.
Теорема доказана.
В качестве примера приведенного в доказательстве теоремы соот-
ветствия рассмотрим случай
n
= 3
. Пусть
A
=
{
α, β, γ
}
, тогда
Б
(
A
) =
{
,
{
α
}
,
{
β
}
,
{
γ
}
,
{
α, β
}
,
{
α, γ
}
,
{
β, γ
}
,
{
α, β, γ
}}
;
E
3
=
{
(0
,
0
,
0)
,
(1
,
0
,
0)
,
(0
,
1
,
0)
,
(0
,
0
,
1)
,
(1
,
1
,
0)
,
(1
,
0
,
1)
,
(0
,
1
,
1)
,
(1
,
1
,
1)
}
.
Соответствие между
E
3
и Б
(
A
)
может быть установлено
8!
различны-
ми способами (оно равно числу перестановок из элементов множества
E
3
). В данном случае элементы множества
E
3
записаны так, что эле-
менту, стоящему на
k
-ом месте,
k
= 1
,
8
, в Б
(
A
)
соответствует
k
-ый
элемент множества
E
3
:
{
γ
}
соответствует
(0
,
0
,
1)
,
{
α, β
}
—
(1
,
1
,
0)
и
т. д.
Отметим следующее свойство булеана:
Б
(
A
∪
B
) =
{
A
1
∪
B
1
|
A
1
∈
Б
(
A
)
, B
1
∈
Б
(
B
)
}
.
10