Графтар теориясының элементтері



Pdf көрінісі
бет7/13
Дата08.02.2022
өлшемі1,03 Mb.
#98807
1   2   3   4   5   6   7   8   9   10   ...   13
Байланысты:
vm 14

 
Анықтама
.
 
(
Х
,≤) д.р.ж. қарастырайық. Егер 
х≤у
және
х
орындалатындай 
z
элементі табылмаса, онда
у
элементі 
х
элементін бүркейді 
дейді.
 
Х 
ақырлы жиын болса, (
Х
,≤) д.р.ж.-ды әрбір элементін жазықтықта нүкте 
болып бейнелеуге болатындай сұлба ретінде жазуға болады. 
Егер 
у
элементі 
х
элементін бүрксе 
х
, онда 
х
және 
у
нүктелерін кесіндімен 
қосады, 
х-
ке сәйкес келетін нүктені 
у 
нүктесінен төмен орналастырады. Мұндай 
сұлбалар Хассе диаграммасы деп аталады. 
Мысалы 1.3.5

A
={
a,b,c
}. 
P
={(
a,a
),(
a,b
),(
b,b
),(
а,с
),(
c,c
)} – дербес 
реттелген қатынас (яғни рефлексивті, антисимметриялы, транзитивті), оны 
матрица [
P
]=










1
0
0
0
1
0
1
1
1
арқылы тексеруге болады. 
Р
сызықты реттілік болмайды, 
себебі
b
және 
c
салыстырмалы емес. (
А, Р
) д.р.ж. үшін Хассе диаграммасы: 
1.3.1 сурет 
 
 
 
Мысалы 1.3.6



c
b
a
A
,
,

. (Р(А), 

) = 


j
i
j
i
A
A
A
A

)
,
(
д.р.ж.
қарастырамыз, мұндағы Р(
А
) – 
А
булеаны. ( Р(
А
), 

) үшін Хассе диаграммасы 
1.3.2 сурет 1.3.3 сурет 
Мысалы 1.3.7






,
4
,
3
,
2
,
1
төрттен аспайтын натурал сандар жиынындағы 
кәдімгі реттілік қатынаспен с.р.ж. үшін Хассе диаграммасы 


Лексикографиктік қатынас. 
Лексикографиктік қатынас әртүрлі сөздіктердегі сөздердің ретпен 
жазылуының негізін қалайды. Алфавит деп аталатын 
Х
={
x,y
,…} бос емес 
символдар жиынын қарастырайық. Сөздер деп 
Х 
жиынының бірінен соң бірі 
жазылған элементтерінің ақырлы жиынтығын айтамыз. 
x
1
,x
2
,…,x
n
сөзінің 
x

элементі
i
-ші координата, ал 
n
оның ұзындығы делінеді. 


15 
Анықтама
.
 
W
(
X
) – 
Х
алфавитінің сөздерінің жиыны болсын, ≤ - 
Х 
жиынындағы реттік қатынасы, яғни (
Х
,≤) – реттелген жиын. 
Егер келесі шарттардың біреуі орындалса:
а) 
x
1
< y
1
; б) 
x
i
=y
i

i:1≤i≤m, m
; в) 
x
i
=y
i
 

i: 1≤ i ≤k, x
k+1
< y
k+1

W
(
X
)-дегі лексикографиктік реттік қатынас (белгіленуі 

немесе 
L
) келесі 
ережемен беріледі: 
x
1,
х
2,
…,x
m
 L
y
1
,y
2
,…,y
n
 



Функционалдық қатынастар (функциялар). 
Анықтама
.
 
Егер: 
а) (
x,y
1
)

f
, (
x,y
2
)


→ 
y
1
=y
2
немесе 

x

A


y

B
, (
x,y


f

б) 
D
f
=A, E
f

B
, бұл жағдайда функцияны кейде толық дейді; (егер 
D
f

A

онда 
f
дербес функция), мұндағы 
D

функцияның анықталу облысы 
E
f

мәндерінің жиыны, 
онда
 А
жиынынан 
В
жиынына 
f

А×В
бинарлық қатынас функционалдық 
немесе функция деп аталынады.
Мысалы 1.2.15
 

