2Дискретка / теория множеств
.pdf1. Теория множеств
Определение:
Множество A – совокупность элементов, объединённых каким-нибудь общим свойством.
Введём следующие обозначения. Множества будем обозначать заглавными
буквами латинского алфавита A, B,... или с подстрочным индексом A1 , A2 ,... ,
элементы множества будем обозначать строчными буквами латинского алфавита a, b,... или с подстрочным индексом a1 , a2 , ... . Принадлежность
элемента x множеству A будем обозначать x A ; если элемент не
принадлежит множеству, тогда пишем x A . |
Пустое множество будем |
|||||||||
обозначать . |
|
|
|
|
|
|
|
|
||
Определения: |
|
|
|
|
|
|
|
|
||
1. |
B |
является подмножеством |
множества |
A , |
то |
|
есть |
B A |
|
|
|
x B x A , то есть каждый элемент x B обладает свойством x A . |
|
||||||||
2. |
A A , то есть является подмножеством любого множества. |
|
||||||||
3. |
Множества A и B равны, то есть A = B , A B и B A . |
|
|
|||||||
4. |
B |
является строгим подмножеством множества |
A , |
будем обозначать |
||||||
|
это B A , B A и B ≠ A . |
|
|
|
|
|
|
|
|
|
5. |
B является собственным подмножеством множества A |
B A |
и |
|||||||
|
B ≠ . |
|
|
|
|
|
|
|
|
|
Определим операции над множествами: |
|
|
|
|
|
|
|
|||
• |
Объединение множеств A и B : |
A B ={x | x A x B}, |
|
|
|
|
|
|||
• |
Пересечение множеств A и B : |
A ∩ B ={x | x A & x B} , |
|
|
|
|
|
|||
• |
Разность множеств A и B : A \ B ={x | x A & x B} , |
|
|
|
|
|
|
|||
• |
Симметрическая разность A и B : A B = (A \ B ) (B \ A), |
|
|
|||||||
• |
Дополнение множества A относительно U , где A U : |
|
|
|
|
|||||
A =U \ A . |
|
Из определения операций над множествами можно получить следующие свойства:
1. |
x A B |
x A и x B , |
2. |
x A ∩ B |
x A или x B , |
3. x A \ B x A или x B .
Пример 1.1:
Доказать равенство A B = A (B \ A)
Доказательство:
По определению, доказательство равенства эквивалентно доказательству двух утверждений:
1.A B A (B \ A),
2.A B A (B \ A).
Докажем первое утверждение: |
|
|
Пусть x A B , тогда x A или x B . Рассмотрим два случая: |
x A и x A . |
|
Пусть x A , тогда для любого множества |
C имеет место |
x A C , в |
качестве множества C возьмём множество B \ A , тогда x A (B \ A). |
||
Пусть x A , тогда x B , то есть можно |
записать, что x B \ A , тогда |
|
x A (B \ A). |
|
|
Докажем второе утверждение:
Пусть x A (B \ A), тогда x A или x B \ A . Рассмотрим два случая: x A
и x A .
Пусть x A , тогда x A B .
Пусть x A , тогда x B \ A , то по определению разности множеств x B и x A , следовательно x A B .
Пример 1.2:
Доказать утверждение A B ∩C A B и A C .
Доказательство:
Для доказательства этого утверждения нужно доказать два следующих следствия:
1. |
A B ∩C A B и A C , |
2. |
A B ∩C A B и A C . |
Докажем первое следствие:
Доказательство состоит в том, что нужно доказать одновременную принадлежность элемента x A множествам B и C . Пусть x A , тогда в силу A B ∩C , следует, что x B и x C .
Докажем второе следствие:
Пусть x A , тогда в силу A B и A C , следует, что x B и x C , по определению операции пересечения x B ∩C .
Пример 1.3: |
|
Существуют ли такие множества A , B , C , |
что A ∩ B ≠ , A ∩C = , |
(A ∩ B )\ C = . |
|
Решение: |
|
Будем считать, что такие множества существуют. |
Тогда x A ∩ B в силу |
того, что A ∩ B ≠ , по определению операции пересечения x A и x B . Так
как x A и A ∩C = , тогда x C . Так как x A , |
x B и x C , следовательно |
x (A ∩ B )\ C , тогда возникает противоречие с |
равенством (A ∩ B )\ C = . |
Следовательно ← x A ∩ B , поэтому множеств |
удовлетворяющих условию |
задачи не существует. |
|
Пример 1.4:
Доказать равенство A ∩ B = A B .
Доказательство:
По определению, доказательство равенства эквивалентно доказательству двух утверждений:
1.A ∩ B A B ,
2.A ∩ B A B .
Докажем первое утверждение:
Пусть x A ∩ B x U \ (A ∩ B ) x U и x A ∩ B x U & x A или x U & x B . Если x U & x A , тогда x A и следовательно x A B . Если x U & x B , тогда x B и следовательно x A B .
Докажем второе утверждение:
Пусть x A B , тогда по определению операции объединения x A или x B . Если x A , тогда x U \ A , следовательно x U и x A , если элемент не принадлежит какому-либо множеству C , то он не будет принадлежать и
пересечению данного множества C |
с любым другим множеством, то есть |
||
|
|
|
|
x A x A ∩ B , из этого следует |
x U \ (A ∩ B ), то x A ∩ B . Аналогично |
проводится доказательство для случая x B .
Пример 1.5:
Доказать равенство A \ (A \ B )= A ∩ B .
Доказательство:
Для доказательства будем использовать эквивалентные преобразования:
x A \ (A \ B ) x A & x A \ B x A & (x A x B ) (x A & x A)(x A & x B ) x A & x B x A ∩ B .
2. Декартово произведение множеств
Определения: |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
1. |
Мощность множества A – это число его элементов, обозначается |
|
A |
|
. |
|||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||
2. |
Мощность |
множеств |
всех |
подмножеств |
множества |
A |
равна |
|||||||||||||||||||||||
|
|
P (A) |
|
= 2 |
|
A |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
3. |
Декартово |
произведение |
множеств A |
и B |
– есть |
множество |
|
вида |
||||||||||||||||||||||
|
|
A × B = { x, y |
|
x A & y B}. |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
4. |
Мощность |
декартова |
произведения |
множеств |
A и |
B |
равна |
|||||||||||||||||||||||
|
|
A × B |
|
= |
|
A |
|
|
B |
|
. |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
Пример 2.1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
Пусть A = {1, 2, 3} и B = {a, b} . |
Найти декартовы произведения A × B и |
||||||||||||||||||||||||||||
B × A . Найти мощности этих декартовых произведений. |
|
|
|
|
|
|
||||||||||||||||||||||||
Решение: |
|
|
|
|
|
|
|
|
|
|
|
По определению декартова произведения:
A × B = {1, a , 1, b , 2, a , 2, b , 3, a , 3, b},
B × A = { a,1 , b,1 , a, 2 , b, 2 , a, 3 , b, 3}.
Очевидно, что A × B ≠ B × A . Мощности полученных декартовых произведений
A × B = B × A = A B = 3 2 = 6 .
Пример 2.2
Доказать равенство (A B )× C = (A× C ) (B × C ).
Доказательство:
Для доказательства равенства докажем два утверждения:
1.(A B )× C (A × C ) (B × C ),
2.(A B )× C (A × C ) (B × C ).
Докажем первое утверждение:
Пусть |
x, y (A B ) C , тогда x A B и y C . Если x A и y C , тогда |
x, y A C , |
следовательно x, y (A C ) (B C ). Если x B и y C , тогда |
x, y B C , следовательно x, y (A C ) (B C ).
Докажем второе утверждение: |
|
|
|
|
Пусть |
x, y (A C ) (B C ), |
тогда x, y A C или |
x, y B C . |
Если |
x, y A C , |
тогда x A и y C , |
следовательно x A B |
и y C , |
тогда |
x, y (A B ) C . Аналогично доказывается для случая x, y B C .
Пример 2.3 |
|
|
|
|
|
|
|
|
|
Доказать |
(A B ) (C D ) (A C ) (B D ), |
при |
каких |
A, B, C, D ≠ |
|||||
получается равенство? |
|
|
|
|
|
|
|
|
|
Доказательство: |
|
|
|
|
|
|
|
|
|
Пусть x, y (A B ) (C D ), |
тогда |
x, y A B |
или |
x, y C D , |
то |
||||
(x A x C )& (y B y D ), из |
этого |
условия следует, |
что |
x A C |
и |
||||
y B D , тогда |
x, y (A C ) (B D ). |
|
|
|
|
|
|
||
Попробуем сделать |
доказательство |
в обратную |
|
сторону. Пусть |
|||||
x, y (A C ) (B D ), |
тогда x A C |
и y B D , из |
этого |
следует, |
что |
(x A x C )& (y B y D ), тогда следует рассмотреть четыре варианта:
1.x A и y B , тогда x, y A B , следовательно x, y (A B ) (C D ),
2.x C и y D , тогда x, y C D , следовательно x, y (A B ) (C D ),
3.x A и y D , тогда x, y A D ,
4.x C и y B , тогда x, y C B .
Тогда возникают дополнительные условия: D B и C A или B D и A C
или A = C или B = D .
3. Бинарные отношения, функции, порядок.
Определения:
1.Бинарным отношением между элементами множеств A и B
называется любое подмножество декартова произведения R A B .
2. Если в предыдущем определении A = B , то R – бинарное отношение на A .
3. Обозначение x, y R xRy .
4. Область определения бинарного отношения R есть множество
δ R ={x y : x, y R}.
5. Область значений бинарного отношения R есть множество
ρR ={y x : x, y R}.
6.Дополнение бинарного отношения R между элементами A и B есть множество −R = (A B )\ R .
7. Обратное отношение для бинарного отношения R есть
R−1 ={ y, x x, y R}.
8. Произведение отношений R1 A B и R2 B C есть отношение
R1 R2 ={ x, y z B : x, z R1 & z, y R2 }.
9.Отношение f называется функцией из A в B , обозначается f : A → B ,
если:
|
• δ f = A и ρ f B , |
|
|
|
|
|
|
||
|
• x, y, z x, y f и x, z f y = z . |
|
|
|
|
|
|||
10. |
Отношение |
f |
называется функцией |
из A |
на |
B , |
обозначается |
||
|
HA |
если: |
|
|
|
|
|
|
|
|
f : A → B , |
|
|
|
|
|
|
||
|
• δ f = A и ρ f = B , |
|
|
|
|
|
|
||
|
• x, y, z x, y f и x, z f y = z . |
|
|
|
|
|
|||
11. |
Если f – функция, то x, y |
f обозначают y = f (x ). |
|
|
|||||
12. |
Тождественная функция iA : A → A определяется iA (x ) = x . |
||||||||
13. |
Функция f |
называется 1-1-функцией, |
если |
x1 , x2 , y y = f (x1 ) и |
|||||
|
y = f (x2 ) x1 = x2 . |
|
|
|
|
|
|
||
14. |
Функция |
f : |
HA |
осуществляет |
взаимно |
однозначное |
|||
A → B |
|||||||||
|
соответствие |
между множествами A |
и |
B , если |
f |
является 1-1- |
|||
|
функцией. |
|
|
|
|
|
|
|
|
15.Множества A1 , A2 ,..., Ar из P (A) образуют разбиение множества A ,
если:
•Ai ≠ , i =1, r ,
•A = A1 A1 ... Ar ,
•Ai ∩ Aj ≠ , i ≠ j ,
Ai – блоки разбиения.
16.Бинарное отношение R на множестве A может иметь следующие свойства:
•рефлексивность x A x, x R ,
•иррефлексивность x A x, x R ,
•симметричность x, y A x, y R y, x R ,
• |
антисимметричность x, y x, y R и y, x R x = y , |
• |
транзитивность x, y, z x, y R и y, z R x, z R , |
•дихотомия x ≠ y либо x, y R , либо y, x R .
17.Эквивалентность на множестве A – это рефлексивное, симметричное
итранзитивное отношение на A .
18.Класс эквивалентности элемента x по эквивалентности R есть множество [x]R ={y x, y R}.
19.Фактор множество A по R есть множество классов эквивалентности элементов множества A и обозначается A / R .
20.Свойства классов эквивалентности:
•классы эквивалентности образуют разбиение множества A ,
•любому разбиению множества A соответствует отношение эквивалентности, классы эквивалентности которого совпадают с блоками указанного разбиения,
•x A попадает в некоторый класс эквивалентности из A / R ,
•классы эквивалентности либо не пересекаются, либо совпадают.
21.Предпорядок на множестве A – это рефлексивное и транзитивное отношение на A .
22.Частичный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на множестве A .
23.Линейный порядок на множестве A – это рефлексивное, транзитивное
иантисимметричное отношение на множестве A , удовлетворяющее условию дихотомии.
24.Пусть ≤ – отношение порядка на множестве A , тогда:
•минимальный элемент x множества A – это элемент для
|
которого ← y |
y < x , |
• |
максимальный элемент x множества A – это элемент для |
|
|
которого ← y |
x < y , |
• |
наименьший элемент x множества A – это элемент для которого |
|
|
y x ≤ y , |
|
• наибольший элемент x множества A – это элемент для которого
y y ≤ x .
25.Если между множеством A и множеством натуральных чисел N можно установить взаимно однозначное соответствие, то множество
A – счётное множество.
Пример 3.1 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Пусть |
A = {1, 2, 3} и B = {a, b} , бинарное |
|
отношение |
определим |
||||||||
R = { 1, a , |
1, b , |
2, b }. |
Будет ли R функцией? |
Как |
изменить |
бинарное |
|||||||||
отношение R , чтобы R стала функцией? |
|
|
|
|
|
|
|
|
|||||||
Решение: |
|
|
|
|
|
|
|
|
|
{ } |
{ |
} |
|||
Рассмотрим первый пункт определения функции |
|
R |
|
||||||||||||
δ |
|
= |
1, 2 |
≠ 1, 2, 3 = A , |
|||||||||||
следовательно |
R |
не |
является функцией. Добавим |
в |
R |
|
пару |
3, a , |
тогда |
||||||
|
R |
{ |
} |
{ |
} |
= A , |
но существуют пары 1, a |
и |
|
, |
что противоречит |
||||
δ |
|
= 1, 2, 3 |
= 1, 2, 3 |
1, b |
второму пункту определения функции, для этого исключим одну пару,
например 1, b и |
определим |
бинарное |
отношение |
R′ = { 1, a , |
2, b , 3, a }, |
||||
которое будет функцией. |
|
|
|
|
|
|
|
||
Пример 3.2 |
|
|
|
|
|
|
|
|
|
Пусть |
A = {1, 2, 3} и пусть бинарное |
|
отношениеR |
на A |
имеет |
вид |
|||
R = { 1,1 , 2,1 , |
2, 3 }. |
Какими |
свойствами |
обладает |
данное |
бинарное |
|||
отношение? |
|
|
|
|
|
|
|
|
|
Решение: |
|
|
|
|
|
|
|
|
|
Это отношение |
не обладает свойством рефлексивности, |
так |
как |
||||||
x = 2 A : x, x R . |
Также R не |
обладает |
свойствами иррефлексивности и |
||||||
симметричности. |
Обладает |
свойствами |
транзитивности |
и |
|||||
антисимметричности, так как пар вида x, y |
, |
y, z и |
y, x |
нет в R . |
|
|
Пример 3.3
Пусть R = { x, y x, y N y mod x = 0}. Найти δ R , ρR , R−1 , R R, R R−1 , R−1 R .
Решение:
δR ≡ {x y x, y R} = {x x y = x: x mod x = 0} = Ν ,
ρR ≡ {y x x, y R} = {y y x = 1: y mod1 = 0} = Ν ,
R−1 ≡{ y, x x, y R}={ y, x y mod x = 0},
R R ≡{ x, y z x, z R & z, y R}={ x, y z = x: x mod x = 0 & y mod x = 0}= R ,
R R−1 ≡ { x, y z x, z R & y, z R}= { x, y z = xy :(xy )mod x = 0 & (xy )mod y = 0}= N 2 ,
R−1 R ≡ { x, y z z, x R & z, y R}= { x, y z = 1 : x mod1 = 0 & y mod1 = 0}= N 2 .
Пример 3.4
Доказать (R1 R2 )−1 = R2−1 R1−1 .
Доказательство:
Пусть |
x, y (R1 R2 )−1 |
y, x R1 R2 z y, z R1 и z, x R2 z |
|||
z, y R−1 |
и x, z R−1 |
x, y R−1 |
R−1 . |
||
1 |
|
2 |
|
2 |
1 |
Пример 3.5
Для каких бинарных отношений R имеет место R−1 = −R ?
Решение:
R A B , тогда возможны два случая:
1. A ∩ B ≠ .
Тогда x A ∩ B . Если x, x R , тогда x, x R−1 и по условию R−1 = −R
следует x, x −R , тогда |
x, x R . |
|
|
2. A ∩ B = . |
|
|
|
Пусть x A и |
y B и |
x, y R , тогда y, x R−1 , тогда по |
условию |
R−1 = −R следует |
y, x −R y A и x B , то есть x A ∩ B и |
y A ∩ B , |
по предположению таких x и y не существует.
Тогда можно сделать вывод, что при условии A, B ≠ , то R−1 ≠ −R .
Пример 3.6
На множестве D – всех действительных чисел определим отношение R
следующим образом: x, y R (x − y ) – рациональное число. Доказать, что
R – отношение эквивалентности.
Доказательство:
Для доказательства отношения эквивалентности следует доказать рефлексивность, симметричность и транзитивность.
1.рефлексивность:
x D x − x = 0 – рационально число,
2.симметричность:
если |
x, y R , |
|
то |
x − y = |
p |
|
– |
рационально число, |
тогда |
||||||||||||
|
q |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
y − x = −(x − y ) = − |
p |
– рациональное число, тогда |
y, x R , |
|
||||||||||||||||
q |
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. транзитивность: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
если |
x, y R |
и |
|
y, z R , |
|
то |
|
x − y = |
p |
|
и |
y − z = |
m |
, |
сложим |
||||||
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q |
|
|
n |
|
||
|
p |
+ |
m |
= x − z = |
np + mq |
– рациональное число, тогда |
x, z R . |
|
|||||||||||||
|
|
|
|
|
|||||||||||||||||
|
q n |
|
nq |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Следовательно R есть отношение эквивалентности. |
|
|
|
|
|
||||||||||||||||
Пример 3.7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Доказать, что если |
f : |
HA |
и g |
: B |
HA |
|
HA |
|
|||||||||||||
A → B |
→C , то |
f g : A →C . |
|
Доказательство:
Для доказательства докажем оба пункта определения функции. Для
доказательства |
первого пункта |
необходимо доказать, что x A |
z C : |
||||||||||||||
x, z f g |
и z C |
x A : |
x, z |
f g . Рассмотрим x пару |
x, z |
f g , тогда |
|||||||||||
y B : |
x, y f |
и |
y, z g , |
такой |
y |
всегда найдётся |
по |
определению |
|||||||||
функций |
f |
и g . Рассмотрим z |
пару |
x, z f g , |
тогда y B : |
x, y f |
и |
||||||||||
y, z g , |
такой |
y |
всегда найдётся по определению функций |
f |
и |
g . Для |
|||||||||||
доказательства |
второго пункта |
определения |
предположим, |
что |
z1 ≠ z2 : |
||||||||||||
x, z1 |
f g |
и |
x, z2 |
f g , |
тогда |
y1 , y2 : |
x, y1 |
f , |
x, y2 |
f , |
|
y1 , z1 g |
и |
||||
y2 , z2 |
g , |
по определению функций |
f |
и g |
следует, что y1 = y2 , |
из чего |
следует z1 = z2 .
Пример 3.8
Разбиение плоскости D2 состоит из лучей, выходящих из начала координат. Выписать отношение эквивалентности R , соответствующее данному разбиению, выписать классы эквивалентности.
y |
x |
Решение: