ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

«МИРАС» УНИВЕРСИТЕТІ

А.С.Муратов

ДИСКРЕТТІ МАТЕМАТИКА Оқу-әдістемелік құрал

Шымкент – 2017жыл

ӘОЖ 510(075.8) ББК 22.12я73

Кафедра мәжілісінде талқыланды және қаралды (10.11.17ж. №4 хаттама)

ЭҚАТ факультетінің әдістемелік комиссиясымен қаралды (14.11.17ж. №4 хаттама) Мирас университетінің Оқу-әдістемелік кеңесінде қаралды ( 20.11.17ж. № 4 хаттама)

Рецензенттер:

1. Мусабекова Л.М. – техника ғылымдарының докторы, «Есептеу техникасы және бағдарламалық қамтамасыз ету» кафедрасының доценті, М.Әуезов атындағы ОҚМУ

2. Дүйсенов Н.Ж. – АТТ кафедрасының аға оқытушысы, т.ғ.к. Мирас университеті Муратов А.С., т.ғ.д., профессор

Дискретті математика

Оқу-әдістемелік құрал.Шымкент,2017ж., 164бет.

Оқу-әдістемелік құралда дискретті математика курсының барлық қажетті мәліметтерін қамтылған. Дискретті математиканың ғылымда алатын рөлі мен орны айқындалған.

Оқу-әдістемелік құрал - жоғары оқу орындарының 5В070300 – «Ақпараттық жүйелер» мамандығының барлық оқу түрлерінің студенттері мен ұстаздар қауымына және ақпараттық жүйелерді зерттеумен айналысатын барша жүйе қолданушыларына арналған.

ӘОЖ 510(075.8) ББК 22.12я73

А.С.Муратов, 2017

Кіріспе

Дискретті математика – ХХ ғасырда қарқынды дамыған математика тармағы. Оның ролі мен орны негізінен үш фактормен анықталады:

− дискретті математиканы компьютерлік математиканың теориялық негіздері ретінде қарастыруға болады;

− дискретті математика модель мен әдістерде, әр түрлі ғылым саласында қолданылады, атап айтсақ химия, биология, генетика, физика, психология, экология т.б моделдер тұрғызумен талдаудың тиімді құралы мен тілі болып табылады;

− дискретті математика тілі аса қолайлы және іс жүзінде бүкіл қазіргі математиканың мета тілі болып қалыптасты.

Ғылым ретінде математика әрине бұрыннан дискретті және континуальды математикаға бөлінеді. Континуальды математикаға не жатады? Шектермен үздіксіздік теория идеялары, айқын немесе астыртын түрге енетінінің барлығы жатады. Қалғаны – дискретті математика (яғни, арифметика, алгебра, көбейткіштер теориясы, жалпы бейнелеулер теориясы, математикалық логика, комбинаторлық талдау, алгоритмдер теориясы және т.б ).

Дәріс № 1. Кіріспе. Жиындар мен жиындарға орындалатын амалдар. Жиын құру әдістері. Эйлер диаграммасы. Жиындардың декарттық көбейтіндісі. Сәйкестік және оның қасиеттері. Функциялар мен бейнелеулер. Жиындардың қуаты.

Дәріс түрі: Кіріспе дәріс Дәрістің мақсаты:

1. Жиындар теориясының негізгі түсініктерін енгізу.

2. Жиындардың берілу тәсілдерін көрсету.

3. Жиындарға қолданылатын амалдарды және олардың негізгі қасиеттерін қарастыру.

4. Декартты көбейтінді түсінігін енгізу.

5. Сәйкестіктер – жиын элементтерінің арасындағы өзара байланысты беру тәсілін енгізу.

6. Бейнелеулер, бейнелеудің мәндер жиыны түсініктерін енгізу.

Дәріс жоспары:

• Жиындар теориясының элементтері. Жиындардың берілу тәсілдері.

• Ішкі жиындарға қолданылатын амалдар.

• Жиындар алгебрасы. Жиындардың декарттық көбейтіндісі.

• Жиынның бүркеуі мен бөлекшесі.

• Сәйкестіктер және олардың қасиеттері

• Функциялар мен бейнелеулер.

Негізгі ұғымдардың сөздігі: Жиын, ішкі жиын, ақырлы, ақырсыз жиындар, кортеж, қуатты жиын, булеан, универсум, Эйлер-Венн диаграммасы, Жиындардың бірігуі, қиылысуы, айырымы, симметриялық айырымы, толықтауышы, декарттық көбейтіндісі, Жиынның бүркеуі, бөлекшесі, сәйкестік, функциялар, бейнелеулер, сюръективті, инъективті,биективті.

Студенттерде қалыптасу керек білім мен дағды: Жиын ұғымымен танысу.

Жиындар теориясының элементтері.

Жиын ұғымы математиканың негізгі, алғашқы ұғымдарының бірі, сондықтан ол басқа ұғымдар арқылы анықталмайды.

Жиындар теориясының негізін қалаған неміс математигі Георг Кантор (1845-1918) жиын түсінігін келесі түрде анықтаған: «Бірнеше заттардың, объектілердің қандай да бір белгісіне қарай біртұтас болып бірігуі жиынды анықтайды».

Сан ұғымынан бұрын шыққан жиын ұғымын қандай да бір нәрселердің жинағы ретінде түсінеміз, ол жинаққа кіретін нәрселерді жеке-жеке қабылдауға және оларды бір-бірінен де, бұл жинаққа жатпайтын басқа нәрселерден де ажыратуға болады деп білеміз. Яғни, жиын туралы сөз еткенде, қандай да бір белгілері бойынша бір тұтас етіп біріктірілген нәрселерді қарастырамыз.

Мысалы,”Бірінші курста оқитын студенттер жиыны”, “Дұрыс көпбұрыштар жиыны”,

