2Дискретка / Метода / 2.Теория множеств

	Содержание
I. Теория множеств.............................................................................................................................		2
Глава 1.	Множества ..................................................................................................................	2
1.1. Основные определения ..........................................................................................................		2
1.2. Основные операции теории множеств. ................................................................................		3
1.3. Обозначения наиболее часто используемых множеств......................................................		5
1.4. Диаграммы Венна...................................................................................................................		5
1.5. Основные законы теории множеств .....................................................................................		6
1.6. Декартово произведение и отношения.................................................................................		7
Глава 2.	Бинарные отношения.................................................................................................	8
2.1. Основные определения ..........................................................................................................		8
2.2. Специальные бинарные отношения....................................................................................		12
Глава 3.	Функции и операции................................................................................................	16
Глава 4.	Алгебраические структуры .....................................................................................	19

I. ТЕОРИЯ МНОЖЕСТВ

ГЛАВА 1. МНОЖЕСТВА

Точного определения понятия "множество" в математике нет. Создатель теории множеств немецкий математик Георг Кантор (1845-1918гг.) использовал следующее "определение": "множество или совокупность – это собрание оп- ределенных и различных объектов нашей интуиции или интеллекта, мыслимое в качестве целого".

1.1. Основные определения

Обычно множества обозначают прописными латинскими буквами A, B, ... , Z, а элементы, принадлежащие данным множествам, – строчными латинскими буквами a, b,..., z.

1)Множество может быть задано с помощью перечисления (указания) всех его элементов, заключенных в фигурные скобки. Например, запись A={1,5} зада- ет множество A, которое состоит из двух элементов – чисел 1 и 5.

2)Множество может быть задано с помощью характеристического свойства его элементов. Например, множество A, состоящее из элементов x, являю- щихся четными числами, можно записать следующим образом: A={x|x – чет- ное число}. В такой записи слева от вертикальной черты задается вид эле- мента (единичный элемент, пара элементов, множество, цепочка символов и т.п.), а справа – характеристическое свойство.

Если множество содержит конечное число элементов, то его называют ко-

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

пись “a A” читается: “элемент a принадлежит множеству A” или “для элемента a выполняется характеристическое свойство множества A”. Запись “a A” чита- ется: “элемент a не принадлежит множеству A” или “для элемента a не выпол- няется характеристическое свойство множества A”.

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

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

Подмножеством множества B считают также пустое множество и само множество B; их называют несобственными подмножествами; остальные под-

множества называют собственными подмножествами.

Если множества A и B заданы перечислением их элементов, то для доказа- тельства включения A B достаточно проверить, что все элементы множества A

присутствуют в множестве B. В общем случае, для произвольных множеств A и B структура доказательства A B, должна иметь вид:

«Пусть a A, тогда …, …, тогда a B ».

Отметим, что фраза « a A» означает, что для a выполняется характеристика множества A, и наоборот, если показано, что для некоторого элемента b выпол- няется характеристика множества B, то можно записать «b B ».

Совокупность всех подмножеств множества A называется булеаном и обо- значается P(A)={B|B A}. Например, булеаном множества A={a, b, c} будет множество P(A)={ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Множества A и B называют равными или совпадающими (обозначается A=B), если они состоят из одних и тех же элементов, т.е. если B A и A B. Та- ким образом, чтобы доказать равенство множеств, требуется доказать два включения.

1.2. Основные операции теории множеств.

На булеане P (U ) определяются операции над множествами A P (U ) и B P (U ).

Объединением множеств A и B называется множество C, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A, B. Обо-

значение: C=A B. Символическая запись: A B={x|x A или x B}.

Пересечением множеств A и B называется множество C, состоящее из всех тех элементов, которые принадлежат каждому из множеств A и B. Обозначение:

C=A∩B. Символическая запись: A∩B={x|x A и x B}.

Объединение или пересечение некоторой совокупности (более двух эле- ментов) множеств может быть записано следующим образом:

а) A ( ∩ A ) – объединение (пересечение) всех множеств, являющихся

A S A S

элементами множества S;

b) Ai (∩Ai )– объединение (пересечение) множеств Ai , где индекс i про-

i I i I

бегает все значения множества I;

k	k
c) Ai	(∩Ai ) – объединение (пересечение) множеств Ai , где индекс i
i=1	i=1

пробегает все значения от 1 до k;

∞∞

d)Ai (∩Ai )– объединение (пересечение) бесконечного количества мно-

i=1 i=1

жеств.

Разностью множеств A и B называется множество C, состоящее из всех тех элементов множества A, которые не принадлежат множеству B. Обозначе- ние: C=A\B. Символическая запись: A\B={x|x A и x B}.

Симметрической разностью множеств A и B называется множество C, со- стоящее из всех тех элементов, которые принадлежат только одному из мно- жеств A, B. Обозначение: C= A B. Символическая запись: A B={x|x A и x B

или x A и x B}=(A\B) (B\A).

Дополнением к множеству A называется множество, состоящее из всех тех элементов универсума U, которые не принадлежат множеству A.

Обозначение: A Символическая запись: A =U\A.

Старшинство операций (операции даны по убыванию приоритетов)

			\	∩

Пример 1. Пусть U={a, b, c, d, e, f, g}, A={a, b, c, d}, B={c, d, e, f}. Определить

A B, A∩B, A\B, B\A, A B, A , B .

	4A B={a, b, c, d, e, f};	A\B={a, b};
			A ={e, f, g};
	A∩B={c, d};	B\A={e, f};
		A B={a, b e, f};	B	={a, b, g}3

Пример 2. Доказать, что для произвольных множеств A и B если A B , то

B A .

Необходимо доказать, что B A , поэтому структура доказательства будет иметь вид «Пусть a B , тогда …, …, тогда a A ».

4Пусть a B , тогда по определению дополнения a U \ B , где U – универсальное множество. Из определения разности множеств из того, что a U \ B , следует, что a U иa B . По условию задачи известно, что A B , т.е., что все элементы множества A есть в множестве B. Так как a B , то эле- мента a в множестве B нет, а следовательно его нет и в множестве A. Если эле- мента a нет в множестве A, то можно записать, что a A. Итак, мы установили, что a U и a A, а это значит, что a A .3

Аналогично доказывается обратное утверждение: если B A , то A B . Такие доказательства можно сократить, если использовать следующие обо-

значения:

–символ « » в выражениях типа P Q будет означать, что «если справедливо P, то справедливо Q» или «из того, что P, следует Q» и т.п.;

–символ « » будет означать: «тогда и только тогда, когда», «если и толь- ко если» и т.п;

–символы «df» будут заменять слово «определение».

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

Пусть необходимо доказать, что если B A , то A B .

df "дополнение"		т.к.						df "дополнение"
			B		A
4a A a		a						a B 3.
	A						B

1.3. Обозначения наиболее часто используемых множеств

N – множество всех натуральных чисел (то есть N = {1,2,3,…} );

Z – множество всех целых чисел;

Z+ – множество целых неотрицательных чисел (Z+ = N {0});

Z– – множество целых неположительных чисел (Z– = Z\N); Q – множество всех рациональных чисел;

R – множество всех действительных чисел;

R+ – множество неотрицательных действительных чисел; R– – множество неположительных действительных чисел.

1.4. Диаграммы Венна

Операции множеств и связанные с ними соотношения представляются на- глядно с помощью диаграмм Эйлера-Венна (названных по имени русского ма- тематика Леонарда Эйлера (1707-1783гг.) и английского логика Джона Венна (1834-1923гг.). На этих диаграммах любые множества изображаются кругами, пересекающими друг друга, исходя из того, что внутренними точками круга изображаются элементы множества. Общей частью двух кругов, пересекающих друг друга, представляются возможные общие элементы двух множеств. Уни- версальное множество изображается в виде прямоугольника.

U

A B

A B

U

A B

A \ B

U

U

A B

A ∩ B

U

A B

B \ A

U

			A				B
	A

		A B
	A

1.5.Основные законы теории множеств

1.Коммутативность операций и ∩:

а) A B=B A

б) A∩B=B∩A

2.

Ассоциативность операций и ∩:

а) A (B C)=(A B) C

б) A∩(B∩C)=(A∩B) ∩C

3.

Законы идемпотентности операций и ∩:

а) A A=A

б) A∩A=A

4.

Законы дистрибутивности:

а) A (B∩C)=(A B) ∩ (A С)

б) A∩(B C)=(A∩B) (A∩С)

5.

Законы поглощения:

а) A (A∩B)=A

б) A∩(A B)=A

6.

Законы де Моргана:

а)

=

∩

б)

=

A B

A

B

A ∩ B

A

B

7.

Законы пустого и универсального множеств:

A = A

A∩ =

A∩

=

A

A U=U

A∩U= A

A

=U

A

=

= U

U

8.

Закон двойного отрицания:

A = A

Пример 3. Доказать, что относительно данного универсального множества U дополнение A любого множества A , если A U , единственно.

4Для доказательства единственности дополнения A множества A U предположим, что существует два множества B и C, каждое из которых удовле- творяет требованиям дополнения множества A, т.е. их пересечение с A пусто, а объединение с A дает U:

а) B ∩ A = ;	б) C ∩ A = ; в) B A =U ;			г) C A = U .
Очевидно, что	B = B ∩U . С учетом условия г)			B = B ∩ (C A). Так как
B ∩ (C A) = (B ∩ C ) (B ∩ A), то с учетом условия а) B = (B ∩ C ) = B ∩ C .
Аналогично, исходя из условий в), б) получим:
C = C ∩U = C ∩ (B A) =		(C ∩ B) (C ∩ A) = (C ∩ B) = C ∩ B .
Итак, мы получили, что		B = B ∩ C и	C = C ∩ B . Так как C ∩ B = B ∩ C
(коммутативность операции пересечения),			то B = C ,	что и требовалось дока-

зать.3

1.6. Декартово произведение и отношения

Декартовым или прямым произведением множеств A1, A2, ... , An называет- ся множество {(x1,x2,...,xn)|x1 A1, x2 A2, ... , xn An}, обозначаемое через

n

A1×A2×...×An , или ∏ Ak .

k =1

Если A1=A2=...=An, то множество A1×A2×...×An называется n-ой декартовой степенью множества A и обозначается An. Положим по определению A0= .

Если хотя бы одно из множеств Ai пусто, то A1×A2×...×An= .

Пример 4. Пусть A={1,2}, B={a, b}, C={c, d}, D={ d | dN и x<3}, Q= . Найти

A×B, B×A, A×D, D×A, A2, A×B×C, (A×B)×C, A×(B×C), (A×Q)×C, A×(Q×C).

4A×B = {(1, a), (2, a), (1, b), (2, b)}. B×A = {(a, 1), (a, 2), (b, 1), (b, 2)}.

Определим множество D, задав его перечислением: D={1,2}. Так как D=A, то A×D = D×A = A2. Далее по определению × получаем:

A×D = D×A = A2 = {(1, 1), (2, 1), (1, 2), (2, 2)}. A×B×C = { (1, a, c), (2, a, c), (1, b, c), (2, b, c),

(1, a, d), (2, a, d), (1, b, d), (2, b, d) }. (A×B)×C = { ((1, a), c), ((2, a), c), ((1, b), c), ((2, b), c),

((1, a), d), ((2, a), d), ((1, b), d), ((2, b), d) }. A×(B×C) = { (1, (a, c)), (2, (a, c)), (1, (b, c)), (2, (b, c)),

(1, (a, d)), (2, (a, d)), (1, (b, d)), (2, (b, d)) }.

Для определения множеств (A×Q)×C и A×(Q×C) необходимо вначале опре- делить множества A×Q и Q×C. Так как множество Q пустое, то и множества A×Q и Q×C тоже будут пустыми, так как в Q не найдется элементов, чтобы по- ставить их в пару к элементам множеств A и C. Следовательно,

