discr_math

1

Раздел 1

Множества. Отображения. Отношения на множестве

1.1. Понятие множества

При изложении теории множеств мы будем придерживаться так называемой интуитивной точки зрения, согласно которой такие понятия, как «множество», «элемент множества», относятся к на-

чальным (примитивным) понятиям математики и поэтому не подле-

жат определению.

Математическое понятие множества постепенно выделилось из привычных представлений о совокупности, собрании, классе и т.д.

Один из создателей теории множеств – Георг Кантор1 представлял множество как «совокупность или набор определенных и различи-

мых между собой объектов, мыслимых как единое целое».

С понятием множества мы соприкасаемся прежде всего тогда,

когда по какой-либо причине объединяем по некоторому признаку в

2

одну группу какие-то объекты и далее рассматриваем эту группу или совокупность как единое целое.

Множества принято обозначать заглавными латинскими бу-

квами. Объекты, которые образуют множество, называют элемен-

тами множества и для обозначения элементов используют, как пра-

вило, малые буквы латинского алфавита. Если a является элемен-

том множества M , то будем говорить, что a принадлежит множе-

ству M , и использовать запись a M , в противном случае, если a

не принадлежит множеству M , будем использовать обозначение a M .

В различных приложениях дискретной математики чаще всего встречаются конечные множества. Интуитивный смысл этого тер-

мина ясен: такие множества содержат конечное число элементов.

Число элементов конечного множества A называют мощностью

этого множества и обозначают символом Card A или | A|. Наряду с конечными множествами в математике рассматривают и бесконеч-

ные множества, то есть такие, которые содержат бесконечно много элементов. Так, например, бесконечно множество натуральных чи-

сел N, множество рациональных чисел Q, множество действитель-

ных чисел R.

1 Кантор Георг (1845-1918) – немецкий математик, основатель теории множеств.

3

Способы задания множеств

1. Множество может быть задано перечислением всех его эле-

ментов или списком. В этом случае элементы множества записыва-

ют внутри фигурных скобок, например: А 1,2,a,x или B { ре-

ка Нил, город Москва, планета Уран }.

2. Множество может быть задано описанием свойств его эле-

ментов. Чаще всего при этом используют запись A x| P x , кото-

рую читают следующим образом: «A есть множество элементов x

таких, что для них выполняется свойство P x ».

Например, B {x| x – натуральное число, меньшее 10 }, при этом,

очевидно, B 1,2,3,4,5,6,7,8,9 .

3. Множество можно задать порождающей процедурой, напри-

мер:

D {z|1 D, и если z D , то z 3 D },

E {x| x 3k , k любое натуральное число}.

Наряду с порождающей процедурой существует распознающая

или разрешающая процедура, которая позволяет определить, при-

надлежит ли данный объект множеству или нет. Для множества D

распознающая процедура заключается в том, что для любого нату-

рального числа n будут проверять, является ли число 3 делителем числа n 1. Для множества E распознающая процедура заключает-

ся в разложении числа на простые множители.

4

Пустое и универсальное множества

Определение 1.1. В теории множеств отдельно вводится множество,

которое не содержит ни одного элемента. Такое множество называ-

ется пустым и обозначается символом .

В любой конкретной задаче приходится иметь дело только с под-

множествами некоторого, фиксированного для данной задачи, мно-

жества. Его принято называть универсальным (универсумом) и обо-

значать символом U.

Например, при сборке некоторого изделия универсальным множеством естественно назвать множество всех деталей и сбороч-

ных элементов, из которых это изделие состоит.

Если мы рассматриваем множества, связанные с какими-

нибудь фигурами на плоскости, то в качестве универсального мно-

жества можно выбрать множество всех точек плоскости.

Определение 1.2. Два множества A и B называются равными

(A B), если они состоят из одних и тех же элементов. Поэтому не-

существен порядок записи в фигурных скобках элементов множест-

ва, задаваемого списком, т.е. {a, b, c} {a, c, b}.

Операции над множествами

Определение 1.3. Множество A называется подмножеством мно-

жества B , если любой элемент множества A принадлежит множе-

ству B . При этом пишут A B, где « » есть знак вложения под-

5

множества. Из определения следует, что для любого множества A

справедливы, как минимум, два вложения A A и A U .

Определение 1.4. Если A B и А В , A , то A называется

собственным подмножеством множества B . В этом случае B со-

держит хотя бы один элемент, не принадлежащий A.

В теории множеств, по определению, полагают, что пустое мно-

жество является подмножеством любого множества: A.

Пустое множество и само множество A называются несобствен-

ными подмножествами множества A.

При графическом изображении множеств удобно использовать

диаграммы Венна, на которых универсальное множество обычно представляют в виде прямоугольника, а остальные множества в виде овалов, заключенных внутри этого прямоугольника (рис 1.1).

U

B

A

6

лежит хотя бы одному из двух множеств A или B (рис 1.2). Симво-

лически это можно записать следующим образом:

A B {x| x A или x B}.

U

A B

Рис. 1.2

Определение 1.6. Пересечением множеств A и B (обозначение

A B ) называется множество, состоящее из элементов x, которые принадлежат и множеству A и множеству B (рис. 1.3):

A B {x| x A и x B}.

U

A B

Рис. 1.3

Определение 1.7. Разностью множеств A и B называется множе-

ство всех тех элементов множества A , которые не принадлежат множеству B (рис. 1.4):

A \ B {x| x A и x B }.

7

U

A B

Рис. 1.4

Определение 1.8. Симметрической разностью множеств A и B

называется множество A B A \ B B \ A (рис. 1.5).

U

A B

Рис. 1.5

Определение 1.9. Абсолютным дополнением множества A называ-

ется множество всех элементов, не принадлежащих A , т.е. множе-

ство A U \ A , где U – универсальное множество (рис. 1.6).

U

A

Рис. 1.6

8

В дальнейшем вместо термина «абсолютное дополнение» мы будем

Свойства операций

Для любых множеств A,B,C выполняются следующие тождества:

1.A B B A , A B B A

(коммутативность объединения и пересечения);

(ассоциативность объединения и пересечения);

3.A B C A B A C ,

A B C A B A C

(дистрибутивность пересечения относительно объединения

иобъединения относительно пересечения);

4.A A A , A A A

(идемпотентность объединения и пересечения);

5.A U U , A U A , A A, A ,

A A U , A A

(свойства универсального и пустого множеств);

6.(A) A

9

(закон двойного дополнения);

7.A B A B , A B A B

(законы де Моргана) .

Посмотрим, как доказываются свойства операций над мно-

жествами. Прежде всего отметим, что, согласно определению, для доказательства равенства двух множеств E F необходимо устано-

вить справедливость двух вложений E F и F E .

Теперь приведем доказательства, например, третьего и седь-

мого свойств.

Доказательство равенства: A B C A B A C .

этому x A и x принадлежит хотя бы одному из двух множеств B

или C .

то x A C и поэтому x A B A C . Таким образом, вло-

жение A B C A B A C доказано.

Докажем справедливость обратного вложения:

A B C A B A C .

2 Если x A B, то x A B D, где символом D обозначено

любое множество. В данном случае D A C.

x A B , то x A и x B . Следовательно, x A и x B C , т.е. x A B C .

Если же x A C , то x A и x C , и тогда x A и x C B ,

т.е. x A C B A B C . ◄

Доказательство седьмого свойства: A B A B .

► Пусть x A B x U \ A B 3 x U и x A B

x U , x A и x B x U \ A A и x U \ B B x A B .

Аналогично доказывается обратное вложение. Пусть x A B

x A и x B x U \ A и x U \ B x U, x A и x B

x U и x A B x U \ A B A B.◄

Наряду с объединением и пересечением двух множеств можно рассматривать объединение и пересечение любого конечного

(или бесконечного) числа множеств. При этом обычно используют

3 - знак логического следования; запись P Q читают следующим

образом: «из P следует Q » или «если справедливо P , то справедливо и

Q ».