“Бөлмедегі орындықтар жиыны”, “Елуге дейінгі натурал сандар жиыны”, т.б.

Жиынды құраушы объектілер оның элементтері деп аталады. Жиынды латын алфавитінің үлкен әріптерімен А,В,С,..., ал оның элементтерін сол алфавиттің кіші әріптерімен а,в,с,... деп белгілейді. Берілген А жиыны а,в,с элементтерінен тұратын болса, оны былай жазады: А={а,в,с}.

Мысалы, А – бір таңбалы жұп сандар жиыны десек, онда А={2,4,6,8}.

Егер а элементі А жиынының элементі болса, онда а элементі А жиынына тиісті делінеді де, былай белгіленеді: аА.

Егер а элементі А жиынының элементі болмаса, онда а элементі А жиынына тиісті емес делінеді де, былай жазылады: аА.

Бір де бір элементі болмайтын жиынды құр (бос) жиын деп атайды. Оны Ø түрінде белгілейді.

-кез келген;

- табылады;

:(/)- мынадай, қасиетін сипаттау үшін;

- бұдан шығатын салдар;

- тепе-теңдік кванторы, тек сол жағдайда;

- қатаң енгізу кванторы.

Егер жиынның элементтерін санап, берілген жиында қанша элемент бар

екендігін анықтауға болатын болса, онда ол жиынды ақырлы жиын деп атаймыз. Мысалы, 25 санының бөлгіштерінің жиынын В деп белгілесек, онда

В={1,5,25} шектеулі жиын болады, себебі оның элементтерінің саны үшеу.

Математикада шектеулі болмайтын жиындар да кездеседі. Ондай жиындарды ақырсыз жиындар дейді, ақырсыз жиындардың элементтерін санап шығу мүмкін емес.

Мысалы, натурал сандар жиыны, жай сандар жиыны, нольден үлкен бірден кіші нақты сандар жиыны.

Жиындардың берілу тәсілдері.

1. Мүшелерін тізіп жазу арқылы. Бұл тәсілмен тек қана ақырлы жиындарберіледі. Мысалы, процессор a, монитор b, клавиатура c және принтерден d тұратын компьютер А жиынын былай өрнектеуге болады: A = {a, b, c, d}, ақырлы жиын

A   a

, a

,... a



Ақырсыз жиындарды тізіммен беру мүмкін емес. Мысалы, барлық натурал сандардың немесе барлық бүтін сандардың жиынын тізім арқылы беру, яғни ол жиындардың барлық элементтерінің тізімін жасау мүмкін емес. Мұндай жағдайда жиынды оның кейбір сипаттамалық қасиетін көрсету арқылы береді.

2. Сипаттау арқылы. Мысалы жиынның кез келген х мүшесі р(х) қасиетіне ие болсын, онда осы элементтерден тұратын С жиыны былай беріледі:C



 



Осы сияқты анықталған жиындар





B m

Z m m n

Q n    







  

 / , , 0 , : 2 1,

Анықтама. А және В жиындары берілсін. Егер А жиынының кез келген х элементі В жиынындада да жатса, онда А жиыны В жиынының ішкі жиыны деп аталады.AB және

A

B деп белгіленеді. Кванторлар тілінде



 



Анықтама. Егер В жиынының А ішкі жиыны В жиынынан және -ден өзгеше болса, онда ол меншікті ішкі жиыны деп аталады. Кванторлар тілінде, ABABA B

 кез келген жиынның ішкі жиыны: A Қасиеттері:

а) A A

ә) A B,B A AB; б) A B,BC AC.

Анықтама. В жиынының В және  ішкі жиындары оның меншіксіз ішкі жиындары деп аталады. Егер жиын ең болмағанда екі элементтен тұрса, онда оның меншікті ішкі жиындары болады.

Мысалы: А={а,в} жиынының ішкі жиындары: {а},{в}, {},{а,в}. Бұл ішкі жиындардың ішінде {а},{в} – меншікті, ал {},{а,в} – меншіксіз болып табылады.

Анықтама. Егер А жиынының әрбір элементі В жиынының да элементі болса және керісінше, В жиынының әрбір элементі А жиынының да элементі болса, онда А мен В жиындары тең деп аталады да, былай жазылады: А=В. Мысалы, А= {1,3,5,7,9} және В=

{9,3,1,5,7} жиындары тең.

Анықтама. Элементтері өзара бірмәнді сәйкестікте болатын жиындарды тең қуатты жиындар деп атайды.

Егер А= {1,2,3,4,5} жиыны берілсе, онда осы жиынның элементтерін әртүрлі тәсілдермен реттеуге болады. Атап айтқанда, әртүрлі бір таңбалы, екі таңбалы, үш таңбалы, төрт таңбалы, бес таңбалы, алты таңбалы т.с.с. сандарды алуға болады. Реттелген осындай жиын элементтерінің әртүрлі жиынтығын кортеж деп атайды, ал кортежді құрап тұрған элементтерді оның компоненттері дейді. Кортеждің компоненттерінің санын оның ұзындығы дейді.Кортежді былай белгілейді: (а1,а2,а3,...,аn). Мысалы, А= {1,2,3} жиынының элементтерінен, ұзындығы 2-ге тең болатын кортеждерді жазайық. Олар: (1;1), (1;2), (1;3), (2;1), (2;2), (2;3), (3;1), (3;2), (3;3). Сондай-ақ, ұзындықтары әртүрлі болатын кортеждерді де жазып көрсетуге болады. Ұзындығы 2-ге тең болатын кортеждерді кейде парлар деп те атайды. Кортеждің компоненттерінің өзі де кортеж болып келуі мүмкін. Екі (а1,а2,а3,...,аn) және (в1,в2,в3,...,вm) кортеждерінің сәйкес компоненттері тең, яғни а1=в1, а2=в2, а3=в3,..., аn=вm және ұзындықтары n=m бірдей болса, онда олар тең болады.