A×Q=Q×C=(A×Q)×C=A×(Q×C)= . 3

Из этого примера видно, что в общем случае (A×B)×C≠A×(B×C), A×B≠B×A, следовательно, × не обладает свойством ассоциативности и коммутативности.

N-местным отношением (соответствием) P, или n-местным предика-

том P на множествах A1, A2, ... , An, называется некоторое подмножество пря- мого произведения A1×A2×...×An. Элементы x1, x2, ... , xn (где x1 A1, x2 A2, ... , xn An) называются связанными соответствием P тогда и только тогда, когда

(x1, x2, ... , xn) P. Если A1=A2=...=An=A, т.е. P An, то чаще используется термин «отношение». В этом случае говорят, что P – n-местное отношение (предикат)

на множестве A. Если же A1≠A2≠...≠An, то обычно используют термин «соот- ветствие». Примерами соответствий являются: функции, отображения, преоб- разования, операции и др.

Наиболее используемыми являются унарные и бинарные отношения (соот- ветствия).

При n=1 отношением P является подмножеством множества A и называет-

ся унарным (одноместным) отношением (или соответствием), или свойст-

вом, на множестве A. Это означает, что в множество P попадут только те эле- менты множества A, которые обладают указанным в отношении признаком.

При n=2 отношение P называется бинарным (двухместным) отношением (или соответствием).

Бинарные отношения используются для определения каких-то взаимосвя- зей, которыми характеризуются пары элементов множества, т.е. если отноше- ние P определено на множестве A×B (P A×B), то это значит, что в множество P попадут только те пары множества A×B, между элементами которых имеет ме- сто указанное отношение.

ГЛАВА 2. БИНАРНЫЕ ОТНОШЕНИЯ

2.1. Основные определения

Бинарные отношения используются для определения каких-либо взаимо- связей, которыми характеризуются пары элементов множества, т.е. если отно- шение P определено на множестве A×B (P A×B), то это значит, что в множест- во P попадут только те пары множества A×B, между элементами которых имеет место указанное отношение.

Способы задания бинарных отношений:

Так как отношения – это множества, то их можно задавать перечислением или характеристическим свойством. Кроме того, для бинарных отношений, оп-

ределенных на конечных множествах, есть еще несколько способов их задания. 1. Бинарное отношение P A×B, где A={a1, a2, …, an}, B={b1, b2, …, bm}

может быть задано (m,n)-матрицей (таблицей) (m строк, n столбцов), в которой элемент pij , стоящей на пересечении i-ой строки и j-ого столбца, равен 1, если

между элементами ai и bj имеет место отношение P, или 0 в противном случае.

Например, отношение P={(a,b) | a A, b B
и a>b}, где A={6,7,8}, B={5,6,7,8,9} заданно ха-		P		5	6	7	8	9
рактеристическим свойством. Это же отноше-		6		1	0	0	0	0
ние может быть определено перечислением		7		1	1	0	0	0
P={(6,5), (7,5), (7,6), (8,5), (8,6), (8,7)} или мат-		8		1	1	1	0	0
рицей отношения:

2. Если P A×B, A и B – числовые множества, то отношение P можно изобразить как множест-

во точек на плоскости, где каждая точка пред-

ставляет собой пару из множества P. Например,

P={(2,1), (1,2), (2,2), (3,2), (4,2), (1,3), (2,4)}, где A={1,2,3,4,5}, B={1,2,3,4}.

4

3

2

1

1 2 3 4 5

3. Если P A B, то отношение P можно изобразить в виде диаграммы, состоящей из узлов и стрелок, при этом узлам взаимно однозначно со- ответствуют элементы множеств A и B, а стрелка соединяет элемент a и с элементом b только в том случае, если (a, b) P. Например,

P={( a,2), (a,3), (b,1), (c,1)}, A={a, b, c}, B={1, 2, 3}.

4. Если P A2, то бинарное отношение может быть задано в виде графа, вершины которого – эле- менты множества, а дуги направленные от a к b озна- чают, что (a, b) P. Например,

P={( a, c), (c, a), (b, a), (b, b) ,(a, d)}, где A={a, b, c, d}.

Способы задания 2-4 иногда называют графиче-

скими способами отображения бинарных отношений.

a

b

c

a

c

1 2

3

b

d

Пусть P – некоторое бинарное отношение.

Областью определения P называется множество

δP={x|(x,y) Ρ для некоторого y}. Областью значений P называется множество ρP={y|(x,y) Ρ для некоторого x}.

Так как бинарное отношение по сущности есть множество, то для него оп- ределены все операции, которых определены для множеств: пересечение, объе- динение, разность, симметрическая разность и дополнение. При этом все зако- ны алгебры множеств сохраняют свою силу. Кроме того, определяются другие операции над отношениями, в том числе:

Обратным к P отношением называется множество

P–1={(y,x)|(x,y) Ρ }.

Композицией бинарных отношений P1 A B и P2 B C называется множе-

ство P3= P P , где P3 A C и P3={(x,y) | x A, y C и найдется z B такой, что
1	2

(x,z) P1 и (z,y) P2}.

Образом множества X относительно P называется множество P(X)={y|(x,y) Ρ для некоторого x X}.

Множество P−1(Y)={x|(x,y) Ρ для некоторого y Y} называется прообразом множества Y относительно P.

Пример 5. Найти δP , ρP , P−1 , P P , P−1 P , P P−1 для отношения:

P = {( x, y) x, y R, y = x +1} .

41) δP = R+ . Для доказательства равенства множеств необходимо доказать два включения δP R+ и δP R+ .

а) По определению δP R , но так как функция квадратного корня не оп-

ределена для неположительных чисел, то δP R \ {x x R, x < 0}, т.е. δP R+ .

б) Покажем, что R+ δP . Пусть x R+ , тогда значение выражения x +1– число вещественное, поэтому можно утверждать, что найдется y, например y = x +1, такой что ( x, y ) P . Таким образом, мы показали, что для элемента x выполняется характеристика множества δP . Следовательно, x δP .

Далее доказательства равенства множеств будем приводить в сокращенной форме.

2) ρ

P

=

{

x

x R, x >1 .

{

}

а)

ρ

P

R \

x

x R, x <1 ,

так как функция квадратного корня принимает

}

только положительные значения.

{

}

P

, так как найдется x, например x = ( y −1)2 , такой, что

б)

x

x R, x >1

ρ

( x, y ) P (действительно, y =

( y −1)2 +1 и при этом x = ( y −1)2 – число веще-

ственное).

3) P−1 ={( x, y )

x, y R, x = y +1} .

4) P P = {( x, y)

x, y R, x ≥ 0 , y ≥ 2, y = x +1 +1}.

а) P P {( x, y)

x, y R, x ≥ 0 , y ≥ 2, y = x +1 +1} .

Пусть ( x, y ) P P ,

тогда существует вещественный z, такой что ( x, z ) P

и ( z, y) P . Учитывая, характеристики множества P, для x, y, z можно записать

z = x +1 и

y = z +1, поэтому x обязательно неотрицательное число, а y ≥ 2 .

Подставляя z из первого выражения во второе получаем y =

x +1 +1. Сле-

довательно,

( x, y) {( x, y)

x, y R, x ≥ 0 , y ≥ 2, y =

x +1 +1} .

б) {( x, y)

x, y R, x ≥ 0 , y ≥ 2, y =

x +1 +1} P P , так

как если пара

( x, y ) принадлежит множеству

{( x, y)

x, y R, x ≥ 0 , y ≥ 2, y =

x +1 +1}, то

найдется z,

например z =

x +1

такой,

что ( x, z ) P и ( z, y) P . Следователь-

но, ( x, y ) P P .

5) P P−1 = {( x, y)

x, y R+ , x = y} .

а) P P−1 {( x, y)

x, y R+ , x = y}.

Пусть

( x, y ) P P−1 ,

тогда существует

вещественный

z, такой что

( x, z ) P и ( z, y) P−1 . Учитывая это, характеристики множеств P и P–1 для x, y,