ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 15352
Скачиваний: 188
21
=
∪
)
(
B
A
∪
(
)
A
B C
∪
∪
=
А
∩ B ∪ A ∩ B ∩ С
.
После этого обращаемся к диаграмме Венна (рис. 1.2):
А
∩ B
= {1, 2, 7};
A ∩
C
B ∩
= {5}.
Объединив эти множества, получаем искомое дополнение множества
D
:
D
= {1, 2, 5, 7}.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 1.5
· · · · · · · · · · · · · · · · · · · · · · ·
Найти дополнение
D
множества
D
=
A ∩ B ∪
(
B
⊕
C
).
В данном случае следует сначала найти элементы множества
D
. Согласно
диаграмме (рис. 1.2), множество
A ∩ B
состоит из элементов 0 и 3. Симметриче-
скую разность множеств
B
и
С
сначала представим в виде:
B
⊕
C
=
B ∩ С ∪ B ∩ C
.
По диаграмме находим:
B ∩ С
= {0, 1, 2};
B ∩ C
= {6, 9}.
Объединение этих множеств есть симметрическая разность
B
⊕
C
:
B
⊕
C
= {0, 1, 2, 6, 9}.
Объединив элементы множеств
A ∩ B
и
B
⊕
C
, получаем множество
D
:
D
= {0, 1, 2, 3, 6, 9}.
Находим разность
U
\
D
и в результате получаем искомое дополнение
D
:
D
= {4, 5, 7, 8}.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Найдите элементы множеств (рис. 1.1):
1)
;
)
(
)
(
B
A
B
A
∪
∩
∪
2)
;
)
(
)
(
B
A
B
A
∪
∩
∪
3)
;
B
A
B
A
∩
∪
∩
4)
.
B
A
B
A
∩
∪
∩
2. Найдите элементы множеств (рис. 1.2):
1)
;
C
B
B
A
С
A
∩
∪
∩
∪
∩
2)
;
)
(
)
(
)
(
C
B
B
A
С
A
∪
∩
∪
∩
∪
3)
;
C
B
A
C
B
A
∩
∩
∪
∩
∩
4)
.)
(
)
(
C
B
A
C
B
A
∪
∪
∩
∪
∪
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
22
1.6 Декартово произведение множеств
Если взять из множества
A
= {
a
1
,
a
2
, …,
a
n
}
элемент
a
i
и записать справа от него элемент
b
j
, принадлежащий множеству
B
= {
b
1
,
b
2
, …,
b
m
},
то получим
упорядоченную
пару элементов
a
i
и
b
j
, записываемую в виде (
a
i
,
b
j
),
где
i
= 1, 2, 3, …,
n
;
j
= 1, 2, 3, …,
m
.
Упорядоченную пару необходимо отличать от обычной, то есть неупоря-
доченной пары: в неупорядоченной паре порядок записи элементов не имеет
значения, в то время как в упорядоченной паре при смене последовательности
записи элементов получается другая пара.
Множество всех упорядоченных пар вида (
a
i
,
b
j
) получило название
де-
картова произведения
множеств
A
и
B
[14; 18; 30]. В существующих литера-
турных источниках встречается также название
прямое произведение
[35; 40].
Для обозначения декартова произведения принят знак арифметического
умножения «
×».
Записывается декартово произведение следующим образом:
A
×
B
= {(
x
,
y
) |
x
∈
A
и
y
∈
B
}.
Читается: «декартово произведение множеств
A
и
B
– это множество упо-
рядоченных пар (
x
,
y
), где
x
обозначает элемент, принадлежащий множеству
A
,
y
– элемент, принадлежащий множеству
B
».
Очевидно, что операция декартова произведения некоммутативна, т. е. в
общем случае
A
×
B
≠
B
×
A
.
Поясним это неравенство на примере следующих двух непересекающихся
множеств:
A
= {1, 2, 3, 4};
B
= {
a
,
b
,
c
}.
Тогда
A
×
B
= {(1,
a
), (1,
b
), (1,
c
), (2,
a
), (2,
b
), (2,
c
),
(3,
a
), (3,
b
), (3,
c
), (4,
a
), (4,
b
), (4,
c
)};
B
×
A
= {(
a
, 1), (
b
, 1), (
c
, 1), (
a
, 2), (
b
, 2), (
c
, 2),
(
a
, 3), (
b
, 3), (
c
, 3), (
a
, 4), (
b
, 4), (
c
, 4)}.
Из этих двух выражений видно, что в результате перестановки знаков в
круглых скобках множества
A
×
B
получается новое множество
B
×
A
, все эле-
23
менты которого отличаются от элементов множества
A
×
B
, т. е. множества
A
×
B
и
B
×
A
не пересекаются.
Кардинальное число декартова произведения множеств
A
и
B
определяет-
ся следующим образом:
|
A
×
B
| = |
B
×
A
| = |
A
| ⋅ |
B
|,
где точкой, поставленной между символами
|
A
| и |
B
|, обозначена операция
арифметического умножения. Например, пусть дано:
A
= {
a
,
b
,
c
},
B
= {1, 2, 3, 4, 5}.
Согласно этим записям:
|
A
| = 3; |
B
| = 5; |
A
×
B
| = 3 ⋅ 5 = 15; |
B
×
A
| = 5 ⋅ 3 = 15.
В случае бóльшего числа множеств кардинальное число их декартова
произведения определяется аналогично: если
|
A
1
|, |
A
2
|, …, |
A
n
| – кардинальные
числа заданных множеств
A
1
,
A
2
, …,
A
n
, то
|
A
1
×
A
2
× … ×
A
n
| = |
A
1
| ⋅ |
A
2
| ⋅ … ⋅ |
A
n
|,
то есть, чтобы найти число элементов декартова произведения
n
множеств, до-
статочно перемножить их кардинальные числа.
Операция декартова произведения множеств ассоциативна:
(
A
×
B
)
×
C
=
A
× (
B
×
C
) =
A
×
B
×
C
,
благодаря чему декартово произведение множеств можно записывать без ско-
бок, но сами множества записываются в строгом порядке.
Множества, входящие в декартово произведение, могут быть равными.
Если в произведении
A
1
×
A
2
×…×
A
n
принять
A
1
=
A
2
=…=
A
n
=
A
,
то получим
M = A
×
A
× … ×
A
=
A
n
,
где
A
n
–
степень
множества
A
. Элементы множества
A
n
называют
кортежами
длины
n
.
Например, пусть задано множество
A
= {
a
,
b
,
c
}. Тогда:
если
n
= 1, то
A
1
= {(
a
), (
b
), (
c
)};
|
A
1
| = 3
1
= 3;
если
n
= 2, то
A
2
= {(
a
,
a
), (
a
,
b
), (
a
,
c
), … (
c
,
b
), (
c
,
c
)};
|
A
2
| = 3·3 = 3
2
= 9;
если
n
= 3, то
A
3
= {(
a
,
a
,
a
), (
a
,
a
,
b
), (
a
,
a
,
c
), (
a
,
b
,
a
), …, (
c
,
c
,
c
)};
|
A
3
| = 3
3
= 27;
если
n
= 4, то
A
4
= {(
a
,
a
,
a
,
a
), (
a
,
a
,
a
,
b
), …, (
c
,
c
,
c
,
c
)};
|
A
4
| = 3
4
= 81 и т. д.
24
Множество
A
1
содержит три кортежа, каждый из которых является одно-
элементным и имеет длину, равную единице. Множество
A
2
называется
квад-
ратом множества
А
. В нём содержится 9 кортежей длины 2. Множество
A
3
со-
стоит из 27 кортежей длины 3 и т. д.
В общем случае справедливо соотношение:
|
A
n
| = |
A
|
n
.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Сколько элементов в декартовых произведениях следую-
щих множеств?
1)
A
= {0, 1, 2};
B
= {3, 4, 5}; 4)
A
= {Ø};
B
= {Ø, 0, 1, 2, 6, 9};
2)
A
= {2};
B
= {0, 1, 2, 6, 9}; 5)
A
= Ø;
B
= {3, 4, 5, 8};
3)
A
= {0, 00, 000};
B
= {3, 4};6)
A
= {Ø, 0};
B
= {00, 10, 2, 6, 9}.
2. Сколько элементов содержит пересечение декартовых про-
изведений
A
×
B
и
B
×
A
следующих множеств?
1)
A
= {0, 1, 2};
B
= {3, 4, 5}; 3)
A
= {0, 1, 2};
B
= {0, 1, 3};
2)
A
= {2};
B
= {0, 1, 2, 6, 9}; 4)
A
= {Ø};
B
= {Ø, 0, 1, 2, 6, 9}.
3. Найдите
n
и |
A
|, если известно, что
1)
|
A
n
| = 128;
2)
|
A
n
| = 49; 3) |
A
n
| = 243; 4) |
A
n
| = 125.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
1.7 Заключительные замечания
На этом завершим первую главу пособия. В ней представлены минималь-
но необходимые, начальные сведения из теории множеств, созданной немецким
математиком Георгом Кантором. К ним относятся: понятие множества и основ-
ные операции, такие как объединение, пересечение и дополнение, а также раз-
ность, симметрическая разность и декартово произведение множеств. При этом
объекты с бесконечным числом составляющих не рассматриваются, всё внима-
ние сосредоточено только на конечных множествах, свойства которых хорошо
согласуются с нашей интуицией, взращённой на представлениях о дискретно-
сти и конечности всех величин, с которыми приходится иметь дело в практиче-
ской деятельности.
Не включена в книгу и теория нечётких множеств, созданная в 60-х гг.
прошлого века американским математиком Лотфи Заде, получившая распро-
странение не только в теоретико-множественных построениях, но и в теории
нечёткого логического вывода [26; 31].
25
Представленных в пособии начальных сведений о чётких конечных мно-
жествах вполне достаточно для освоения дальнейшего материала данной книги,
где не требуется учитывать особенности бесконечных и нечётких множеств.
При необходимости же всегда можно обратиться к другим учебным пособиям,
в которых теоретико-множественные аспекты рассматриваются более подроб-
но. Примерами могут служить публикации [5; 24; 26; 29; 31; 32; 34; 35; 38; 45;
55; 56], где можно найти сведения не только о конечных, но и бесконечных, а
также нечётких множествах.