Анықтама. Ақырлы жиындардағы элементтердің саны жиынның қуаты деп аталады және | | белгілерімен қоршалып жазылады. Мысалы, М – ақырлы жиын болса, оның қуаты | M |.

Анықтама. Егер А және В жиындары тең болса, олар тең қуатты жиындар деп аталады. Мысалдар:

1. А = {1, 2, 3}, B = {3, 4, 5}, A  B.

2. A = {1 ,2 ,3, 4}; B = {4, 3, 1, 2}; A = B, себебі A  B, B  A;

3. A = {1, 2, 3}; B = {2, 4, 6}; C = {1, 2, 3, 4, 5}, A  C; B  A.

Анықтама. А жиынының барлық ішкі жиындарының жиынтығы булеан немесе дәрежелі жиын деп аталады және Р(А) деп белгілінеді (2^А деп те белгіленеді). Сонымен, 2^А = P(A) ⇆ {B | B  A} немесе 2^А. Мысалдар: Егер А = {1, 2 ,3} болса, P(A) = {, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}}.

Ішкі жиындарға қолданылатын амалдар.

Анықтама. Қарастыруға болатын барлық мүмкін элементтерден тұратын жиын универсал немесе универсум деп аталады және U деп белгіленеді, яғни элементтер осы жиыннан алынып отыратын болсын.

Эйлер – Венн диаграммасы. Көрнекілік үшін жиындарды дөңгелек сызықтармен белгілейді. Сызықтың ішінде тек жиын элементтері ғана орналасады. Ол дөңгелектерді Эйлер дөңгелектері немесе диаграммалары деп атайды. Эйлерден кейін логикалық есептерді дөңгелектер арқылы шешу әдісін

дамытқан ағылшын математигі Джон Венн болды. Сондықтан да, мұндай схемалар кейде

«Эйлер – Венн диаграммасы» деп аталады.

Тік төртбұрыштың нүктесі U жиынынан алынған деп есептейік. Мысалыға:









 

 B C

А жиындарын алайық.

1) Ең болмағанда А жиынына немесе В жиынына тиісті элементтер жиынын А және В жиындарының бірігуі (қосындысы) АВдеп атаймыз.





В

А  :  







В

А АС





2) А жиынына да В жиынына да тиісті элементтер жиынын А және В элементтер жиынының қиылысуы (көбейтіндісі) деп аталады.





В

А  :  

 



В

А ВС

 

3) А жиынына тиісті, бірақ В жиынына тиісті емес элементтер жиынын А және В жиындарының айырымы (А\В) деп атайды.





В

А\  :  

 

\ В 

А В\С

 

4) А және В жиындарының симметриялық айырымы (сақиналы қосынды) (АВ) деп келесі жиынды айтамыз





)

\ ( )

\

(А В В А х x Aжанех В немесе х Вжанех А В

А       









) 5 ( ) 4 , 2

(      



В А С

А

5) U\А жиыны А жиынының толықтауышы деп аталып, А^ деп белгіленеді A

А U \



Универсум U 











А болады.

Жиындар алгебрасы.

Жиындарға амалдар қолданып, жаңа жиындар алуға болады. Осы амалдардың негізгі қасиеттері мен олардың арасындағы байланыс жиындар алгебрасы деп аталады.

1.1-кесте. Қасиеттері:

№ ^{ }

1 (идемпотенттік) АА=A АА=A

2 Ауыстырымдылық (коммутативтік)

AB=BA AB=BA

3 Терімділік (ассоциативтік )

A(BC)=(AB) C A(BC)=(AB)C 4 Үлестірімділік (дистрибутивтік)

A(BC)=(AB)(AC) A(BC)=(AB)(AC)

5 Жұтылу(сіңіру) A(AB)=A A(AB)=A

6 Нөлдік қасиеті A=A A=

7 Бірлік қасиеті AU=U AU=A

8 Қосалқы принципі (де Морган заңы) B

A =A B, 



Ak 1



k

Ak

1

B

A =A B, 



Ak 1



k

Ak

1

9 Екі рет теріске шығару A=A

10 Толықтыру қасиеті AA=U AA

Жиындардың декарттық (тура) көбейтіндісі.

Кортеж ұғымына сүйеніп, екі жиынның декарттық көбейтіндісін анықтауға болады.

Мысал. А={а, в, с}, В={3, 4} шектеулі жиындары берілсін. Осы жиындардың элементтерінен ұзындығы 2-ге тең кортеждердің жиынын

құрайық. Олар: {(а;3),(а; 4),(в;3), (в;4), (с;3),(с;4)}.

Анықтама. А және В жиындарының декарттық (тура) көбейтіндісі деп біріншікомпоненті А жиынынан, екінші компоненті В жиынынан алынған барлық реттелген жұптардың жиынын айтады. А және В жиындарының декарттық көбейтіндісін А  В деп белгілейміз.

Анықтама бойынша: А  В = {(х ,у) | хА және уВ}.

A

A

A

,

,...,

An

A

A₁ ₂ ... = 

 т m

Ai 1

=

{( x

, x

,..., x

) x

 A

, x

 A

,..., x

 A

}

Егер A1=A2=…=An=A болса, онда A1хA2х,…,хAn жиыны А жиынының n-ші декарттық дәрежесі деп аталады және Аⁿ болып белгіленеді. Анықтама бойынша A⁰⇌{}

Мысалдар:

1.A={1,2}, B={3,4} берілсін.

AхB={ (1,3),(1,4),(2,3),(2,4) };

BхA={ (3,1),(3,2),(4,1),(4,2) };

AхA={ (1,1),(1,2),(2,1),(2,2) }; Бұл мысалдардан AхBBхA.

2. (Шахмат тақтасы).

A={a,b,c,d,e,f,g,h}; B={1,2,3,4,5,6,7,8} жиындары берілсін. Олай болса әр (х,у) жұбына x,yAхB шахмат тақтасының торлар жиыны сәйкес келеді.

3. [0,1]² жиыны { (a,b) | 0  a 1, 0  b  1 } ;Бұл жиынға жазықтықтың 1-ден аспайтын теріс емес координаттары бар нүктелер жиыны сәйкес келеді.

4. A₁ [0,1], A₂ [2,3] екі жиынын қарастырайық. Егер жазықтықтағы декарттық координаталар жүйесін қарастырсақ, онда A₁A₂ ұзындығы бірге тең квадрат ретінде қарастыруға болады.

5. A={a,b,c}; B={1,2}; AхB={(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)};

BхA={(1,a),(2,a),(1,b),(2,b),(1,c),(2,c)}; AхB  BхA

6. А={1,2,3}; АхА={(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1 ), (3,2), (3,3) };

7.X {x₁,x₂,...,x_m}; Y {y₁,y₂,...,y_n}; X,Y - жиындарының декарттық көбей-тіндісін табайық. Декарттық көбейтіндісінің элементтері әр түрлі жиын элементтерінен алынған жұптардан тұратындығы белгілі.

Оларды кестеге орналастырайық: Бұл кестеде m жол, n бағаннан тұратын элементтер жұбын көреміз. (x,y) - саны х-элементтерінің жиыны мен ү элементтерінің жиындарының көбейтіндісіне тең.

(x,y)(x)(y) (1)

Бұл жиындарды көбейту ережесі. Егер декарттық көбейткіштері n жиыннан тұрса, онда (1) төмендегідей жалпылауға болады:

) ( )...

( ) ( )

* ...

*

*

(x₁ x₂ x_n  x₁  x₂  x_n

   (2)

A х B х C; (A х B) х C; A х (B х C) жиындары да әр түрлі. A х B х C- (a,b,c); (A х B) х C- ((a,b),c ) aA, bB, cC;

A х (B х C)=(a, (b,c) ); Егер А,В жиындарының бірі бос болса, олардың декарттық көбейтіндісі де бос деп есептеледі. A х  =  х A =  х  = ;

Мысал, А={a1,a2,a3}, B={b1,b2,b3} ;

АхВ 

















3 3 2 3 1 3

3 2 2 2 1 2

3 1 2 1 1 1

b a b a b a

b a b a b a

b a b a b

a ;

1 – есеп. AB AB Де Морган заңын (қосалқы принципі) дәлелдеу керек.

Шешуі: І әдіс Эйлер-Венн диаграммасы арқылы. Ол үшін теңдіктің сол жағындағы жиынды кескін деп аламыз:

а)AB

Ал оң жақтағы жиынды бейнелеу үшін алдымен A жиынын  көлденең жолақпен, B жиынын тік жолақпен белгілеп аламыз. Сонда бізге керекті жиын екі жолақтың қиылысуында, яғни тормен кескінделген жиын болады;

ә) AB

B A

x 

Байқасақ, жоғарыдағы диаграммада штрихпен белгіленген жиын мен төмендегі тормен белгіленген бір жиынды береді, бұл екі жиынның теңдігін білдіреді.

ІІ әдіс қасиеттерге сүйеніп, өрнектерді түрлендіру арқылы.

Алдымен U V U V,V U қасиеті бойынша:

1) AB AB;

2) AB AB енгізулері орындалатынын көрсетейік.

1)xABxABxA және xBxA және xBxAB;

2) керісінше, xABxA және xBxA және xBxABxAB. Жиынның бүркеуі мен бөлекшесі.

Жиындарға қолданылатын операциялардың тағы бір түрі – жиынды ішкі жиындар жүйесіне бөліктеу операциясы болып табылады. А жиыны мен оның ішкі жиындар жүйесін A {A₁,A₂....,A_n}{A_i /i1,n} қарастырайық.

Анықтама 1. Егер 1) A_i  A [A_i  A,A_i ], 2)



i

Ai

A

1

 ; шарттары орындалса, онда A жиын жүйесін А жиынының бүркеуі деп атайды.

Анықтама 2. 1) A_i A [A_i A,A_i ,i1,n], 2)



i

Ai

A

1



3) A_i,A_j  A [A_i  A_j  A_i A_j ] немесе i, j1,n,i jA_i A_j  шарттары орындалса, онда A жиын жүйесі А жиынының бөлікшесі деп аталады.

Егер бүркеу анықтамасындағы екі шартқа 3) шартты қоссақ, онда бүркеу бөлікше бола алады. Басқаша айтқанда, егер әрбір xA элементі тек қана бір A_i ішкі жиынына тиісті болса, онда А жиынының бос еме ішкі жиындарының A жүйесі оның бөлікшесі бола алады.

1 – мысал. A{1,2,3} жиыны берілсін:

а) A₁ {{1,2},{2,3},{3,1}} - А жиынының бүркеуі;

ә) A₂ {{1},{2},{3}}- А жиынының бөлікшесі болады;

б) A₃ {{1},{2}}- қандай-да бір ішкі жиындардың жүйесі, ол бүркеуі де емес, бөлікшесі де емес, себебі {1}{2}{1,2,3}.

2 – мысал. N – натурал сандар жиынын қарастырайық. N₀ - жұп, N₁- тақ сандар жиыны болсын. Онда {N ,N₁}N бөлікшесі бола алады.

Сәйкестік және оның қасиеттері.

Анықтама. А, В жиындарының арасындағы сәйкестік деп бұл жиындардың тура (декарт) көбейтіндісінің G ішкі жиынын айтады.

G  AхB Егер (a,b)G болса,G сәйкестігінде b a-ға сәйкес деп айтады. G={a|(a,b)G, G сәйкестігінің анықталу облысы, ал G={b|(a,b)G} мәндер жиыны деп аталады.

Анықтама. Егер G=A болса толық анықталған сәйкестік, AA болса толық емес (жартылай) сәйкестік болады. (толық анықталмаған).

Анықтама. Егер G=B – сюръективті сәйкестік деп аталады. (В-ның әрбір элементінің А прообразы бар) Анықтама А жиынының әрбір aA элементіне B жиынының G сәйкестігіндегі а-ға сәйкес барлық bB элементтерінің жиыны a элементі- нің образы, ал әрбір bB элементіне А жиынының G сәйкестігіндегі в-ға сәйкес барлық aA элементтерінің жиыны b элементінің А жиынындағы прообразы деп аталады.

Анықтама. Барлық а С G элементтерінің образдарының жиыны С жиынының образы деп аталады. Барлық вDG элементтерінің прообраздарының жиыны D

жиынының прообразы деп аталады.

Анықтама. Егер анықталу облысынан (G) алынған кез-келген а элементінің мәндер жиынында (G) бір ғана образы bG болса, G – функционал (бір мәнді) сәйкестік деп аталады.

Анықтама. Егер G сәйкестігі толық анықталған,сюръективті, функционалды және  bG элемен тінің анықталу облысында бір ғана прообразы aG болса, онда G өзара бір мәнді сәйкестік болады.

Егер А мен В жиындарының арасында өзара бір мәнді сәйкестік болса, онда олардың қуаттары тең және олар тең қуатты жиындар |A|=|B| деп аталады.Бұл фактілер жиынды санамай-ақ,олардың тең қуаттылығын анықтауға

болатындығын көрсетеді. Қуаты белгілі немесе оңай санауға болатын басқа жиынмен өзара бір мәнділігін дәлелдеу арқылы жиын элементтерін санамай-ақ оның қуатын анықтауға болады. N натурал сандар жиыны мен тең қуатты жиындар саналымды жиын деп аталады.

R нақты сандар жиынымен тең қуатты сандар континуальды деп аталады.

1- мысал. Айталық , G (x-3)²+(y-2)²≤1 қатынасын қанағат тандыратын барлық (х,у) нақты санды сандар жиыны болсын. G={(x,y)|x,y үшін (x-3)²+(y-2)²≤1} сәйкестігінің графикалық кескіні центрі (3,2) нүктесінде болатын ,радиусы 1-ге тең дөңгелек. Бұл 3.2 суреттегідей G дөңгелегі R мен R арасындағы сәйкестік ( яғни ОХ өсі мен ОУ өстерінің арасындағы сәйкестік).

а) 2, 3, 4 сандарының образы мен прообраздарын табу керек.

Шешуі: 2G G сәйкестігіндегі образы жалғыз ғана 2G, 3-ң G сәйкестігіндегі образы [1,3] кесіндісіндегі барлық нақты сандар жиыны , 4-ң образы 2. G сәйкестігінің мәндер жиыны G алын ған (2G ) 2 санының G сәйкестігіндегі прообразы [2,4]G ; 3G G сәйкестігіндегі прообразы 3G. 4G – G сәйкестігінде прообраздары жоқ

б) 1) [2,3] G сандарының образы осы [2,4] кесіндідегі барлық образдарының бірігуі, яғни [1,3]G;

2) Осыған ұқсас [2,4] кесіндісінің G сәйкестігіндегі образы [1,3];

3) [2,3] кесіндісінің прообразы [2,4] ; [2,4]G прообразы [2,4];

Егер G сәйкестігі нақты сандар жиынында анықталған десек, яғни GRхR онда 1) G – толық анықталмаған себебі ,GR (GR)

2) Сюръективті емес себебі , GR (GR)

3) Функционалды (бір мәнді) емес, себебі [2,4]=G үшін (2 мен 4-тен басқа) образдар жалғыз емес.

4) Өзара бір мәнді болудың қажетті шарттары (1,2,3 шарттар) орындалмағандықтан сәйкестік өзара бір мәнді емес.

Егер сәйкестік G [2,4]х[1,3] болса G толық анықталған және сюръективті ,бірақ функционал ды және өзара бір мәнді емес.

2 мысал. Айталық G сәйкестігі x-2=y, x,y≥0 түзуінің бойындағы нүктелер жиыны G={(x,y)|, x-2=y, x,y≥0}; G={ элементтері x-2=1 қатынасын қанағаттандыратын нүктелер жиыны}. G – сәйкестігінің қандай қасиеттері бар?

Шешуі: Егер G нақты сандар жиынында берілген сәйкестік (GRхR ) болса,онда:

1) G толық анықталмаған сәйкестік, себебі

G =[2,∞)R;

2) Сюръективті емес, себебі анықталу облысы G =R+=[0,∞] нөлмен қоса алғанда барлық нақты сандар жиыны.

3) Функционалды, себебі  xG, G – анықталу облысынан алынған

әрбір х-ке бір ғана yG сәйкес (х-ң бір ғана образы бар).4) Өзара бір мәнді емес, себебі толық анықталмаған және сюръективті емес.

2. G сәйкестігі нөлмен қоса алғандағы R + жиынында яғни G  R+  R+ берілген болса, онда G сәйкестігінің төмендегідей қасиеттері болады:толық анықталмаған ,себебі G = [2,

) және G  R+;

• сюръективті, себебі анықталу облысы G = R+;

• функциональды;

• Өзара бір мәнді емес, себебі толық анықталмаған . 3. G сәйкестігі G  [2, ) х R+ болса :

• в толық анықталған;

• сюръективті;

• функциональды;

• Өзара бір мәнді ,себебі алдыңғы аталған қасиеттерге қоса, анықталу облысынан алынған кез –келген yG үшін бір ғана прообраз бар.

Функциялар мен бейнелеулер. Айталық, А, В жиындарында f  AхB сәйкестігі бар болсын.

Анықтама Егер f=A, f=B және _{(x,y )f, (x,y ) f}

2

1 болғандығынан y₁ y₂ болса, онда B

A

f   сәйкестігі функция деп аталады ол f : AB немесе А^f B болып жазылады.

Бұл анықтамадан функция дегеніміз функционал сәйкестік екендігін көреміз және f функциясының типі АВ деп оқылады . f функциясы анықталу облысының әрбір элементіне (х ) мәндер облысынан бір мәнді (у)сәйкестендіреді және у = f (х) болып белгіленеді. ) (х аргумент, у функцияның мәні) болып жазылады (у х-тың образы).Мысалдар: f={(1,2),(2,3),(3,2)} – функция; f={(1,2),(1,3),(2,3)} - функция емес;

{(x,x²-2x+3), xR} – функция ; бұл функция әдетте y=x²=2x+3 болып жазылады.

Анықтама Толық анықталған функция f : AB А-ны В-ға іштей бейнелеу деп аталады. f : A ^iштей B ( f=A ,  f B) толық анықталған функция

Анықтама Егер  f = B болса функция сюръективті функция деп аталады.

Анықтама Егер функция толық анықталған (f=A) және сюръективті (f=B) болса ,онда ол А-ны В-ға толық бейнелеу деп аталады: f : A^толык  B болып жазылады.

Анықтама .А



  

f және g функциялары тең болады, егер төмендегі шарттар орындалса:

• Олардың анықталу облыстары біреу -ол Ажиыны;

• Кез-келген а  A үшін f(a) = g (a).

Сәйкестік

Міндетті түрде болу керек қасиеті Функционалды Толық

анықталған Сюръективті Функция

А-ны В-ға іштей бейнелеу

А-ы В-ға толық бейнелеу

+ + +

+

+ +

f: А1А2...Аn  В типті функция п –орынды функция деп аталады.Бұл жағдайда функцияның п аргументі бар деп түсіну келісілген.:f(а1,..., аn)=b, мұндағы а1А1,...,аnАn, bВ. Айталық, GAхB сәйкестігі берілсін. Тек (а,b)G болса ғана (b,a)Н болатын HBхA сәйкестігі, G-ң кері сәйкестігі деп аталады және G-1 болып белгіленеді.

Анықтама Егер f:AB сәйкестігіне кері сәйкестік функционалды болса (яғни әрбір bf үшін бір ғана af болса), онда ол f функциясына кері функция деп аталады, f ^-1 болып белгіленеді.

Кері сәйкестікте образ бен прообраздың орындары ауысып келетіндіктен f функциясына кері функция болу үшін f : AB f функциясының мәндер жиынының әрбір b f элементінің жалғыз ғана образы болу керек. Бұдан f : AB функциясы өзінің анықталу облысы мен мәндер облысының өзара бір мәнді сәйкестігі болса ғана оған кері функция болатындығы көрінеді.

Егер h(x) = g(f(x)), мұндағы, хА орындалса h:АС функциясы f және g функцияларының композициясы деп аталады және f(g) белгіленеді.

Көбіне h функциясы f ті g –ң орнына қойғаннан алынды деп айтады.Көп орынды f: А^т

 В, g: Вⁿ С функциясы үшін f-ті g –ға қоюдың әртүрлі варианттары бар. Нәтижесінде әртүрлі типтегі функциялар алынады. Мысалы, т = 3 және п = 4 үшін h = g (x1, f(у1,у2, у3), х3, х4) функциясында 6 аргумент бар ал оның типі В  А³  В2  С. Аргументтерін басқаша атап f1,...,fn функцияларын бір-біріне қойғаннан алынған функция f1,...,fn функ- цияларының суперпозициясы деп аталады. Бұл суперпозицияны және функ-ционалдық белгі мен аргументтердің символдарын сипаттайтын өрнек формула деп аталады.

Функциялардың берілу тәсілдері:

• График түрінде;

• Кесте;

• Функцияны басқа функциялардың суперпозициясы түрінде сипаттайтын формула түрінде;

Анықтама. Егер f ^-1 сәйкестігі толық емес функция болса, яғни  x1, x2f үшін, x1x2

болғандығынан f(x1)f(x2) болса, f функция инъективті (Инъекция) функция деп аталады..Егер f – инъекция болса f: болып белгіленеді.

Анықтама. Егер G = B болса f:AB функциясы сюръективті (сюръекция) функция деп аталады f:

А 

    В

Анықтама. Егер f инъективті және сюръективті болса, ол биективті деп аталады:

f:AB

Анықтама. Егер f А-ы В-ң әр түрлі мәндеріне бейнелесе, онда f функциясы өзара бір мәнді сәйкестік немесе биективті функция (биекция) деп аталады. Сонымен, егер функция сюръективті және инъективті болса, функция биекция болады. Егер f А мен В арасындағы биекция болса, f : AB болып жазылады. F: AA биекциясы А жиынының (подстановка) алмастыруы деп аталады.

Суретте графиктік түрде функциялар берілген

} 4 , 3 , 2 , 1 { ],

1 , 0 [ ] 1 , 0 [

:  i

f_i

f1 – сюръективті, инъективті емес

f2 – инъективті, сюръективті емес f3 – инъективті, сюръективті – биекция f4 - инъективті де емес, сюръективті де емес

2- мысал: Үш функцияны қарастырайық f_i:RR,i1,2,3: 1) f₁(x)e^x инъективті, сюръективті емес

2) f₂(x)xsinx сюръективті, инъективті емес 3) f₃(x)2x1биективті;

Бақылау сұрақтары:

1. Жиын дегеніміз не?

2. Қандай жиынды ішкі жиын деп атайды?

3. Жиындармен орындалатын негізгі амалдар қандай?Жиындарды өрнектеудің қандай әдістері бар?

4. Жиындардың декарттық көбейтіндісі? Сәйкестік,бейнелеу,функциональды бейнелеу дегеніміз не?

5. Қандай бейнелеулер инъективті, сюръективті, биективті деп аталады?

Пайдаланылған әдебиеттер:

1. Байсалов М.Ж. Дискретті математика. Оқу құралы. Алматы, 2007.

2. Жетпісов Қ. Математикалық логика және дискретті математика, Қарағанды, 2008.

3. Мутанов Г.М.,Акбердин Р.А. Теория графов. – Алматы, изд-во «Рауан», 2008.

4. Нефедова В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 2011.

5. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Изд-во МГТУ им.Н.Э.Баумана, 2010.

Дәріс № 2. Қатынастар. Бинарлы қатынастарды беру тәсілдері. Бинарлы қатынастар матрицаларының негізгі қасиеттері. Эквивалентті қатынастар.

Дәріс түрі: Ақпараттық Дәріс мақсаты:

1. Бинарлы қатынастар түсінігін енгізу және бинарлы қатынастардың қасиеттерін қарастыру.

2. Эквивалентті және реттік қатынастар түсінігін енгізу.

Дәріс жоспары:

• Бинарлы қатынастар. Бинарлы қатынастардың негізгі қасиеттері.

• Эквивалентті қатынас және кластарға бөлшектеу.

• Реттік қатынас.

Негізгі ұғымдардың сөздігі: Унарлы, бинарлы, эквивалентті, реттік, рефлексивті, антирефлексивті, симметриялы, антисимметриялы, транзитивті.

Студенттерде қалыптасу керек білім мен дағды: Жиындар арасындағы қатынас түсінігімен танысу.

Бинарлы қатынастар.

Жалпы математикада екі объектінің арасындағы қатынастар қарастырылады.

1) Сандар арасында: тең, артық, үлкен, кіші, бөлінеді, еселі;

2) Түзулер арасында: параллель, перпендикуляр, қиылысады, айқас;

3) Геометриялық фигуралар арсында: конгруэнтті, ұқсас т. с. с.

Сондай-ақ жиындарды салыстыра отырып, олар қиылысады немесе тең, біреуі екіншісіне тиісті, т. с. с. , яғни жиындар арасында да қатыстар орнатуға болады.

Мысал. А={6, 7, 8, 9} сандар жиынын қарастырайық. Бұл сандардың

арасында «артық» қатысы бар, 7>6, 8>7, 9>8, 9>7, 9>6, 8>6.

Осы сандардың арасындағы «1-ге артық» деген қатысты қарастырсақ,

«7 саны 6-дан 1-ге артық», «8 саны 7-ден 1-ге артық», «9 саны 8-ден 1-ге артық» болады. Бұл сандардың арасында әлі де басқа қатыстар болатынын

қарастыруға болады. Сонда, әрбір қатысты қарастырғанда элементтері берілген

А жиынынан алынған реттелген жұптардың жиынын құрдық. «Артық» қатысы үшін 7,6,

8,7, 9,8, 9,7, 9,6, 8,6жиыны, ал «1-ге артық» қатысы үшін 7,6, 8,7, 9,8жиыны болады. Сонымен, қарастырылған әрбір қатыс берілген жиынның элементтерінен құрылған жұптардың жиынымен анықталып тұр. Осы жұптарды А жиынының элементтерінің арасындағы қатынас деп атайды.

Анықтама. А жиынының элементтерінің арасындағы немесе А жиынындағы қатынас деп А  В декарттық көбейтіндісінің кез келген ішкі жиынын айтады.

Қатынас латынның үлкен әріптерімен белгіленеді: P, Q, R, S т. с. с.

Егер А жиынының элементтерінің арасындағы қатынас R болса, онда R  А  В болады.

Қатынастардың ішінен унарлы, бинарлы қатынастар көбірек белгілі. Унарлы (бір орынды) қатынастар бір жиын элементтерінің белгілі бір R қасиетінің болуын бейнелейді.М жиынының R қасиетімен (белгісімен) ерекшеленетін элементтерінің жиыны М-ң бір ішкі жиынын құрайды.(Мысалы, қобдишадағы шарлардың бір бөлігінің ақ болуы) Оларды унарлы қатынас деп атайды, R мен белгіленеді, яғни aR, RM.

Бинарлы қатынастар М жиынының бір жұп элементтерінің қандай да бір өзара қарым- қатынасын анықтауға қолданылады. Мысалы, М адамдар жиыны десек 2 адамның бір қалада тұруы, бір ұйымда қызмет істеуі, біреуінің екіншісінен жас болуы, әке мен бала болуы т. б.

Анықтама Екі орынды немесе бинарлы Р қатынасы деп А, В жиындарының декарт (тура) көбейтіндісінің (a,b) жұптарынан тұратын ішкі жиынын айтады және (a,b)P, PAB болып белгіле неді. А–Р қатынасының анықталу облысы, ал В мәндер облысы деп аталады.Айталық, PAxB қатынасы мына суреттегідей кескінделсін:

Бинарлы қатынас бір жиынның ішінде болса, мысалы М-жиынында болса Р қатынасы (a,b)P, PMхM=M² немесе (a,b)P, аРb болып белгіленеді. Жалпы жағдайда n орынды R қатынасы деп n жиынның тура (декарт) көбейтіндісінің R ішкі жиынын айтады:

R  M1 x M2 x…x Mn

Егер (a1,a2,…,an)R, ал (a1M1,…,anMn) онда a1,a2,…,an элементтері R қатынасында делінеді. Егер n орынды R қатынасы М жиынында болса, яғни M1=M2=…=Mn, онда RM ⁿ.

Бинарлық қатынастар жиын болғандықтан, жиынның берілу тәсілдерінің бәрімен беріле алады. Ақырлы жиындарда берілген қатынастар әдетте төмендегідей әдістермен беріледі:

1. Бинарлы қатынас орындалатын жұптардың тізімі арқылы. Мысалы, A={2,3,4,5,6,7,8} жиыны берілсін. P={(x,y) | x,yA, y x-ке бөлінеді және x≤3} бинарлы қатынасын P={ (2,2), (2,4), (2,6) ,(2,8 ) ,(3,3) ,(3,6) } түрінде жазуға

болады.

2. Графиктік түрде: Графиктік кескіндеудің бірнеше түрлері бар:

2.1. Координат өсьтеріне қатынастың элементтерін белгі леу арқылы. Алдыңғы мысалды графикалық түрде суреттегідей кескіндеуге болады.

2.2. А мен В жиындарының элементтерінің арасындағы Р қатынасын стрелкалар арқылы көрсетуге болады.

Мысалы,A={a,b,c}; B={1,2,3} жиындары берілсін. Олардың элементтерінің арасындағы

P1={(a,2),(b,1),(c,2)} қатынасын төмендегі 6-суретпен кескіндеуге болады.

2.3. Граф арқылы да кескіндеуге болады. Мысалы, P2={(a,b),(b,b),(c,a)} қатынасының граф түріндегі бейнесі 6-суреттегідей болады.

Бинарлы қатынастар PM1хM2 (PM², M1=M2=M) жиын болғандықтан оларға жиынға қолданылатын барлық амалдар орындалады. Олар:

1. Бірігу Р1Р2; Р1Р2={(a,b) | (a,b)  P1 немесе (a,b)  P2} 2. Қиылысу P1P2; P1P2={(a,b) | (a,b)  P1 және (a,b)  P2} 3. Айырым P1\P2; P1\P2={(a,b) | (a,b)  P1 және (a,b)  P2} 4. Толықтауыш P; P=U\P, мұндағы U=M1M2 (U=M²) 5. Кері қатынас P^-1; P^-1 = {(a, b) | (b, a)  P}.

P^-1⇌{(y,x) | (x,y)P} жиыны Р қатынасына кері қатынас деп аталады. Мысалы, Р-жас болу болса, P^-1 үлкен болу, Р-баласы болу болса, P^-1 әкесі

болу. P (x)={y | (x,y)P қандай да бір х үшін} Х жиынының Р -ға қатысты образы (бейнесі) деп, ал P^-1(x) – Х жиынының Р- ға қатысты прообразы деп аталады. Мысалы, A={2,3,4,5,6,7,8}

жиыны берілсін.

P={(x,y) | x,yA,y x-ке бөлінеді және x≤3} бинарлы

қатынасына кері қатынас P^-1={(2,2), (4,2),(6,2), (8,2),(3,3),(6,3)}; X-ң Р-ға қатысты образы P(x)={3,6}; X-ң Р-ға қатысты прообразы немесе P^-1 ( x )= {3}.6 Бинарлы қатынастың көбейтіндісі немесе Р1 мен Р2 композициясы Р1Р2.

Айталық А,В,С жиындары және Р1 ,Р2 қатынастары берілсін. Р1  АхВ және Р2  ВхС бинарлы қатынастарының көбейтіндісі немесе Р1 мен Р2 композициясы бар болады яғни (a,b)  Р1○Р2 егер (a,z)P1 және (z,b)P2 болатындай zB элемент табылса; Р1○Р2={(a,b) | aA, bC және (a,z)P1 .

.Дербес жағдайда, егер Р қатынасы М жиынында анықталған болса PM², онда Р○Р={(a,b) | (a,c),(c,b)P}

Мысалы Р-баласы болу болса, онда Р○Р-немересі болу.

Бинарлық қатынастардың негізгі қасиеттері.

1. А жиынында берілген бинарлы қатынас болсын: РА².Кез-келген хА үшін х Р х қатынасы бар болса, Р қатынасы рефлексивті деп аталады. (бір жиын ішіндегі жұптар қатынасы мы салы бір қалада тұру - рефлексивті).

2. Егер х Р х қатынасы А жиынның бір де бір элементі үшін орындалмаса Р қатынасы антирефлексивті (баласы болу қатынасы - антирефлексивті). Антирефлексивті матрицаның бас диагоналы тек нөлдерден тұрады.

3. Егер кез-келген х,уА үшін (х,у)Р(у,х)Р болса, яғни Р^-1 =P немесе[P]^T=[P]

болса, Р қатынасы симметриялы деп аталады. Егер x A y болудан у А х болса (бір фирмада жұмыс жасайды), онда А симметриялы.

4. Егер (х,у )Р және (у,х)Р болғандығынан х=y болса, яғни PP^-1  IdA, онда Р қатынасы антисимметриялы деп аталады,яғни х Р у және у Р х қатынастары әртүрлі х пен у- тың ешқан дай жұбында бір уақытта орындалмаса (баласы болу, бастық болу - антисимметриялы), онда бұл қатынас антисимметриялы.

5. Егер (x,y)P және (y,z)P болғандығынан (x,z)P болса, (яғни РРР) онда Р – транзитивті қатынас деп аталады,яғни х Р у және у Р z болудан x P z болса (жасырақ болу, інісі болу) Р-транзитивті болады.

Ескерту: 1. Антисимметрия мен симметрия емес ұғымдары бірдей емес. Мысалы A={1,2,3} жиынындағы Р={(1,2),(2,3)(3,2)} қатынасы симметриялы емес ((1,2)Р, ал (2,1)Р) антисимметриялы да емес, себебі (2,3)Р, (3,2)Р бірақ 23

2. IdA – қатынасы бір уақытта симметриялы да, антисимметриялы да болады.

Бинарлы қатынастың матрица арқылы берілуі.A={a1,a2,…,an} және B={b1,…,bn} ақырлы жиындары және PAхB бинарлы қатынас берілсен. Р бинарлы қатынастың [P]=(Pij) mхn мөлшерлі матрицасын төмендегі ережемен анықтаймыз:

Pi j =









болса жо аатына бинарлы егер P а b егер

болса бар аатына бинарлы еге