Дискретная математика. Прокушев Л.А. - 5 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

3
Операции над множествами позволяют получить новые множества.
Вложенность множеств (подмножество, надмножество): операция ⊆.
Пусть А = {а, b}, B = {a, b, c}, тогда А ⊆ В (А есть подмножество В, т. е. А
вложено, содержится в В; В есть надмножество над А, т. е. В содержит А).
Объединение множеств: операция ∪ (сумма). Пусть А = {a, b}, B =
={b, c}, тогда А ∪ В = {a, b, c} (все элементы множеств А и В без
повторения элементов).
Пересечение множеств: операция ∩. Пусть А = {a, b}, B = {b, c}, тогда
A ∩ B = {b} (элементы общие для множеств А и В).
Дополнение множеств: операция \ (разность). Пусть A = {a, b}, B =
={b, c}, тогда A \ В = {a} (все элементы множества А, не принадлежа-
щие В, т. е. из А вычитаются элементы, общие с В).
Симметрическая разность: операция –. Пусть А = {a, b, c}, B = {a, c, d},
тогда А – В = {b, d} (все элементы А, не принадлежащие В, и все элемен-
ты В, не принадлежащие А).
Равенство множеств: операция =. A = B справедливо тогда и только
тогда, когда A ⊆ B и B ⊆ A.
Справедливы отношения: A ∩ B ⊆ A, A ∩ B ⊆ B, A ⊆ A ∪ B, B ⊆ A ∪ B.
Например, если A ⊆ B, B ⊆ C, то A ⊆ C, поэтому из приведенных
выше соотношений следует, что A ∩ B ⊆ A ∪ B. Справедливы также
формулы дистрибутивности: (A ∪ B) ∩ C = (A ∩ B) ∪ (B ∩ C), (A ∩ B) ∪
∪ C = (A ∪ C) ∩ (B ∪ C).
Диаграммы Эйлера–Венна иллюстрируют операции над множества-
ми, что будет показано при объяснении контрольного задания.
Булеаном называется множество всех подмножеств множества М
и обозначается В(М), а множество М называется универсумом, или
универсальным. Каждое множество М ≠ ∅ имеет, по крайней мере, два
различных элемента: само М и ∅. Пусть М = {x, y, z}, тогда его булеан
В(М) = {∅, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, M}. Мощность булеана от
универсума |B(M)| = 2
|M |
. Например |M| = 3, |B(M)| = 2
3
= 8.
Алгебра множеств определяет правила выполнения операций над мно-
жествами. Множество М вместе с заданной на нем совокупностью опера-
ций О = {o
1
, o
2
, …,o
m
}, т. е. система А = (М; o
1
, o
2
, …, o
m
} называется
алгеброй; М называется основным множеством (носителем) алгебры А.
Пусть задано универсальное множество U; его булеан B(U). Сово-
купность операций ∪ (объединения), ∩ (пересечения), ↓ (дополнения,
отрицания) называются булевыми операциями. Алгебра B = (B(U); ∪,
∩, ↓) называется булевой алгеброй множеств над U. Элементами ос-

Страницы