ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 8588
Скачиваний: 22
6
1
ВВЕДЕНИЕ
В
ТЕОРИЮ
МНОЖЕСТВ
Изучение дискретной математики начинается с изучения
понятий «множество», «отношение», «функция», поскольку с
помощью этих понятий строятся математические дисциплины.
Любое понятие дискретной математики также можно определить
с помощью множества.
Понятию «множество» сложно дать точное определение,
поэтому строгого определения нет.
Под множеством понимается совокупность объектов, об-
ладающих определенными свойствами. В данном случае опреде-
ление «множество» дается через свойства его же элементов.
Бурбаки дают следующее определение понятия «множе-
ство»: множество строится из некоторых элементов, обладаю-
щих определенными свойствами и находящихся в каких-то от-
ношениях между собой и с элементами других множеств.
Объекты, образующие множество, называются элементами
множества и обозначаются малыми буквами латинского алфавита
a, b, c, d, …, x, y, z. Большими буквами латинского алфавита обо-
значаются сами множества. Если элемент m принадлежит мно-
жеству М, то это записывают как m
∈ М, в противном случае
m
∉ М (элемент m не принадлежит множеству М). Принадлеж-
ность нескольких элементов может быть записана a
∈B, b∈B,
c
∈B или a,b,c∈B. Множество может содержать любое количество
элементов: счетное, бесконечное, конечное, один элемент, ни од-
ного элемента.
Множество, содержащее конечное число элементов, называ-
ется конечным. Если же множество не содержит ни одного эле-
мента, то оно называется пустым множеством и обозначается
∅
или { }.
Все элементы множества должны отличаться один от друго-
го. Поэтому каждый элемент может входить в множество только
один раз. Количество элементов множества называется мощно-
стью.
Если число элементов множества А конечно, то такое мно-
жество называют конечным множеством, в противном случае его
называют бесконечным множеством.
7
Множество, имеющее мощность, равную единице, называют
синглетоном.
Остановимся на способе перечисления бесконечных мно-
жеств. Пусть N – множество натуральных чисел. Заметим, что
способ перечисления его элементов очевиден: 1, 2, 3, …
Счетным множеством называется множество, равномощное
с множеством натуральных чисел.
Бесконечное множество счетно, если его можно выстроить в
цепочку. В качестве примера рассмотрим множество целых чи-
сел. Цепочка будет выглядеть следующим образом: 0, +1, –1, +2,
–2, +3, –3, …. Любой элемент из множества целых чисел попада-
ет в эту последовательность и любому элементу последователь-
ности можно поставить в соответствие его номер, т.о., множество
целых чисел счетно.
Множество называется полностью определенным, если о
каждом предмете можно сказать, принадлежит он множеству или
нет.
Множество может быть задано различными способами, но
наибольшее распространение получили два способа задания.
1. Путем прямого перечисления его элементов, которые за-
писываются через запятую внутри фигурных скобок. Например,
D = {понедельник, вторник, среда, четверг, пятница, суббо-
та, воскресенье};
А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
При этом порядок перечисления элементов множества не
важен. Так, множества {1, 7, 3}и {1, 3, 7} совпадают. Таким спо-
собом можно задавать конечные множества, содержащие не-
большое количество элементов.
2. С помощью характеристического свойства, которым дол-
жен обладать каждый объект, чтобы стать элементом множества.
Записывается следующим образом:
А = {а | а обладает свойством Q}, т.е. А – множество эле-
ментов а таких, что они обладают свойством Q. Предыдущие
примеры записываются:
D = {x | x – день недели }, А = {а | а целое, 0
≤ а ≤ 9}.
Этим способом можно задать множество, содержащее бес-
конечное количество элементов, т.е. бесконечное множество.
8
Иногда бесконечное множество можно задать просто перечисле-
нием нескольких первых элементов, и тогда характеристическое
свойство оказывается заданным в неявном виде. Например,
множество нечетных чисел можно задать так: А = {1, 3, 5, 7,…}.
Отношение равенства. Два множества равны, если все их
элементы совпадают. Доказывается это утверждение в два этапа:
1.
Каждый элемент множества А является элементом мно-
жества В, т.е., если х
∈А, то х∈В.
2.
Обратное утверждение: каждый элемент множества В яв-
ляется элементом множества А, т.е., если х
∈В, то х∈А.
Отношение равенства обладает свойством транзитивности.
Если А=В и В=С, то А=С.
Отношение включения. Множество А называется под-
множеством В (А включено в В) тогда и только тогда, когда лю-
бой элемент множества А принадлежит множеству В:
А
⊂ В ↔ (а ∈А → а ∈ В ) или
А
⊂ В ↔ А = { a | a
∈B };
Здесь
⊂ – знак включения подмножества;
а
→ b означает: если а то b;
а
↔ b означает: b, если и только если а.
Если хотя бы один элемент множества А не является эле-
ментом множества В, то множество А не является подмножест-
вом В и это записывается следующим образом: А
⊄ В.
В соответствии с определением подмножества пустое мно-
жество является подмножеством любого множества, так как все
его элементы (а у него их нет) являются элементами любого
множества и любое множество является своим подмножеством:
А
⊆ А и ∅ ⊆ ∅. Ø ⊂ А для любого множества А.
Число всевозможных подмножеств любого конечного мно-
жества, содержащего n элементов, равно 2
n
.
Например, пусть задано множество А = {1, 2, 3}, число
подмножеств у него восемь:
∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. Из них ∅ и
само множество А – несобственные подмножества, все осталь-
ные подмножества – собственные. Запишем элементы заданного
множества А в каком-либо порядке.
9
№ 1 2 3 подмножества
0
1
2
3
4
5
6
7
0 0 0
0
0 1
0
1 0
0
1 1
1
0 0
1
0 1
1 1 0
1 1 1
∅
{3}
{2}
{2, 3}
{1}
{1,3}
{1, 2}
{1, 2, 3}
Каждому элементу поставим в соответствие 0, если элемент
отсутствует, и 1 – если элемент присутствует. Для каждого мно-
жества А существует множество, элементами которого являются
подмножества множества А, и только они. Такое множество бу-
дем называть семейством множества А или булеаном этого мно-
жества и обозначать В(А). Множество А будем называть универ-
сальным (универсумом) и обозначать I (в другой литературе его
обозначают как T, U, 1).
Примеры правильных записей:
1)
A = {1, 2, 3, 4}; 1
∈ A; 3∈ A; {1 3}∉ A; {1,3} ⊂ A.
2)
B = {1, 2, {3}}; 1
∈ B; 3 ∉ B; {3} ∈ B; {1, 2} ⊂ B; {2} ⊂ B;
{3}
⊄ B; { {3} } ⊂ B.
3)
C = {1, 2, {1, 2}}; {1, 2}
∈ C; {1, 2} ⊂ C.
4)
D = {
∅, {∅}}; ∅ ∈ D; {∅} ∈ D; ∅ ⊂ D; {∅} ⊂ D.
1.1
Операции
над
множествами
Основными операциями над множествами являются: объе-
динение –
∪, пересечение – ∩, вычитание (разность) – \, сумма –
⊕ и унарная операция дополнение – ¬.
Операция объединения –
∪. Объединением двух мно-
жеств А и В называется такое множество С, элементы которого
состоят из элементов множества А и из элементов множества В.
А
∪ В = {x | x ∈ А и/или х ∈ В}.
Пусть С = А
∪ В, тогда, если х ∈ С, то х ∈ А и/или х ∈ В.
10
Пример:
Пусть заданы множества A = {0, 1, 2, 3, 4} и B = {3, 4, 5, 6}.
Тогда А
∪ В = C = {0, 1, 2, 3, 4, 5, 6}.
Операция пересечения –
∩. Множество С есть пересече-
ние множеств А и В, если каждый элемент множества С является
элементом А и В одновременно.
С = А
∩ В = { x | x ∈ А и х ∈ В}.
Союз «и» заменяют часто знаком &.
Если x
∈ С, то x ∈ А & х ∈ В.
Пример:
Если A = {0, 1, 2, 3, 4}, B = {3, 4, 5, 6}, то C = {3, 4}.
Операция разность – \. Разностью множеств А и В называ-
ется множество С, элементы которого принадлежат А, но не при-
надлежат В.
С = А \ В = { x | x
∈ А и х ∉ В}.
Если x
∈ С, то x ∈ А и х ∉ В.
Для предыдущего примера С = А \ В = {0, 1, 2}; C’ = B\ A =
={5, 6}.
Операция сумма –
⊕ (симметрическая разность).
С = А
⊕ В = (А \ В) ∪ (В \ А).
Если x
∈ С, то х является элементом разности А и В или
элементом разности В и А.
С = А
⊕ В = {x | x ∈ А / В или x ∈ В \ А}.
То есть, если А={1,2,3,4,5}, В={3,4,5,6,7}, тогда С=А
⊕В=
={1,2,6,7}.
Операция дополнение (одноместная операция). Допол-
нение А обозначается ¬А, Ā, А', содержит все те элементы уни-
версального множества I, которые не принадлежат А.
С = Ā = I \ А .
Пусть I = {0,1,2,3,4,5,6,7,8,9}. A={3,8,5,7,0}. Тогда Ā={1, 2,
4, 6, 9}.
1.2
Диаграммы
Эйлера
-
Венна
Возможно графическое представление множеств. Универ-
сальное множество задается в виде квадрата, а множества А и В
как множества точек плоскости, ограниченные соответствующи-