A
={1,2,3}, 

={(1,2);(2,3),(3,2)}

2
A
– функция, себебі 
D


A

E
f

A; P
={(1,1),(1,2),(2,3)} 

2
A
–функция емес, себебі (1,1) және (1,2) 
жұптары енеді, бұл жұптарда бірінші элементтері бірдей, екіншілері әртүрлі. 




R
x
x
x
x
P




1
;
2
қатынасы 
функция, 
себебі 
y
x

теңдігінен
1
1
2
2





y
y
x
x
4 шығады. 
P
={(
x
2
,x
)|
x

R
} –функция емес, себебі бірінші элементтері бірдей, екіншілері 
әртүрлі жұптар бар: (1,-1) 

P
, (1;1) 

P

 


R
x
x
x
P


;
- дербес функция, себебі 





;
0
P
D

R
D
P


Егер
f
= {(
x,y
)|
x

A, y

B
} функция берілсе, онда 
x
- аргумент, 
y

функцияның мәні. Функцияны белгілеудің әртүрлі жолдары: 
y
=
f
(
x
),
f: A→B,
f: x→ y; A
f
B
,
x
f
у
.
Сонымен қатар,
f
х
элементіне
y
элементін сәйкес қояды дейді. 

= {(
x,y
)| 
x

A, y

B
} – функция болсын. Ол функция: 
а) Егер (
x
1
,y


f
және (
x
2
,y


f
→ 
x
1
=x
2
(немесе
x
1
≠x
2
 → f
(
x
1
) ≠ 
f
(
x
2
)), және 
де
1

f
- дербес функция болса, онда инъективті (инъекцией, әртүрлі мәнді) деп 
аталады. 
б) Егер 

y

B

x

A
: (
x;y
)

f
, яғни 
E

= B, 
онда сюръективті (сюръекция, 
А-
ның 
В-
ға бейнесі).
в) Егер функция әрі инъективті, әрі сюръективті болса, ол биективті 
(биекцией, өзара-бірмәнді сәйкестік) деп аталады. Белгіленуі
А

В
.
Айта кетелік, егер функция дербес болса, онда, ол инъективті және 
сюръективті болған жағдайда, функция әруақытта биективті болады. Мысалы, 
 


R
y
x
x
y
y
x
P



,
,
ln
;
(
R
R
P


) - дербес функция, себебі 





,
0
P
D

R
D
P

. Ол инъективті, себебі для кез келген анықталу облысынан 
2
1
x
x

үшін 
2
1
ln
ln
x
x

; ол сюръективті, себебі
R
E
P


бірақ биекция емес, себебі табылады 
R
x

( мысалы, 
1


x
), бірақ оған бірде бір 
R
y

сәйкес келмейді. 


16 
Егер биекция 
f: А

А
, онда ол 
А 
жиынының орнына қоюы (подстановка) 
делінеді. Мысалы тепе-тең қатыная 
I
.
Мысалы 1.3.8
- Үш функция қарастырайық 
i
f

)
3
,
2
,
1
(


i
R
R

1.
x
e
x
f

)
(
1
- инъекция, бірақ сюръекция емес, себебі 
D

= R,
 
E
f
 



;
0
R
(1.3.4 суретті қара);
2.
x
x
x
x
x
x
f
4
)
2
)(
2
(
)
(
3
2





- сюръективті, бірақ инъективті емес, себебі 
2
1
x
x


, мысалы,
0
2


, бірақ 
0
)
0
(
)
2
(
2
2



f
f
,
E
f
= R
(1.3.5 суретті қара).
3. 
3
)
(
3


x
x
f
- биективті (графигі – түзу сызық).
1.3.4 сурет 1.3.5 сурет 
Айта кетелік, функциялардың қасиеттерін графиктері арқылы көруге 
болады. 
Мысалы 1.3.9
- Функциялар қарастырайық 
i
f

   
)
4
,
3
,
2
,
1
(
,
1
,
0
1
,
0


i

графиктері 1.3.6 суретте кескінделген: 
1.3.6 сурет 
График бойынша
а) 
)
(
1
x
f
- сюръекция (инъекция емес);
б) 
)
(
2
x
f
- инъекция;
в) 
)
(
3
x
f
- биекция;
г) 
)
(
4
x
f
- инъективті де, сюръективті де емес функция. 

 


17 
 
 
Жиынның қуаты туралы ұғым. 
Жиындарды элементтерінің санына қарай салыстыру қажеттігі 
туындайды. Бұл жағдайда
 
жиынның қуаты туралы ұғым пайда болады. 
Анықтама.
 
Егер 
f: А

В
биекциясы бар болса (яғни олардың арасында 
өзара бірмәнді сәйкестік орнаса (ө.б.с.)), онда 
А
және 
В 
жиындары эквивалентті 
делінеді (белгіленуі 
А~В
). 
Екі ақырлы екі жиынның элементтер саны бірдей болғанда олардың
эквивалентті болатындығы белгілі. Егер екі жиын шексіз және олардың 
арасында өзара бірмәнді сәйкестік орнаса, онда олардың ортақ қуаты болады 
делінеді. Сонымен, кез келген екі эквивалентті жиынның (ақырлы немесе 
шексіз) ортақ қуаты бар немесе бірдей қуатты болады. 
Анықтама. 
А
жиынының қуаты деп 
А
жиынына эквивалентті барлық 
жиындар класы айтылады (белгіленуі 
A
).
Үш мүмкін жағдай бар:
а) Егер 
А
ақырлы жиын және
 n
элементі бар, онда 
A

n
;
б) Егер 
А
шексіз жиын және 
N
натурал сандар жиынына эквивалентті 
болса, онда 
А
санамалы жиын деп атап, былай жазады: 
A


. Сонымен, 
санамалы жиынның барлық элементтерін нөмірлеуге болады;
в) шексіз жиын бар, оларды 
N
натурал сандар жиынымен ө.б.с. келтіруге 
болмайды. Мысалы, [0,1] кесіндісіндегі барлық нақты сандар жиыны санамалы 
емес (Кантор теоремасы). Бұл жиынның қуатын континуум (белгіленуі 
с
), ал 
мұндай қуатты жиындарды континуалды деп айту келісілген. 
А
континуалды жиын болса, онда 

2


c
A
, яғни континуумның қуаты 
санамалы жиынның барлық ішкі жиындар жиынының қуатына тең екендігі 
дәлелденген. Жалпы, кез келген 
А
жиыны үшін: Р(А) =
A
2
, мұндағы Р(А) – 
булеан. 
Санамалы жиындар мысалы:
а) 
Z
бүтін сандар жиыны, сонымен қатар 


Z
Z
,
;
б) 
Q
рационал сандардың жиыны ;
в) 

жиынының кез келген шексіз ішкі жиыны, мысалы, {2,4,6,8,…};
г) 
2
N
( жалпы 
N
N
n
~
). 
Континуалды жиындар мысалы:
а) 
R
барлық нақты сандар жиыны немесе сан осіндегі нүктелер жиыны;
б) жазықтықтың (кеңістіктің) 


R
R
R
R
R



барлық нүктелерінің жиыны;
в) санамалы жиынның барлық ішкі жиындар жиыны (яғни санамалы 
жиынның булеаны). 
Жиындар теориясында көрсетілгендей, кез келген қуатты жиын үшін 
барлық ішкі жиындар жиыны қуаты жоғарырақ болады. Сондықтан 
максималды қуатты жиын болмайды. Жиынның қуатына кардиналды сан 
немесе кардинал деп аталатын жаңа объектіге қарағандай болады. 
Кардиналдың мысалы 
а) кез келген натурал сан (ақырлы жиын қуаты ретінде);


18 
б) 



2
2
,
2
,
c

және т.б. 
Айта кетелік, екі жиын арасындағы биекцияның бар болуы бір жиынның 
қасиеттері арқылы екіншісінікін зерттеуге мүмкіндік береді, мысалы, 
А (
A

n

ақырлы жиынның кейбір қасиетін, {0,1,2,3,…
n
-1} жиыны бойынша зерттеуге 
болады. 


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   10   ...   13




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет