Математика 4 сынып

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

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



А.С.Муратов











ДИСКРЕТТІ МАТЕМАТИКА

Оқу-әдістемелік құрал





























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

2
ӘОЖ 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

3
Кіріспе

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

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

Дәріс түрі: Кіріспе дәріс
Дәрістің мақсаты:
1. Жиындар теориясының негізгі түсініктерін енгізу.
2. Жиындардың берілу тәсілдерін көрсету.
3. Жиындарға қолданылатын амалдарды және олардың негізгі қасиеттерін қарастыру.
4. Декартты көбейтінді түсінігін енгізу.
5. Сәйкестіктер – жиын элементтерінің арасындағы өзара байланысты беру тәсілін
енгізу.
6. Бейнелеулер, бейнелеудің мәндер жиыны түсініктерін енгізу.
Дәріс жоспары:
• Жиындар теориясының элементтері. Жиындардың берілу тәсілдері.
• Ішкі жиындарға қолданылатын амалдар.
• Жиындар алгебрасы. Жиындардың декарттық көбейтіндісі.
• Жиынның бүркеуі мен бөлекшесі.
• Сәйкестіктер және олардың қасиеттері
• Функциялар мен бейнелеулер.
Негізгі ұғымдардың сөздігі: Жиын, ішкі жиын, ақырлы, ақырсыз жиындар, кортеж, қуатты
жиын, булеан, универсум, Эйлер-Венн диаграммасы, Жиындардың бірігуі, қиылысуы,
айырымы, симметриялық айырымы, толықтауышы, декарттық көбейтіндісі, Жиынның
бүркеуі, бөлекшесі, сәйкестік, функциялар, бейнелеулер, сюръективті, инъективті,биективті.
Студенттерде қалыптасу керек білім мен дағды: Жиын ұғымымен танысу.

Жиындар теориясының элементтері.
Жиын ұғымы математиканың негізгі, алғашқы ұғымдарының бірі, сондықтан ол басқа
ұғымдар арқылы анықталмайды.
Жиындар теориясының негізін қалаған неміс математигі Георг Кантор (1845-1918)
жиын түсінігін келесі түрде анықтаған: «Бірнеше заттардың, объектілердің қандай да бір
белгісіне қарай біртұтас болып бірігуі жиынды анықтайды».
Сан ұғымынан бұрын шыққан жиын ұғымын қандай да бір нәрселердің
жинағы ретінде түсінеміз, ол жинаққа кіретін нәрселерді жеке-жеке қабылдауға
және оларды бір-бірінен де, бұл жинаққа жатпайтын басқа нәрселерден де
ажыратуға болады деп білеміз. Яғни, жиын туралы сөз еткенде, қандай да бір
белгілері бойынша бір тұтас етіп біріктірілген нәрселерді қарастырамыз.
Мысалы,”Бірінші курста оқитын студенттер жиыны”, “Дұрыс көпбұрыштар жиыны”,
“Бөлмедегі орындықтар жиыны”, “Елуге дейінгі натурал сандар жиыны”, т.б.
Жиынды құраушы объектілер оның элементтері деп аталады. Жиынды латын
алфавитінің үлкен әріптерімен А,В,С,..., ал оның элементтерін сол алфавиттің кіші
әріптерімен а,в,с,... деп белгілейді. Берілген А жиыны а,в,с элементтерінен тұратын болса,
оны былай жазады: А={а,в,с}.
Мысалы, А – бір таңбалы жұп сандар жиыны десек, онда А={2,4,6,8}.
Егер а элементі А жиынының элементі болса, онда а элементі А жиынына тиісті делінеді де,
былай белгіленеді: а А.
Егер а элементі А жиынының элементі болмаса, онда а элементі А жиынына тиісті емес
делінеді де, былай жазылады: аА.
Бір де бір элементі болмайтын жиынды құр (бос) жиын деп атайды. Оны Ø түрінде
белгілейді.
Жиі қолданылатын кванторлар:

5
 -кез келген;
 - табылады;
:(/)- мынадай, қасиетін сипаттау үшін;
 - бұдан шығатын салдар;
 - тепе-теңдік кванторы, тек сол жағдайда; 
- қатаң енгізу кванторы.
Егер жиынның элементтерін санап, берілген жиында қанша элемент бар
екендігін анықтауға болатын болса, онда ол жиынды ақырлы жиын деп атаймыз. Мысалы,
25 санының бөлгіштерінің жиынын В деп белгілесек, онда
В={1,5,25} шектеулі жиын болады, себебі оның элементтерінің саны үшеу.
Математикада шектеулі болмайтын жиындар да кездеседі. Ондай жиындарды
ақырсыз жиындар дейді, ақырсыз жиындардың элементтерін санап шығу мүмкін емес.
Мысалы, натурал сандар жиыны, жай сандар жиыны, нольден үлкен бірден кіші нақты
сандар жиыны.

Жиындардың берілу тәсілдері.
1. Мүшелерін тізіп жазу арқылы. Бұл тәсілмен тек қана ақырлы жиындарберіледі. Мысалы,
процессор a, монитор b, клавиатура c және принтерден d тұратын компьютер А жиынын
былай өрнектеуге болады: A = {a, b, c, d}, ақырлы жиын  
naaaA ,...,
21 .
Ақырсыз жиындарды тізіммен беру мүмкін емес. Мысалы, барлық натурал сандардың
немесе барлық бүтін сандардың жиынын тізім арқылы беру, яғни ол жиындардың барлық
элементтерінің тізімін жасау мүмкін емес. Мұндай жағдайда жиынды оның кейбір
сипаттамалық қасиетін көрсету арқылы береді.
2. Сипаттау арқылы. Мысалы жиынның кез келген х мүшесі р(х) қасиетіне ие
болсын, онда осы элементтерден тұратын С жиыны былай беріледі: xpxC / .
Осы сияқты анықталған жиындар  NnnxxBmZmn
m
n
Q 






 ,12:,0,,/

Анықтама. А және В жиындары берілсін. Егер А жиынының кез келген х элементі В
жиынындада да жатса, онда А жиыны В жиынының ішкі жиыны деп аталады.BA және AB
деп белгіленеді. Кванторлар тілінде   BxAxBA 

Анықтама. Егер В жиынының А ішкі жиыны В жиынынан және  -ден өзгеше болса,
онда ол меншікті ішкі жиыны деп аталады. Кванторлар тілінде, BBAABA 
 кез келген жиынның ішкі жиыны:A
Қасиеттері:
а) AA
ә) ;, BAABBA 
б) ., CACBBA 
Анықтама. В жиынының В және  ішкі жиындары оның меншіксіз ішкі жиындары
деп аталады. Егер жиын ең болмағанда екі элементтен тұрса, онда оның меншікті ішкі
жиындары болады.
Мысалы: А={а,в} жиынының ішкі жиындары: {а},{в}, { },{а,в}. Бұл ішкі жиындардың
ішінде {а},{в} – меншікті, ал { },{а,в} – меншіксіз болып табылады.
Анықтама. Егер А жиынының әрбір элементі В жиынының да элементі болса және
керісінше, В жиынының әрбір элементі А жиынының да элементі болса, онда А мен В
жиындары тең деп аталады да, былай жазылады: А=В. Мысалы, А= {1,3,5,7,9} және В=
{9,3,1,5,7} жиындары тең.

6
Анықтама. Элементтері өзара бірмәнді сәйкестікте болатын жиындарды тең қуатты
жиындар деп атайды.
Егер А= {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 жиынынан алынған д еп есептейік. Мысалыға:    6.5,5.3.1,4.3.2.1  CBА
жиындарын алайық.
1) Ең болмағанда А жиынына немесе В жиынына тиісті элементтер жиынын А және В
жиындарының бірігуі (қосындысы) ВА деп атаймыз.  ВхнемесеAxхВА  :

7
 5,4,3,2,1ВА  ,6,5,4,3,2,1СА
2) А жиынына да В жиынына да тиісті элементтер жиынын А және В элементтер
жиынының қиылысуы (көбейтіндісі) деп аталады.  ВхжанеAxхВА  :

3,1ВА
5СВ СА
3) А жиынына тиісті, бірақ В жиынына тиісті емес элементтер жиынын А және В
жиындарының айырымы (А\В) деп атайды.  ВхжанеAxхВА :\

3,1\ВА
3,1\СВ АСА\
4) А және В жиындарының симметриялық айырымы (сақиналы қосынды) (А В) деп
келесі жиынды айтамыз  )()(:)\()\( АхжанеВхнемесеВхжанеAxхАВВАВА 

  6,5,4,3,2,1)6,5()4,3,2,1(,5,4,2)5()4,2(  САВА

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


Универсум  9.8.7.6.5,4,3,2,1U болса, онда  9.8.7.6.5

А болады.

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

8
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 Қосалқы принципі (де Морган заңы) BA
=A  B , 


n
k
k
A
1 
n
k
kA
1
BA
=A  B , 


n
k
k
A
1 
n
k
kA
1
9
Екі рет теріске шығару A =A

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

Жиындардың декарттық (тура) көбейтіндісі.
Кортеж ұғымына сүйеніп, екі жиынның декарттық көбейтіндісін анықтауға болады.
Мысал. А={а, в, с}, В={3, 4} шектеулі жиындары берілсін. Осы жиындардың элементтерінен
ұзындығы 2-ге тең кортеждердің жиынын
құрайық. Олар: {(а;3),(а; 4),(в;3), (в;4), (с;3),(с;4)}.
Анықтама. А және В жиындарының декарттық (тура) көбейтіндісі деп біріншікомпоненті
А жиынынан, екінші компоненті В жиынынан алынған барлық реттелген жұптардың жиынын
айтады. А және В жиындарының декарттық көбейтіндісін А  В деп белгілейміз.
Анықтама бойынша: А  В = {(х ,у) | хА және уВ}. nAAA,...,,
21
жиындары үшін декарттық көбейтіндісі? nAAA  ...
21
= 

т
m
iA
1 = },...,,),...,,{(
221111 nnn
AxAxAxxxx  болады.
Егер A1=A2=…=An=A болса, онда A1хA2х,…,хAn жиыны А жиынының n-ші
декарттық дәрежесі деп аталады және А
n
болып белгіленеді. Анықтама бойынша A
0
⇌{}
Мысалдар:
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]
2
жиыны { (a,b) | 0  a 1, 0  b  1 } ;Бұл жиынға жазықтықтың 1-ден
аспайтын теріс емес координаттары бар нүктелер жиыны сәйкес келеді.
4. ]3,2[],1,0[
21  AA екі жиынын қарастырайық. Егер жазықтықтағы декарттық
координаталар жүйесін қарастырсақ, онда 21AA ұзындығы бірге тең квадрат ретінде
қарастыруға болады.

9


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.},...,,{
21 mxxxX ; },...,,{
21 nyyyY ; YX, - жиындарының декарттық көбей-тіндісін
табайық. Декарттық көбейтіндісінің элементтері әр түрлі жиын элементтерінен алынған
жұптардан тұратындығы белгілі.
Оларды кестеге орналастырайық: Бұл кестеде m жол, n бағаннан тұратын элементтер
жұбын көреміз. ),(yx - саны х-элементтерінің жиыны мен ү элементтерінің жиындарының
көбейтіндісіне тең.
)()(),( yxyx   (1)
Бұл жиындарды көбейту ережесі. Егер декарттық көбейткіштері n жиыннан тұрса,
онда (1) төмендегідей жалпылауға болады:
)()...()()*...**(
2121 nn xxxxxx  
(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} ; АхВ 









332313
322212
312111
bababa
bababa
bababa ;
1 – есеп. BABA  Де Морган заңын (қосалқы принципі) дәлелдеу керек.
Шешуі: І әдіс Эйлер-Венн диаграммасы арқылы. Ол үшін теңдіктің сол жағындағы жиынды
кескін деп аламыз:
а)BA

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

10 BAx

Байқасақ, жоғарыдағы диаграммада штрихпен белгіленген жиын мен төмендегі
тормен белгіленген бір жиынды береді, бұл екі жиынның теңдігін білдіреді.
ІІ әдіс қасиеттерге сүйеніп, өрнектерді түрлендіру арқылы.
Алдымен UVVUVU  , қасиеті бойынша:
1) BABA  ;
2) BABA  енгізулері орындалатынын көрсетейік.
1)AxBAxBAx  және AxBx  және ;BAxBx 
2) керісінше, AxBAx  және AxBx  және .BAxBAxBx 

Жиынның бүркеуі мен бөлекшесі.
Жиындарға қолданылатын операциялардың тағы бір түрі – жиынды ішкі жиындар
жүйесіне бөліктеу операциясы болып табылады. А жиыны мен оның ішкі жиындар жүйесін
A },1/{}....,,{
21
niAAAA
in
 қарастырайық.
Анықтама 1. Егер 1) 
iA A ],,[ 
ii AAA 2) 
n
i
iAA
1
 ; шарттары орындалса, онда
A жиын жүйесін А жиынының бүркеуі деп атайды.
Анықтама 2. 1) 
iA A ],,1,,[ niAAA
ii
 2) 
n
i
iAA
1

3) 
ji
AA, A ][ 
jiji
AAAA немесе 
ji
AAjinji ,,1, шарттары
орындалса, онда A жиын жүйесі А жиынының бөлікшесі деп аталады.
Егер бүркеу анықтамасындағы екі шартқа 3) шартты қоссақ, онда бүркеу бөлікше
бола алады. Басқаша айтқанда, егер әрбір Ax элементі тек қана бір iA ішкі жиынына
тиісті болса, онда А жиынының бос еме ішкі жиындарының A жүйесі оның бөлікшесі бола
алады.
1 – мысал. }3,2,1{A жиыны берілсін:
а) }}1,3{},3,2{},2,1{{
1A - А жиынының бүркеуі;
ә) }}3{},2{},1{{
2A - А жиынының бөлікшесі болады;
б) }}2{},1{{
3A - қандай-да бір ішкі жиындардың жүйесі, ол бүркеуі де емес, бөлікшесі де
емес, себебі }3,2,1{}2{}1{  .
2 – мысал. N – натурал сандар жиынын қарастырайық. 0N - жұп, 1N - тақ сандар жиыны
болсын. Онда NNN },{
1 бөлікшесі бола алады.
Сәйкестік және оның қасиеттері.
Анықтама. А, В жиындарының арасындағы сәйкестік деп бұл жиындардың тура
(декарт) көбейтіндісінің 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
болса толық емес (жартылай) сәйкестік болады. (толық анықталмаған).

11
Анықтама. Егер 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)
2
+(y-2)
2
≤1 қатынасын қанағат тандыратын барлық (х,у)
нақты санды сандар жиыны болсын. G={(x,y)|x,y үшін (x-3)
2
+(y-2)
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 – сәйкестігінің қандай қасиеттері бар?

12
Шешуі: Егер 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 және fyxfyx  ),(,),(
21 болғандығынан 21yy болса, онда BAf 
сәйкестігі функция деп аталады ол f : AB немесе BА
f
 болып жазылады.
Бұл анықтамадан функция дегеніміз функционал сәйкестік екендігін көреміз және f
функциясының типі АВ деп оқылады . f функциясы анықталу облысының әрбір
элементіне (х ) мәндер облысынан бір мәнді (у)сәйкестендіреді және у = f (х) болып
белгіленеді. ) (х аргумент, у функцияның мәні) болып жазылады (у х -тың
образы).Мысалдар: f={(1,2),(2,3),(3,2)} – функция; f={(1,2),(1,3),(2,3)} - функция емес;
{(x,x
2
-2x+3), xR} – функция ; бұл функция әдетте y=x
2
=2x+3 болып жазылады.
Анықтама Толық анықталған функция f : AB А-ны В-ға іштей бейнелеу деп
аталады. f : A
iштей B ( f=A ,  f B) толық анықталған функция
Анықтама Егер  f = B болса функция сюръективті функция деп аталады.
Анықтама Егер функция толық анықталған (f=A) және сюръективті (f=B) болса
,онда ол А-ны В-ға толық бейнелеу деп аталады: f : A
тол ык B болып жазылады.
Анықтама .А
iштей А бейнелеу А жиынын түрлендіру, ал А
тол ык А бейнелеуі А-
ға алмастыру деп аталады А 
Ал м астыру А болып та белгіленеді.
f және g функциялары тең болады, егер төмендегі шарттар орындалса:
• Олардың анықталу облыстары біреу -ол Ажиыны;
• Кез-келген а  A үшін f(a) = g (a).

Сәйкестік
Міндетті түрде болу керек қасиеті
Функционалды
Толық
анықталған
Сюръективті
Функция
А-ны В-ға іштей
бейнелеу
А-ы В-ға толық
бейнелеу
+
+
+

+
+


+

13
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: В
n
 С функциясы үшін f-ті g –ға қоюдың әртүрлі варианттары бар. Нәтижесінде
әртүрлі типтегі функциялар алынады. Мысалы, т = 3 және п = 4 үшін h = g (x1, f(у1,у2, у3), х3,
х4) функциясында 6 аргумент бар ал оның типі В  А
3
 В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[:  if
i

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

14
f2 – инъективті, сюръективті емес
f3 – инъективті, сюръективті – биекция
f4 - инъективті де емес, сюръективті де емес
2- мысал: Үш функцияны қарастырайық :3,2,1,: iRRf
i
1) x
exf)(
1 инъективті, сюръективті емес
2) xxxf sin)(
2  сюръективті, инъективті емес
3) 12)(
3 xxf биективті;

Бақылау сұрақтары:
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} сандар жиынын қарастырайық. Бұл сандардың

15
арасында «артық» қатысы бар, 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
2
немесе (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
n
.
Бинарлық қатынастар жиын болғандықтан, жиынның берілу тәсілдерінің бәрімен
беріле алады. Ақырлы жиындарда берілген қатынастар әдетте төмендегідей әдістермен
беріледі:
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. Графиктік түрде: Графиктік кескіндеудің бірнеше түрлері
бар:

16
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
2
, 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
2
)
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
2
, онда
Р○Р={(a,b) | (a,c),(c,b)P}
Мысалы Р-баласы болу болса, онда Р○Р-немересі болу.

Бинарлық қатынастардың негізгі қасиеттері.
1. А жиынында берілген бинарлы қатынас болсын: РА
2
.Кез-келген хА үшін х Р х
қатынасы бар болса, Р қатынасы рефлексивті деп аталады. (бір жиын ішіндегі жұптар
қатынасы мы салы бір қалада тұру - рефлексивті).
2. Егер х Р х қатынасы А жиынның бір де бір элементі үшін орындалмаса Р қатынасы
антирефлексивті (баласы болу қатынасы - антирефлексивті). Антирефлексивті матрицаның
бас диагоналы тек нөлдерден тұрады.
3. Егер кез-келген х,уА үшін (х,у)Р(у,х)Р болса, яғни Р
-1
=P немесе[P]
T
=[P]
болса, Р қатынасы симметриялы деп аталады. Егер x A y болудан у А х болса (бір фирмада
жұмыс жасайды), онда А симметриялы.

17
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 = 




болсажоаатынабинарлыегерPbаегер
болсабараатынабинарлыегерPbаегер
jі
jі
),(,0
),(,1
Алынған бұл матрица элементтер арасындағы
байланыс туралы толық ақпарат береді және оны
компьютерге өрнектеу мүмкіндігі бар. Мысалы, Суретте
көрсетілгендей PA
2
A={1,2,3} бинарлы қатынасының
матрицасы
[P]=









001
100
111 ; P={(1,1),(1,2),(1,3),(2,3),(3,1)}
2-мысал. M={1,2,3,4,5,6}. Егер Р  қатаң кіші болуды білдір се РМ х М қатынасын
тізім және матрица түрінде бейнелеу керек: Р қатынасы М жиынының a b болатын
элементтер жұбынан тұрады. Р=};,),({ baMbaba  . Олай болса, Р қатынасын тізім және
матрицамен беруге болады: Р={ (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4),
(3,5), (3,6), (4,5), (4,6)} ;
Анықтама. Кез-келген жиын үшін анықталған
IdA={(x,x) | xA} қатынасы тепе-теңдік қатынас немесе
диагональ қатынас деп аталады, ал UA⇌A
2
универсалды
немесе толық қатынас деп аталады. Айталық, Р – бинарлы
қатынас болсын.  P⇌{x | (x,y)P қандай да бір Y үшін}
жиыны Р қатынасының анықталу облысы деп, ал Р⇌{y | (x,y)P қандай да бір Х үшін}
жиыны Р қатынасының мәндер жиыны деп аталады. Мысалы, A = {2, 3, 4, 5, 6, 7, 8}
жиынының P = {(x, y) | x, y  A, у x ке бөлінеді және х ≤3} қатынасы үшін
P={(2,2),(2,4),(2,6),(2,8),(3,3),(3,6)) қатынасы мен х={3} үшін анықталу облысы Р={2,3}.
Мәндер аймағы Р={2,3,4,6,8};
Бинарлы қатынастар матрицалдарының негізгі қасиеттері.
Егер P,QAхB, [P]=(pij), [Q]=(qij) болса, oнда [PQ]=(pij+ qij) және [PQ]=(pij* qij)
мұндағы қосу [PQ]=[P]+[Q], 0+0⇌0, 1+1⇌1+0⇌0+1⇌1 ережесімен, ал [PQ]
көбейту [P] мен [Q] сәйкес элементтерін тура көбейтуден алынады: [PQ]=[P]*[Q]
Мысалы, 








011
101
][P , 








001
011
][Q P,Q қатынастарының матрицасы болса, онда 


























011
111
001
011
011
101
][][][ QPQP
; 


























001
001
001
011
011
101
][][][ QPQP 

















100000
110000
111000
111100
111110
P

18
Егер PAхB, Q=B х C, онда [PQ]=[P][Q]; Мұнда [P] және [Q] матрицаларын
көбейту матрицаларды көбейтудің әдеттегі ережесімен, ал [P] мен [Q] алынған элементтердің
көбейтіндісі мен қосындысы 1 пунктегі ережелермен жүргізіледі. Мысалы,    

















































11
10
11
10
01
110
010
онда ;
11
01
10
;
0
0
1
1
1
0
QPQP
; P
-1
кері қатынастың матрицасы Р
қатынасының транспонирленген матрицасы:[P]
-1
=[P]
T

PQ; [P]=(pij), [Q]=(qij) болса, онда pij≤qij

Эквивалентті қатынас және кластарға бөлшектеу.
Анықтама Рефлексивті, симметриялы және транзитивті Р бинарлы қатынасы
эквивалентті қатынас немесе жай ғана эквивалентті деп аталады. Эквиваленттілік Е
символымен немесе ~ белгісімен белгіленеді. х Е у немесе х~у Мысалы х=у болу қатынасы
кез-келген А жиынында эквивалентті қатынас. x=x –болғандықтан рефлексифті.
x=yy=xсимметриялы.x=y, y=zx=z– транзитивті.
Адамдар жиынында бір қалада тұру эквиваленттік.
7 бөлгендегі бірдей қалдық болу қатынасы эквиваленттік.
R={(a,b) | a,bN, a/7, b/7 қалдық бірдей}R – жиындағы эквиваленттік.
Бұл қатынас (11,46 ), (14,170) жұптарына орындалады.ҚазҰТУ студенттер жиынынан
бір топқа жату эквиваленттілік–эквивалентті қатынас. Айталық, М жиынында R
эквиваленттілігі берілсін (R эквивалентті қатынас берілсін). Белгілі бір тәртіппен М-ң ішкі
жиындарын құрайық. Ішкі жиындарды класс деп атайық.С 1–класы а1М және оған
эквивалентті элементтен құралсын; С2 – класы а2М және оған эквивалентті элементтерден
құралсын т.с.с. осылай жалғаса берсін.С1, С2,...,Сі кластар жүйесі құралады. М жиынының
кез-келген элементтері ең болмағанда бір класқа кіреді, яғни

Бұл кластар жүйесінің мынадай қасиеттері бар:Олар бөлімдер құрайды, яғни кластар
өзара қиылыспайды; Бір кластағы кез-келген 2 элемент эквивалентті;Әр кластан алынған кез-
келген 2 элемент эквивалентті емес.Бұл қасиеттер R қатынасының рефлексивтілік,
симметриялық және транзитивтік қасиеттерінен шығады.М жиынынан осылай бөлшектеу,
яғни кластар жүйесі R қатысты эквивалентті кластар жүйесі деп аталады. Бұл жүйенің қуаты
бөлу индексі деп аталады.

Реттік қатынас.
Анықтама. А жиынында берілген Р қатынасы антисимметриялы және транзитивті
болса, онда Р реттік қатынас деп аталады.
Барлық қатынастар не эквивалентті, не реттік болып бөлінеді деп ойлауға болмайды.
Эквивалентті де, ретті де болмайтын қатынастың түрлері бар.
Егер қатынас рефлексивті ,антисимметриялы және транзитивті болса, қатаң емес
реттік қатынас деп аталады.Егер қатынас антирефлексивті, антисимметриялы және
транзитивті, қатаң реттік қатынас деп аталады. Қатынастардың бұл екі түрі реттік
қатынастары деп аталады.
Мысал  ,  қатынастары қатаң емес,  ,  қатынастары қатаң. Бұл екі қатынастар
N, Р жиындарын реттейді.

Бақылау сұрақтары:
1.Жиындағы бинарлық қатынас дегеніміз не?
2. Бинарлық қатынастың қандай қасиеттері бар? Мысалдарын келтіріңіз.
3. Эквивалентті қатынастың және кластарға бөлшектеудің анықтамасын беріңіз.
5. Реттік қатынас дегеніміз не?

19
Пайдаланылған әдебиеттер:
1. Байсалов М.Ж. Дискретті математика. Оқу құралы. Алматы, 2007.
2. Жетпісов Қ. Математикалық логика және дискретті математика, Қарағанды, 2008.
3. Мутанов Г.М.,Акбердин Р.А. Теория графов. – Алматы, изд-во «Рауан», 2008.
4. Нефедова В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 2011.
5. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Изд-во МГТУ
им.Н.Э.Баумана, 2010.


Дәріс № 3. Тұжырымдар мен тұжырымдар формасы. Тұжырымдар логика -сының
негізгі логикалық байланыстырушылары. Логика алгебрасы. Тұжырымдар
логикасының формуласының анықтамасы. Тұжырымды формальдау процедурасы.

Дәріс түрі: Ақпараттық дәріс
Дәріс мақсаты:
1. Математикалық логика тарихына қысқаша шолу.
2. Тұжырымдар логикасының негізгі лог икалық байланыстырушылары
туралы ұғымдар.
3. Тұжырымдарды белгілейтін әріптер, логикалық байланыстар, жақшалар логикалық
тұжырым тілінің алфавиті.
4. Алфавит элементтерінің көмегімен түрлі формулалар құру.
5. Тұжырымдар алгебрасының формулалары түсінігін енгізу.
6. Буль алгебрасының негізгі заңдарын оқыту.
7. Логикалық формулалардың классификациясын қарастыру.

Дәріс жоспары:
• Тұжырымдар мен тұжырымдар формасы.
• Жай және күрделі тұжырымдар.
• Тұжырымдарға қолданылатын логикалық амалдар.
• Логика алгебрасы.
• Тұжырымдар логикасы формуласының анықтамасы.
• Тұжырымды формальдау процедурасы.
• Логикалық тұжырымдар формулаларының эквиваленттілігі.
• Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған
формулалары.
• Негізгі тепе-теңдіктер.
Негізгі ұғымдардың сөздігі: Логика, тұжырым (жай, күрделі), терістеу, конъюнкция,
дизъюнкция, эквиваленция, импликация, логика алгебрасы, тұжырымдар формуласы,
эквивалентті формулалар, пара-пар, тепе-тең ақиқат, тепе-тең жалған.

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

"Логика" термині гректің  (логос) деген сөзінен шыққан. Бұл сөздің мағынасы
"түсінік", "ес, ақыл-ой" дегенді білдіреді. Логика ғылым ретінде ойлауды оқытады.
Логика дұрыс ойлаудың формалары мен заңдары туралы ғылым. Математикалық
логика дәстүрлі локикадан дамыған. Бұл ғылым дұрыс ойлаудың жалпы құрылымын зерттеу
үшін математикалық әдістерді қолданып, математиканың бір бөлімі болып қалыптасты.
Логиканың ғылым ретінде негізін салған ежелгі грек философы және ғалымы Аристотель
(384 - 322 ж. б.э.д.) болатын. Ол дедукция теориясын, яғни логикалық түрде қорыту
теориясын жасап шығарды.

20
Тұжырымдар мен тұжырымдар формасы.
Қазақ тілінде сөйлемнің үш түрі бар екенін білеміз: хабарлы сөйлем,сұраулы сөйлем,
лепті сөйлем. Математикалық логикада осылардың ішінде хабарлы сөйлемдер
қарастырылады. Мынадай бірнеше жай сөйлемдер берілсін:
1. Маңқыстау-мұнайлы өлке;
2. Натурал сандар жиыны шектеусіз;
3. 7 саны – тақ сан;
4. 42 саны 3-ке бөлінбейді;
5. Тең бүйірлі үшбұрыштың барлық бұрыштары тең.
Мазмұны жағынан бұл сөйлемдер әртүрлі. Бірақ, олардың барлығына ортақ бір
қасиеттің бар екенін байқауға болады. Ол қасиет-кейбір сөйлемдерде
ақиқат, ал кейбір сөйлемдерде жалған ойдың айтылуы. (1, 2 , 3 –сөйлемдер ақиқат, ал 4, 5-
сөйлемдер жалған)
Анықтама. Тұжырым деп ақиқаттығы немесе жалғандығы туралы айтуға болатын
байланысты баяндамалы сөйлемді айтамыз.
Бірақ хабарлы сөйлемнің барлығы тұжырым бола бермейді. Мысалы, «математика- ең
қызықты пән», «оның шашы сары», «х > 1», «басқа планеталарда да тіршілік бар»
сөйлемдерінің ақиқат не жалғандығы туралы ешқандай тұжырым айта алмайсың. a
2
= 4
сөйлемін алып көрейік. Дәл осы тұрысында бұл сөйлем тұжырым емес. Ал енді осындағы а -
ны айнымалы деп, ал {-2,0,3,4}-айнымалының мәндерінің жиыны деп қарасақ, сол
айнымалының әрбір мәніне сай жалған немесе ақиқат пікір шығады.
Мысалы, (-2)
2
= 4 (ақиқат) 0
2
= 4 (жалған) 2
2
= 4 (ақиқат).
Яғни, кез-келген сөйлем тұжырым болмайды.
Анықтама. Құрамына ең болмаса бір айнымалысы бар және айнымалылардың
орнына мәндерін қойғанда тұжырымға айналатын сөйлем тұжырымдылық форма деп
аталады.
Тұжырым туралы жалпы әңгіме болғанда оның мазмұнына қарамаймыз, тек ақиқат не
жалған екендігін анықтаймыз.
Тұжырымдар А, В, С т. с. с латынның бас әріптерімен белгіленеді, ал мағынасы ақиқат
болса тұжырымның тұсына а әрпі немесе 1 саны, жалған болса ж әрпі немесе 0 саны
жазылады.

Жай және күрделі тұжырымдар.
Қазақ тіліндегі жай және құрама сөйлемдер сияқты логикалық тұжырымдарда жай
(қарапайым, элементар) және күрделі болып бөлінеді. Жай (қарапайым, элементар)
тұжырым деп басқа тұжырымдарға жіктеуге келмейтін тұжырымды айтамыз. Ал, бірнеше
тұжырымдарға жіктеуге болатын тұжырым күрделі тұжырым деп аталады. Күрделі
тұжырымдар әр түрлі жалғаулықтармен байланысқан бірнеше жай тұжырымдардан
құралады. Мысалы, «102 саны жұп сан және 3- ке бөлінеді», «Үшбұрыштар қабырғаларына
қарай тең бүйірлі немесе тең қабырғалы болып бөлінеді», «Жай сан өзіне және 1- ге
бөлінеді» тұжырымдары күрделі. Олар «және», «немесе» деген сөздермен байланысқан жай
сөйлемдерден құралып тұр. Қазақ тіліндегі «және», «немесе», «егер, онда», «емес», «сонда
тек сонда ғана» сөздері логикада логикалық жалғаулар (байланыстар) деп аталады. Сонымен
логикалық жалғаулар арқылы кез-келген элементар тұжырымнан күрделі тұжырым алуға
болады. Айтылған сөйлемнің ақиқат не жалғандығы біржақты шешілуі үшін логикалық
байланыстардың қызметі зор. Күрделі тұжырымға кіретін элементар пікрлердің ақиқат
немесе жалғандығына қарай күрделі тұжырымның ақиқат немесе жалғ ан екендігі
анықталады. Ол үшін алдымен күрделі тұжырымдағы элементар тұжырымдарды әріптермен
белгілеп, берілген күрделі тұжырымның логикалық құрылымын анықтайтын өрнек аламыз.
Осындай өрнек бар болса, онда осы өрнекке сәйкес келетін күрделі тұжырымның ақиқат
немесе жалған екендігін анықтауға болады.

21
Тұжырымдарға қолданылатын логикалық амалдар.
Терістеу.
Кез келген А тұжырымынан оны теріске шығара отырып, жаңа тұжырым алуға
болады. Мысалы, «кез келген үшбұрышты сырттай шеңбер сызуға болады»,«кез келген
үшбұрышты сырттай шеңбер сызу мүмкін емес» тұжырымдарының біріншісін екіншісі
теріске шығарып тұр (бұл жерде «емес» логикалық жалғауы қолданынылып тұр).
Анықтама. А-ның терістеуі (инверциясы) деп А жалған болса мәні ақиқат, ақиқат
болса жалған болатын тұжырымды айтады.
Екеуі бірдей ақиқат немесе екеуі бірдей жалған болу мүмкін емес.
А пікірін теріске шығаруды А немесе ¬А деп белгілейді. ( «А емес» немесе «дұрыс
емес А» деп оқылады)
Жоғарыдағы мысалда А пікірі ақиқат, ал А пікірі жалған.
Егер А- «қиылысатын түзулер бір жазықтықта жатпайды» десек, А - «қиылысатын
түзулер бір жазықтықта жатады» деген тұжырымды береді. Бұл жерде керісінше, А-
тұжырымы жалған, А -тұжырымы ақиқат.
А және А тұжырымдарының арасындағы байланысты кесте арқылы көрсетуге
болады.
А А
a ж
ж a

Бұл түрдегі кестені ақиқаттық кестесі деп атайды.
Конъюнкция.
«АВСD параллелограмының диагональдары қиылысады және қиылысу нүктесінде қақ
бөлінеді» тұжырымының логикалық құрылымын анықтайық. Мысалдағы күрделі тұжырым
«және» жалғауы арқылы байланысқан екі қарапайым тұжырымдардан құралып тұр. «АВСD
параллелограмының диагональдары қиылысады» тұжырымын А деп, « қиылысу нүктесінде
қақ бөлінеді» тұжырымын В деп белгілесек,онда берілген тұжырым «А және В» деп
жазылады.
Анықтама. А және В тұжырымдарының конъюнкциясы(біріктірушісі) деп, егер екі
тұжырымда ақиқат болғанда ақиқат және егер кем дегенде біреуі жалған болғанда жалған
болатын жаңа тұжырымды айтамыз.
А және В Тұжырымдарының конъюнкциясы мына символмен белгіленеді АВ
(АּВ, А В, А&В) және былай оқылады «А және В». А, В тұжырымдары конъюнкция
мүшелері деп аталады. А және В екі тұжырымның барлық мүмкін логикалық мәндерінің
конъюнкциясы келесі ақиқаттық кестеде көрсетілген:

А В АВ
a a a
a ж ж
ж a ж
ж ж ж
Конъюнкция операциясы анықтамасында көрсетілгендей «және» сөзі логика
алгебрасында күнделікті сөйлесудегі сияқты мағынада қолданылады. Бірақ кәдімгі
сөйлесуде «және» сөзімен мағынасы әртүрлі екі тұжырымды біріктіру қабылданбаған, ал
логика алгебрасында кез-келген екі тұжырым конъюнкциясы қарастырылған. Мысалы,
«екі көбейту екі тең төрт және бүгін бейсенбі».

22
Дизъюнкция.
Математикада «21 10», «16  7 » деген пікірлер жиі кездеседі. Енді осы
пікірлердің ақиқат не жалғандығын анықтап көрейік. «21  10» теңсіздігін «21
саны 10-нан артық немесе тең» деп оқимыз. Сонда бұл тұжырым «21>10» деген
ақиқат және «21= 10» деген жалған тұжырымдардан құралып тұр.
Осы тұжырымдарды «немесе» жалғаулығымен байланыстыра алынған
күрделі тұжырым ақиқат.
«16  7» жалған тұжырым, өйткені ол «16< 7» және «16= 7» деген екі жалған
тұжырымдардан құралып тұр.
«126 саны жұп немесе 3-ке бөлінеді» тұжырымы ақиқат,өйткені ондағы екі
тұжырымда ақиқат. Бұл тұжырымдардың бәрі күрделі, олардың логикалық
құрылымы «А немесе В» болады.
Анықтама. А және В тұжырымдарының дизъюнкциясы (ажыратушысы) деп, егер екі
тұжырымның бірі ақиқат болса, ақиқат және егер екеуі де жалған болса, жалған болатын
жаңа тұжырымды айтамыз.
А және В тұжырымдардың дизъюнкциясы мына символмен белгіленеді: АВ және
былай оқылады «А немесе В». А, В Тұжырымдары дизъюнкция мүшелері деп аталады.
А және В екі тұжырымның барлық мүмкін логикалық мәндерінің дизъюнкциясы келесі
ақиқаттық кестеде көрсетілген:

А В АВ
а а а
а ж а
ж а а
ж ж ж

Эквиваленция.
Анықтама. А және В екі тұжырымдарының эквиваленциясы деп егер тұжырымдар
бірдей ақиқат немесе жалған болса, ақиқат, ал қалған жағдайларда жалған болатын жаңа
тұжырымды айтамыз.
А және В тұжырымдарының эквиваленциясы мына символмен белгіленеді: А~В
(АВ) және былай оқылады: “А үшін қажетті және жеткілікті В” немесе “А сонда және
тек сонда ғана, қашан В”. А,В тұжырымдары эквиваленция мүшелері деп аталады.
А және В екі тұжырымның барлық мүмкін логикалық мәндерінің эквиваленциясы
келесі ақиқаттық кестеде көрсетілген:







Мысалы: «S төбесі және PQ негізімен берілген SPQ үшбұрышы тең бүйірлі болады,
сонда және тек сонда ғана, қашан  P= Q» эквиваленциясы ақиқат. “ S төбесі және PQ
негізімен берілген SPQ үшбұрышы тең бүйірлі” және “ S төбесі және PQ негізімен берілген
SPQ үшбұрышында  P= Q ” тұжырымдары бір мезгілде ақиқат немесе жалған.
А В А~В
a a a
a ж ж
ж a ж
ж ж a

23
Импликация.
А және В екі тұжырымның импликациясы (тығыз байланыстылығы) деп, егер А
ақиқат, ал В – жалған болса жалған және қалған жағдайда ақиқат болатын жаңа
тұжырымды айтамыз.
А және В тұжырымдарының импликациясы былай белгіленеді: А В
(А  В,А В) және былай оқылады “егер А, онда В ” немесе «А-дан В шығады». А
тұжырымын шарт немесе сілтеме тұжырым, ал В тұжырымын – салдары немесе
қорытынды деп атайды.
А және В екі тұжырымның барлық мүмкін логикалық мәндерінің импликациясы келесі
ақиқаттық кестеде көрсетілген:





Логикалық амалдармен алғаш танысқанда импликациядан басқаның барлығы
мейлінше табиғи түрде енгізілген секілді. Ал импликация анықтамасын енгізуді
қабылдауға біздің санамыз қарсылық көрсетіп жатқандай болып көрінеді. Бірақ
импликацияның мұндай анықтамасы біздің түйсікті ішкі логикамызға және математикада
өте жиі қолданылатын «егер …, онда....» конструкциясына сәйкес келетіндігін көрсететін
мысал келтіруге болады. Арифметикадан бір теореманы еске түсірейік - Q(x)= «Егер х
натурал саны 4-ке бөлінсе онда, ол 2-ге бөлінеді». Бұл теореманың әділдігіне біз күмән
келтіреміз, яғни Q(x ) - қа қандай х натурал санын қойсақ та біз ақиқат тұжырым аламыз.
Белгілеу енгіземіз: А(х)= «х натурал саны 4-ке бөлінеді», В(х)= «х натурал саны 2-ге
бөлінеді».
Сонда шығатыны:
Q(x )= А(x ) В(x ) (1)

(1) формулаға х=8, 2, 3 мәндерін қоя отырып келесілерді аламыз: a  a, ж a, ж ж.
(1) формулаға a  ж шарты орындалатындай х-тің мәнін қою мүмкін емес (себебі
келтірілген теорема әділ).
Қарапайым тілде «Егер А, онда В» түрдегі сөйлемде А мен В мазмұны жағынан
байланысты екенін көреміз. Біздің импликация анықтамасында бұл мүлде міндетті емес.
Яғни біз мынадай импликацияны қарастыру құқымыз бар: «Егер бүгін бейсенбі болса, онда
2*2=5», бұл бейсенбіден басқа барлық күні ақиқат, ал бейсенбіде жалған.

Логика алгебрасы.
Логика алгебрасы математикалық логиканың бір бөлімі. Логика алгебрасында
күрделі логикалық тұжырымдардың (логикалық формулалардың) құрылымы және
алгебралық әдістердің көмегімен олардың ақиқаттығын анықтау әдістері қарастырылады.
Бұл бөлімде негізінен логика алгебралық формулаларын қарастыратын боламыз.
Формулалар әріптерден, логикалық операциядан және жақшадан тұрады. Әріптер тек
“ақиқат”, “жалған “ деген екі мәннің бірін ғана қабылдай алатын логикалық айнымалылар.
Операция белгілері логикалық амалдарды белгілейді. Әр формула логикалық функцияны
береді, ал функция өз кезегінде 2 мәннің бірін қабылдайды (a,ж). Логика алгебрасы
А В АВ
a a a
a ж ж
ж a a
ж ж a

24
дегеніміз өзінің барлық мүмкін операцияларымен бірге қарастырылатын {a,ж} жиынынан
құралған алгебра.

Тұжырымдар логикасы формуласының анықтамасы.
Анықтама. Егер А – формуласының барлық айнымылылары <x1i ,…,xik > реттелген
жиынтығына жатса, онда бұл <x1i ,…,xik > жиынтығы А формуласының айнымалылар
тізімі деп аталады. Тізімдегі айнымалылардың бір бөлігі А ға айқын кірмеу мүмкін. Оларды
жасанды айнымалы дейміз.
Анықтама. Тізімдегі әр айнымалыға ақикаттық мән сәйкестендіруді айнымалылар
тізімін бағалау дейміз. Егер А формуласының айнымалылар тізімінде к айнымалы болса онда
2
k
– ке тең бағалар болады, демек ақикаттың кестесінде 2k – тең жол болады.
Тұжырымдарды белгілейтін әріптер, логикалық байланыстар, жақшалар логикалық
тұжырым тілінің алфавиті деп аталады. Алфавит элементтерінің көмегімен түрлі формулалар
құруға болады. Математикалық логикада қабылданғандай формулаға нақтылы анықтама
берейік:
Анықтама. Тұжырымдардың белгілері және логикалық байланыстырушылармен
(жақшада көрсетілген) құрылған өрнек логикалық формула деп аталады,егер ол төмендегі
шарттарды қанағаттандырса:
1.Тұжырымдарды белгілейтін кез келген логикалық айнымалы - формула;
2. a, ж – символдары формула;
3. Егер А – формула болса, онда  А формула;
4. Егер А и В – формулалар болса ,онда (А  В), (А  В), (А  В), (А ~ В) – формула
болады;
Алдыңғы төрт пункттегіден басқа формула жоқ.

Тұжырымды формальдау процедурасы.
Егер тұжырым қарапайым болса, оған қарапайым формула сәйкестендіріледі.
Егер тұжырым күрделі болса, онда оған сәйкес формула құру үшін
а) Күрделі тұжырым құрып тұрған барлық қарапайым тұжырымдарды
байланыстырушылардан бөліп алу керек;
б) Оларды сәйкес символдармен алмастыру керек;
в) Тұжырымдардың мағынасына қарай жақшалар қою керек. Формула қарапайым
болу үшін сыртқы жақшаларды жазбауға болады; Жақшалар сыңарлары тең болу керек.
Мысалы, 1321)( xxxx  -формула емес; 121 )( xxx  - формула; ~(
1x 32)xx  -
формула.

Логикалық тұжырымдар формулаларының эквиваленттілігі.
Анықтама. Айталық А мен В бір айнымалылар тізіміне <kii
xx,...,
1 > тәуелді екі
формула болсын. Егер олар <kii
xx,...,
1 > тізімінің кез- келген бағасында бірдей мәндер
қабылдаса оларды эквивалентті формулалар деп атайды.
Анықтама. Егер F1(x1,x2,…,xn) және F2 (x1,x2,…,xn) формулаларының ақиқаттық
кестелері бірдей болса бұл формулалар эквивалентті деп аталады және «~,, »
белгілерінің бірімен көрсетіледі. Екі формуланың эквиваленттілігін білудің стандартты тәсілі
екеуінің ақиқаттық кестесін құрып, алынған нәтижені салыстыру болып табылады. Мысалы:
(x  y) ~(y x ) формулаларының эквиваленттігін мына ақиқаттық кестеден көруге
болады.
Алынған ақиқаттық кесте әрбір құрама бойынша салыстырылады. Эквивалент
формулалардың мынадай қасиеттері бар:

25
х у x  y x y y x
ж ж a a a a
ж a a a ж a
a ж ж ж a ж
a a a ж ж a

Тұжырымдар алгебрасының пара -пар, тепе-тең ақиқат және тепе-тең жалған
формулалары.
Егер логика алгебрасының А және В формулалары олардың құрамына енетін
қарапайым Тұжырымдарының кез келген мәндерінде бірдей мән қабылдаса, онда бұл
формулалар пара-пар деп аталады. Формулалардың пара-парлығын  белгісімен белгілейміз,
яғни
А В  А және В формулалары пара-пар.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 1 мәнді
қабылдайтын болса, онда бұл формула тепе-тең ақиқат (немесе тавтология) деп аталады.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 0 мәнді
қабылдайтын болса, онда бұл формула тепе-тең жалған (немесе қарама-қайшылық) деп
аталады.
Пара-парлық және эквиваленттік ұғымдары арасында мынадай байланыс бар: егер А
және В формулалар пара-пар болса, онда АВ формуласы – тавтология, және керісінше,
егер АВ формуласы тавтология болса, онда А және В формулалары пара-пар болады.

Негізгі тепе-теңдіктер.
Теорема 1. Келесе тепе-теңдіктер орындалады:
а bab;
a~b  (а b)( b a)  (ab)( ab)  (ab)  (ab)
Осы тепе-теңдіктердің кез-келгенін ақиқаттық кестесі көмегімен дәлелдеуге болады.
Келтірілген тепе-тең көрінетіндей,  және ~ амалдары ,  арқылы ¬ өрнектеледі.
Кейінірек ,  және  арқылы тұжырымдар алгебрасының кез-келген амалын өрнектеуге
болатыны көрсетіледі. Оларды тұжырымдар алгебрасының буль амалдары деп атайды.
Теорема 2. Тұжырымдар алгебрасының булдік амалдары үшін келесі 19 тепе-теңдік
орындалады:
0. аа – екі еселі терістеу заңы 




abba
abba
.2
.1
– коммутативтік заңдары 




сbасbа
сbасbа
)()( .4
)()( .3
– ассоциативтік заңдары 




)()()( .6
)()()( .5
саbасba
саbасba
– дистрибутивтік заңдары 




ааа
ааа
.8
.7
– идемпотенттік заңдары 




baba
baba
.10
.9
– де Морган заңдары

26 










аа
аа
а
a
1 .14
0 .13
00 .12
11 .11
– 0 мен 1 заңдары 





abaa
abaa
.16
.15
– жұту заңдары 1 .17 aa
– үшінші жоққа шығару заңы 0 .18 aa
– қайшылық заңы 
Бұлардың кез-келгенін ақиқаттық кесте көмегімен дәлелдеуге болады. 

Бақылау сұрақтар:
1. Тұжырым дегеніміз не? Тұжырымның мысалдарын келтіріңіз.
2. Қандай логикалық амалдар бар? Қандай ақиқаттық кестелер арқылы анықталады?
3. Логикалық амалдар барлық жағдайларда бір -бірімен мағынасы бойынша
байланысады ма?
4. Берілген логикалық амалдардың қайсысы бинарлық болады?
5. Тұжырымдар алгебрасының формулалары дегеніміз не?
6. Тұжырымдар алгебрасының қандай формулалары эквивалентті деп аталады?
7. Буль алгебрасының заңдары атап шығыңыз.
8. Логикалық формулалардың негізгі заңдарының анықтамаларын айтыңыз. Мысалдар
келтіріңіз.
9. Логикалық формулалардың негізгі түрлері арасында қандай байланыс бар.
Пайдаланылған әдебиеттер:
1. Байсалов М.Ж. Дискретті математика. Оқу құралы. Алматы, 2007.
2. Жетпісов Қ. Математикалық логика және дискретті математика, Қарағанды, 2008.
3. Мутанов Г.М.,Акбердин Р.А. Теория графов. – Алматы, изд-во «Рауан», 2008.
4. Нефедова В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 2011.
5. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Изд-во МГТУ
им.Н.Э.Баумана, 2010.

Дәріс № 4. Буль алгебрасының негізгі эквивалентті қатынастары. ДҚФ, КҚФ, ЖДҚФ,
ЖКҚФ. Ақиқаттық кесте бойынша ЖКҚФ құрудың алгоритмі. Түйіндестік принципі

Дәріс түрі: Ақпараттық дәріс
Дәріс мақсаты:
1. ДҚФ, КҚФ, жетілдірілген ДҚФ, жетілдірілген КҚФ түсініктерін енгізу.
2. Тұжырымдар алгебрасы үшін қалыпты формалар мен жетілдірілген ДҚФ және КҚФ
анықтауда біліктілік пен дағдыны қалыптастыру.
Дәріс жоспары:
• Буль функцияларының канондық формалары.
• Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру.
• Ақиқаттық кесте бойынша ЖКҚФ құрудың алгоритмі. Түйіндестік принципі.
Негізгі ұғымдардың сөздігі: қарапайым конъюнкция, қарапайым дизъюнкция,
конъюнктивті қалыпты форма (КҚФ), дизъюнктивті қалыпты форма (ДҚФ), жетілдірілген
конъюнктивті қалыпты форма (ЖКҚФ), жетілдірілген дизъюнктивті қалыпты форма
(ЖДҚФ), түйіндес функция.
Студенттерде қалыптасу керек білім мен дағды: Буль функцияларының канондық
формаларымен танысу.

27
Буль функцияларының канондық формалары.
Түрлі функцияларды белгілі бір ереже бойынша жазуды функциялардың
канондық формасы деп атайды. Буль функциясын канондық түрде жазудың
екі формасы бар: қалыпты форма және жетілдірілген қалыпты форма.
А(а1, а2, …, аn) n тұжырымның формуласын қарастырайық.
Анықтама. n тұжырымның қарапайым конъюнкциясы (қарапайым дизъюнкциясы)
деп тұжырымдардың немесе олардың терістеулерінің конъюнкциясын (дизъюнкциясын)
айтады.
Мысал 1. xyz, xy – қарапайым конъюнкция;
xyz, yz, xz –қарапайым дизъюнкция.
Анықтама. Егер А формуладағы қарапайым дизъюнкциялар бір-бірімен
конъюнкцияның көмегімен байланысқан болса, онда формуланы конъюнктивті қалыпты
форма (КҚФ) деп атаймыз.
Анықтама. Егер А формуладағы қарапайым конъюнкциялар бір -бірімен
дизъюнкцияның көмегімен байланысқан болса, онда формуланы дизъюнктивті қалыпты
форма (ДҚФ) деп атаймыз.
Тұжырымдар алгебрасының кез келген формуласы үшін тепе-тең түрлендірулер көмегімен
оның ДҚФ немесе КҚФ алуға болады, бұл формалар жалғыз болмайды.
Анықтама. Егер дизъюнктивті қалыпты формадағы қарапайым конъюнкцияның
құрамына әрбір қарапайым Тұжырымның өзі немесе кері шамасы міндетті түрде енетін
болса, формуланы жетілдірілген дизъюнктивті қалыпты форма (ЖДҚФ) деп атаймыз.
Анықтама. Егер конъюнктивті қалыпты формадағы қарапайым дизъюнкцияның
құрамына әрбір қарапайым Тұжырымның өзі немесе кері шамасы міндетті түрде енетін
болса, формуланы жетілдірілген конъюнктивті қалыпты форма (ЖКҚФ) деп атаймыз.
Мысал 2. А(x,y,z)= xyzxy – дизъюнктивті қалыпты форма;
B(x,y,z)= (xyz)( yz)( xz) – конъюнктивті қалыпты форма;
C(x,y,z)= xyzxyz – жетілдірілген дизъюнктивті қалыпты форма;
D(x,y,z)= (xyz)( xyz)( xyz) – жетілдірілген конъюнктивті қалыпты форма.
Теорема 1. Тұжырымдар алгебрасының кез келген формуласының оған пара-пар ДҚФ
және КҚФ бар.
Теорема 2. Тұжырымдар алгебрасының кез келген тепе -тең жалған емес
формуласының бірмәнді ЖДҚФ түрінде өрнектелуі бар.
Теорема 3. Тұжырымдар алгебрасының кез келген тепе -тең ақиқат емес
формуласының бірмәнді ЖКҚФ түрінде өрнектелуі бар.
Мысал 3.  zzxух ~ формуласы берілген. Формуланың дизъюнктивті және
конъюктивті формаларын табу керек.
► ДҚФ түземіз:       zzxухzzxухzzxух ~
    zzухzxухzzxухzzxух   .00 zyzxzzxzyzxzzxyx 

КҚФ түземіз:    .~ zyxzyzxzzxух 

Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру.
Есеп. А(x,y,z) формуласының ақиқаттық кестесі берілсін.

х у z А(x,y,z)
а а а а
а а ж ж
а ж а ж

28
ж а а а
а ж ж а
ж а ж ж
ж ж а ж
ж ж ж ж

Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген формула
қарпайым тұжырымдардың 1, 4, 5 жолдардағы үлестірулерінде ақиқат мән қабылдайды.
Конъюнкцияның ақиқаттық кестесін пайдаланып, осы жолдардан қарапайым конъюнкция
құрайық.
Бірінші жолдағы мәндерде xyz ақиқат,
Төртінші жолдағы мәндерде xyz ақиқат,
Бесінші жолдағы мәндерде xyz ақиқат.
Енді, осы қарапайым конъюнкциялардан жетілдірілген қалыпты дизъюнктивті форма
құрайық:
хyz  xyz  xyz.
Бұл формуланың ақиқаттық кестесінің А(x,y,z) формуласының ақиқаттық кестесімен
сәйкес келетіндігін тексеру қиын емес. Себебі, басқа жолдардағы қарапайым
тұжырымдардың мәндерінің үлестірулерінде жоғарыдағы қарапайым конъюнкциялардың
әрқайсысы жалған мән қабылдайды.
А(x,y,z)= хyz  xyz  xyz.
Демек, тепе-тең жалған емес формуланы жетілдірілген қалыпты дизъюнктивті
формаға келтіру үшін оның ақиқаттық кестесіндегі ақиқат мәндерге сәйкес келетін
жолдардан қарапайым конъюнкциялар құру қажет. Бұл қарапайым конъюнкцияларда, егер
қарапайым тұжырым ақиқат мән қабылдаса, онда оның өзін, ал жалған мән қабылдаса, онда
оның кері шамасын аламыз. ЖКҚФ құру алгоритмін келтірейік.
Тепе-тең ақиқат емес формуланы жетілдірілген қалыпты конъюнктивті формаға
келтіру үшін оның ақиқаттық кестесіндегі жалған мәндерге сәйкес келетін жолдардан
қарапайым дизъюнкциялар құру қажет. Бұл қарапайым дизъюнкцияларда, егер қарапайым
Тұжырым ақиқат мән қабылдаса, онда оның кері шамасын, ал жалған мән қабылдаса, онда
оның өзін аламыз.
Мәселен, жоғарыда қарастырылған формуланың ЖКҚФ келесі түрде болады:
А(x,y,z)= (хyz) (xyz)(xyz) (xyz) (xyz).

Ақиқаттық кесте бойынша ЖКҚФ құрудың алгоритмі. Түйіндестік принципі.
Тұжырымдар логикасының әрбір формуласына ақиқат кесте құруға болатынын
білеміз. Керісінше қалай? Керісінше де яғни ақиқат кесте бойынша формула құруға
болатынын көреміз.

29
2. Осы құрамаларға сәйкес конъюнкция жазамыз. Егер хі аргументінің құрамадағы
мәні 1-ге тең болса ол конъюнкцияға өзгеріссіз енеді, ал хі=0, болса конъюнкцияға оның
терістеуі алынады.
3. Алынған барлық конъюнкциялардың дизъюнкциясы іздеген формула болады және
ол құрылған функцияның ЖДҚФ-ы болады.
Мысалы, f (x1 ,x2,x3 )=1
V (3,4,6), f (x1 ,x2,x3 )=V
1 (0,2,5,7)
3,4,6-құрамалардың нөмірлері 0,2,5,7- құрамалардың нөмірлері
,
Ақиқаттық кесте бойынша ЖКҚФ құрудың алгоритмі.
Алгоритмді f (x1 ,x2,x3 ) =V
0 (0,3,7) функциясына ЖКҚФ құруға қолданайық.
1. Кестеден функцияны 0-ге айналдыратын аргументтерге сәйкес құрамалар
алынады(асты сызылады).
2. Осы құрамаларға сәйкес дизъюнкция жазамыз. Егер хі аргументінің құрамадағы
мәні 0-ге тең болса ол конъюнкцияға өзгеріссіз енеді, ал хі=1, болса конъюнкцияға оның
терістеуі алынады.
3. Алынған барлық дизъюнкциялар конъюнкциямен жалғастырылады. 321321321( xxxxxxxxxF 




Анықтама. Егер f
*
(x1,x2,…,xn)=),...(1 nxxf онда f*(x1,x2,…,xn) функциясы
f(x1,x2,…,xn) функциясына түйіндес функция деп аталады. f(x1,x2,…,xn) функциясына
түйіндес функцияны анықтау үшін, барлық айнымалылар және функцияның өзін оның
қарама-қарсы мәндеріне ауыстыру керек.
Мысал. Үш айнымалыдан тәуелді )&)(()~(),,(
23121321
xxxxxxxxf 

функциясын буль формуласы яғни ЖДҚФ-түрінде өрнектеу керек.

30


Іздеп отырған МДҚФ
),,(
321
xxxf
= 321321321321321 ххххххххххххххх 

Түйіндестік принципі: Егер f функциясын өрнектейтін F формуласындағы барлық
операция белгілерін түйіндес функцияның операция белгілеріне алмастырғаннан алынған F*
формуласы берілген f функциясының түйіндес функциясын өрнектейтін болады.
Тек , , а, ж символдарымен ғана байланысқан формулаларды қарастырамыз. , ,
а, ж символдары бір біріне түйіндес деп аталады.
Мысалдар: ақиқат–формуласының түйіндесі - жалған;



Егер f1, f2 функциялары тең болса, онда оларға сәйкес түйіндес формулалар да тең
болады. 21ff онда *
2
*
1ff . Түйіндестік принцип дизъюнкция, конъюнкция, терістеу
арқылы байланысқан формулалармен берілген функциялардың түйіндестерін табу үшін
ыңғайлы. Бұл жағдайда берілген формулада конъюнкция дизъюнкцияға, дизюнкция
конъюнкцияға ауысады. Сөйтіп ДҚФ–КҚФ, КҚФ-ДҚФ, ЖДҚФ–ЖКҚФ немесе керісінше.
Мысалы: ()()()()
*
zyxzxyxzyxxzxy 
Егер  формуласы -ге эквивалент болса: онда оларға сәйкес түйіндес
формулалар да эквивалентті болады ,яғни *

* болады.
Егер f*

(x1,x2,…,xn)=f(x1,x2,…,xn) онда f(x1,x2,…,xn) функциясы өзіне-өзі түйіндес
функция деп аталады. Мысалы,  xyxzyz функциясы өзіне өзі түйіндес функцияны
кескіндейді. Оған (б1,б2,б3) және (1-б1, 1-б2 , 1-б3) жиынтықтарының қарама-қарсы
мәндерінде функция да қарама-қарсы мән қабылдайтындығына көз жеткізуге болады. Ол
үшін ақиқаттық кесте құрып: