“O’zbekiston temir yo’llari” daтk toshkent temir yo’l muhandislari instituti

2 

 

 “O’zbekiston temir yo’llari”  DAТK 

 

Toshkent temir yo’l muhandislari  instituti 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

B.Еgamberdiev,  F.R.  Nuriddinov 

 

DISKRET  MATEMATIKA 

(Bakalavriatning  “telekommunikatsiya”  yo’nalishini  2-kurs  talabalari 

uchun  uslubiy  qo’llanma) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Toshkent   2013 

3 

 

 

UDK  519.854 

 

   Ushbu  uslubiy  qo’llanma  “telekommunikatsiya”  bakalavriat  yo’nalishi 

talabalariga  mo’ljallangan.  Unda  diskret  matematikaning  to’plamlar 

nazariyasining  elementlari,  kombinatorika,matematik  mantiq  elementlari 

graflar  nazariyasi  elementlari  kabi  bo’limlariga  doir  nazariy  ma’lumotlar 

va masalalar keltirilgan. 

   Uslubiy  qo’llanma  amaliy  mashg’ulotlarni  o’tkazishda  va  talabalar  uyga 

vazifayi mustaqil bajarishida foydalanishiga mo’ljallangan. 

   Uslubiy  qo’llanma  “Oliy  matematika  kafedrasi”  majlisida  ko’rib 

chiqilgan va chop etishga  tavsiya qilingan. 

 

Tuzuvchilar:  B.Еgamberdiuev  –f.-m.f.n.,  “Oliy matematika”   kafedra-  

si  dotsenti, 

F.R.Nuriddinov  -“Oliy matematika”  kafedrasi katta           

o’qituvchisi   

 

 

Taqrizchilar:   A.A.Xoliqov – t.f.d., “Elektr aloqasi va radio” kafedra-  

                        si professori, 

 

R.N. Dadajonov – f.-m.f.n.,  O’z MU  dotsenti 

 

 

 

 

 

 

 

 

 

 

 

               © Toshkent  temir yo’l muhandislari  instituti,   2013 г. 

4 

 

 

                                           Kirish 

   Diskret 

matematika 

haqiqatan 

mavjud 

narsalarning 

sonli 

xarakteristikalari bilan ishlaydi. Bu narsalar diskretb tuzilishga ega va sonli 

xarakteristikalarining  qiymati  ham  diskretdir.   

   Hozirgi  kunda    oliy  o’quv  yurti  talabalari  uchun  diskret  matematikadan 

bir  qator  mukammal  qo’llanmalar  mavjud.  Lekin  o’rtacha  matematirk 

tayyorgarlikka  ega  bo’ldan  talabalarni  diskret  matematikaning  zamonaviy   

usullari bilan tanishtiruvchi  qo’llanma zarurligi sezilif turadi.  

    Ushbu  qo’llanmaning  yozilishi  shu  muammoni  yechishga  urinishlardan 

biridir.  Qo’llanma  to’rtta  paragrafdan  iborat:1.  To’plamlar  nazariyasining 

elementlari.2.Kombinatorika.3.Matematik  mantiq  elementlari.  4.  Graflar 

nazariyasi elementlari. 

    Mavzular  quyidagicha  bayon  qiliunadi.  Avval,  odattagidek  nazariy 

ma’lumotlar  va  asosiy  teoremalar  keltirilib  muammoning  mohiyati 

tushuntiriladi.Bunda ba’zi tasdiqlarning isboti misollar yechimi bilan tahlil 

qilingan.Har  bir  bo’lim  so’ngida  mavzuni  chuqur  o’rganish  uchun 

yechilishi  tavsiya  qilinadigan  masalalar  keltirilgan.  Ulardan  har  biri  bir 

nechta    bir  xil  variantdan  iborat  .  Shu  sababli  bir  yoki  bir  nechta  variant 

yechimi  topilsa yetarli. 

 

          1-§.To’plamlar  nazariyasining  elementlari. 

       1.1.To’plamlar  nazariyasining  asosiy ta’riflari.   

To’plam  tushunchasi  matematikaninig  asosiy  tushunchalaridan  biri 

bo’lib,  unga  ta’rif  berish  ancha  murakkabdir.  Gap  shundaki,  ta’rif  berish 

boshlang’ich  tushuncha  bo’lib,  unda  tushuncha  biror  tur  ko’rinishida 

berilishi  kerak.  Lekin  “to’plam”  tushunchasi  matematika  va  matematik 

mantiqning  eng  keng  tushunchasi  bo’lib,  uni  o’zidan  keng  darajadagi 

tushuncha  bilan aniqlab bo’lmaydi.  

To’plam  deb  shunday  ob’ektlar  majmuasiga  aytiladiki,  bu  ob’ektlar: 

deyarli  har  xil,  qandaydir  faqat  ularga  tegishli  bo’lgan  xususiyatga  ega, 

ob’ektlar to’plam elementlari deb ataladi, hamda to’plam yagona bir butun 

deb tushuniladi. 

Bizni  to’plamlarning  strukturaviy  tuzilishi,  bir-biridan  farqi  va  ular 

orasida qanday matematik  va mantiqiy  amallar aniqlanganligi  qiziqtiradi. 

Birinchi  navbatda  biz  to’plam  elementlari  qanday  ob’ektlar 

majmuasidan  tuzilganligiga  e’tibor berishimiz kerak.  

a elementning  X to’plamga  tegishli ekanligini  a Х orqali belgilaymiz. 

Shuni  hisobga  olish  kerakki  a  element  va  {a}  to’plam  bir  xil  narsa 

emas.  Birinchisa  a  bilan  belgilangan  element,  ikkinchisa  faqat  bitta 

5 

 

elementli  to’plamdir.  Shuning  uchun  a  tegishli  {a}  to’plamga  –  bu to’g’ri 

muloxaza.  Shu  bilan bir qatorda {a} tegishli a – noto’g’ri muloxaza. 

Toplam  elementlari  qanday  tartibda  yozilishi  ahamiyatga  ega  emas. 

{a,b,c} va {a,c,b} bir xil to’plamlardir. 

To’plamlarning  berilish usullari: 

1.  To’plamning  barcha  elementlarini  yozish  usulida.  Odatda  chekli 

to’plamlar bunday  usulda beriladi. 

2.  Faqat  berilgan  to’plam  elementlariga  xos  xossani  ko’rsatish  bilan. 

Bunday  xossa  to’plamning  xarakteristik  xossasi  deyiladi  va berilish usulini 

shartni  qanoatlantirish  asosida  deyiladi.Bu  usul  bilan  chekli  va  cheksiz 

to’plamlarni  bewrish  mumkin.

  yozuv 

to’plam 

 

to’plamning   

 [jssaga ega bo’lgan elementlaridan  tuzilganini  bildiradi. 

Agar  biror  xossaga  ega  bo’lgan  to’plamni  bilsak,  bu  xossaga  ega 

bo’lgan  faqat  bitta  ob’ekt  bo’lishi  mumkin  yoki  bunday  ob’ekt  umuman 

bo’lmasligi mumkin.  Bunday  ob’ektlar yaqqol ko’rinib turmasligi mumkin. 

Agar  A    to’plam  xarakterli xossasi bilan berilsa va bu xossaga hech bir 

ob’ekt  ega  bo’lmasa,  u  holda  A  to’plam  to’plam  bo’sh  to’plam  deyiladi. 

Bo’sh to’plam   belgi bilan belgilanadi. 

Bo’sh  to’plam  tushunchasi  juda  muhim  tushuncha.  Bo’sh  to’plamni 

xossasiga asosan berishimiz mumkin va bu to’plam ustida bemalol amallar 

bajarishimiz mumkin.  Bo’sh to’plamni chekli to’plam deb hisoblaymiz. 

To’plamlar chekli yoki cheksiz ko’p elemenyli bo’ladi. 

Ta’rif: To’plam elementlarining  soniga to’plamning  quvvati deyiladi. 

Ta’rif:  Agar  cheksiz  to’plamning  elementlari  bilan  musbat  butun 

sonlar  o’rtasida  o’zaro  bir  qiymatli  moslik  o’rnatish  mumkin  bo’lsa? 

Bunday  to’plamga sanoqli to’plam deyiladi. 

Ta’rif:  Agar  ikkita  to’plam  bir  xil  elementlardan  tuzilgan  bo’lsa,ular 

teng  deyiladi  :

.  Ya’ni  X  ning  ixtiyoriy  elementi  Y  ga  element  va  Y 

ning  ixtiyoriy elementi  X ga element. 

               1.2.To’plamosti.  Universal  to’plam  tushunchasi. 

Ta’rif:  X  to’plam  Y  to’plamning  to’plam  osti  deyiladi,  agar  X  ning 

ixtiyoriy  elementi  Y  ga  tegishli  bo’lsa.  Bunday  ichida  yotish  X    Y  qat’iy 

emas deyiladi. 

To’plam ostilarining ba’zi bir xossalari: 

1.  Х Х – reflektivlik; 

2.  X   Y & Y Z    

   X   Z – tranzitivlik; 

3.      X bo’sh to’plam har qanday  to’plamning  to’plam ostidir. 

Agar  Y  to’plamning  X  to’plamga  tegishli  bo’lmagan  elementlari  ham 

mavjud  bo’lib,  X  to’plam  Y  ning  to’plam  osti  bo’lsa  Х У  ko’rinishida 

yoziladi va X to’plam Y ga qat’iy tegishli deyiladi. 

6 

 

Universal  to’plam. 

Ta’rif:  O’rganilayotgan  sohadagi  barcha  elementlarni  va  barcha 

to’plam  ostilarni  o’z  ichiga  olgan  to’plamga  universal  to’plam  deyiladi. 

Universal to’plamni odatda U harfi bilan belgilashadi. 

1.  Agar М  U  bo’lsa, М   U bo’ladi. 

2.  Agar  М 

  U  bo’lsa,  u  holda  Ώ(М) 

  U,  bu  yerda  Ώ(М)  –  M 

to’plamning  barcha  mumkin  bo’lgan  to’plam  ostilari,  M  to’plamning 

Buleani deyiladi. 

K’orilayotgan  to’plamlar  va  yechilayotgan  masaladan  kelib  chiqib, 

universal to’plamni mustaqil belgilashimiz mumkin. 

                        1.3.To’plamlar  ustida  amallar. 

Ta’rif:  X  va  Y  to’plamlarning  kesishmasi  X∩Y  deb,  shunday 

to’plamga  aytiladiki  u  faqat X ga ham va Y ga ham tegishli elementlardan 

tashkil topadi. Belgilanishi X∩Y. 

Ta’rif:  Аgar  to’plamlar  umumiy  elementga  ega  bo’lmasa,  ular 

kesishmaydi  deyiladi,  ya’ni  ularning  kesishmasi  bo’sh  to’plamdir 

(X∩Y= ). 

Bu  amalni  ikkitadan  ko’p  bo’lgan  to’plamlar  uchun  ham  qo’llashimiz 

mumkin.  Bunday  holda  shunday  elementlar  to’plami  haqida  gapiriladiki 

ular bir vaqtda hamma  to’plamlarga tegishli bo’lishi kerak. 

Ta’rif.  Ikki  X  va  Y  to’plamlarning  birlashmasi  (X Y) deb, X yoki Y 

ga tegishli bo’lgan elementlardan tuzilgan  to’plamga aytiladi. 

Birlashma  amalini  ikkitadan  ko’p  to’plamlar  uchun  qo’llashimiz 

mumkin.  Bunday  holda  shunday  to’plam  haqida  gapiriladiki,  uning 

elementlari kamida bitta to’plamga  tegishli bo’ladi. 

Ta’rif.  X  va  Y  to’plamlarning  ayirmasi  X\Y  deb,  shunday  to’plamga 

aytiladiki  u  faqat  X  ga  tegishli  va  Y  ga  tegishli  bo’lmagan  elementlardan 

tashkil topadi. 

Bu amal kesishma va birlashmadan farqli ravishda faqat ikkita to’plam 

uchun  aniqlangan. 

      To’plamlar  algebrasida  nol  sifatida  bo’sh  to’plam  qatnashadi. 

To’plamlar algebrasida bir sifatida qatnashuvchi to’plamni aniqlaylik. 

4. To’plam to’ldiruvchisi. 

X  to’plamning  to’ldiruvchisi 

X

  deb  U  va  X  to’plam  ayirmasi  U\X  ga 

aytiladi: U\X  =

X

. 

To’plamlar ustidagi amallar ahamiyatga  loyiq xossalarga ega. 

Teorema. Agar U universal to’plam bo’lsa va   A, B, C   U lar uchun 

quyidagi xossalar o’rinli: 

1) Kommutativlik  xossasi: А В=В А,  А В=В А 

7 

 

2) 

Assotsiativlik 

xossasi: 

А (В С)=(А В) С, 

А (В С)=(А В) С 

3) 

Distributivlik 

xossasi: 

А (В С)=(А В) (А С), 

А (В С)=(А В) (А С) 

4) Ayniyat  xossasi: А

=А, А

= ,  А U=U,  А U=А 

5) Idempotentlik  xossasi: А A=A, А A=A 

6) Yutish  xossasi: А (А В)=А, А (А В)=А 

7) Ikkilamchi  to’ldiruvchi: 

A

A

 

8) To’ldiruvchining  xossasi: А

A

=U,  А

A

=  

9) De Morgan  qonunlari: 

A

B

A

B

A

B

A

B

. 

   To’plamlar    ustidagi  amallar  geometrik  Eyler-Venn  diagrammalari  bilan 

ko’rsatilishi  mumkin,bunda  to’plamlar  tekislikdagi  aylanalar  bilan  mos 

keltiriladi,natijani esa ularning o’zaro joylashishi aniqlaydi.        

 

 

         1.4.Kortej tushunchasi.  To’plamlarning  dekart ko’paytmasi. 

Ta’rif:  Qandaydir  chekli  ob’ektlarning  tartiblangan  va  tashqi  ma’lum 

holatni anglatuvchi  termasiga tartiblangan to’plam yoki kartej deyiladi. 

Kortejga kiruvchi  ob’ektlarga komponentalar  (koordinatalar) deyiladi. 

Kortej  komponentalari  soni  uning  uzunligi  deyiladi.  To’plamdan  farqli 

ravishda  kartejda  bir  xil  komponentalar  bo’lishi  mumkin  va  ularning 

qanday  tartibda joylashishi juda muhim. 

Ta’rif:  Ikkita  bo’sh  bo’lmagan  X  va  Y  to’plamlarning  dekart 

ko’paytmasi  deb  shunday  Х×У  to’plamga  aytiladiki,  u  barcha  tartiblangan 

(x,y) juftliklardan iborat bo’ladi. 

   

 

Х×У = {(x,y) : x   X;   y   Y) 

Agar  X  va  Y  to’plamlardan  birortasi  bo’sh  bo’lsa,  u  holda  Х×У ham 

bo’sh toplam bo’ladi. 

Keltirilgan ta’rifdan ko’rinadiki 

Х×У У×Х 

  1.5.Moslik,  akslantirish,  munosabat  va funksiya  tushunchalari. 

А

н

и

м

а

н

и

е

:

А 

В 

А 

В 

 

 

 

8 

 

Ikkita  A  va  B  to’plamlarini  ko’raylik.  Bu  to’plamlarning  elementlari 

orasida  (a;  b)  juftlik  tashkil  etuvchi  moslik  o’rnatilgan  bo’lsin.  Agar  bu 

moslik  biror  usulda  berilgan  bo’lsa, to’plamlar orasida moslik o’rnatilgan 

deyiladi.  Bunday  holda  A  va  B  to’plamlarning  barcha  elementlari 

taqqoslashda qatnashishi  shart emas. 

Ta’rif: A va B to’plamlar dekart ko’paytmasi R= А×В ning har qanday 

to’plam ostiga moslik deyiladi. 

Ta’rif:  D

R

,  =  {a    A  :    b    B  (a,b)    R}  to’plamga  R  moslikning 

aniqlanish sohasi deyiladi. 

Ta’rif:  B

R

,  =  {  b    B:  (a,b)    R}  to’plamga  R  moslikning  qiymatlar 

sohasi yoki  aksi deyiladi. 

Demak,  moslikni  aniqlanish  sohasi,  qiymatlar  sohasi  va  moslik 

qonuniyati  orqali berish mumkin. 

Ta’rif:  X  ning  har  bir  elementi  uchun  Y  dan  bir  yoki  undan  ko’p 

elementi mos qo’yilsa, u holda X ni Y ga akslantirish berilgan deyiladi. 

Ta’rif: X ni Y ga bir qiymatli akslantirishga funksiya deyiladi. Ya’ni f 

shunday  akslantirishni  agar 

(х

1

,y

1

)     f  va (х

2

,y

2

)     f , х

1

 = х

2

  bo’lsa, y

1

 = y

2

  bo’ladi. 

Bunday  hollarda X va Y lar ustma-ust  tushishi  mumkin. 

Ta’rif:  Agar  akslantirishning  aniqlanish  sohasi  bilan  qiymatlar  sohasi 

ustma-ust  tushsa,  bunday  akslantirishga  munosabat  deyiladi. 

Munosabatlarning  ba’zi bir xossalari: 

1.  Refleksivligi, хГх  – rost 

2.  Antirefleksivligi, хГх  – yolg’on 

3.  Simmetrikligi,  хГу   

 уГх 

4.  Antisimmetrikligi,  хГу  va уГх 

 у=х 

5.  Simmetrik  emasligi, хГу  rost, u holda  уГх   - yolg’on 

6.  Tranzitivligi, хГу  и уГz 

 хГz. 

   Ta’rif:  Ekvivalent  munosabatlar  deb,  X  to’plamdagi  shunday  biror 

munosabatlarga  aytiladiki, ular quyidagi  shartlarni qanoatlantiradi. 

1. Х Х – refleksivlik; 

2. Х У 

 У Х – simmetriklik; 

3. Х У и У Z 

 Х Z tranzitivlik. 

   Ya’ni  ekvivalentlik  uchun  quyidagi  shartlar  o’rinli:  har  bir  element 

o’ziga  o’zi  ekvivalent,  ekvivalent  elementlar  uchun  tartib  muhim  emas, 

agar  ikkita  element  uchinchisiga  ekvivalent  bo’lsa,  u  holda  ular  o’zaro 

ekvivalentdir. 

Ta’rif:  Qat’iy  tartib  munosabati  –  bu  quyidagi  shartlarni 

qanoatlantiruvchi  X to’plamga  bo’lgan biror munosabat: 

1. Х<Х – antirefleksivlik; 

9 

 

2. Х<У и У<Х – nosimmetriklik; 

3. Х<У и У

 Х

Ta’rif:  Noqat’iy  tartib  munosabati  –  bu  quyidagi  shartlarni 

qanoatlantiruvchi  X to’plamga  bo’lgan munosabat: 

1. Х Х – refleksivlik; 

2. Х У и У Х

Х=У – antisimmetriklik; 

3. Х У и У Z 

 Х Z – tranzitivlik. 

To’plam  quvvati. 

A  va  B  to’plamlar  orasida  o’zaro  bir  qiymatli  moslik  o’rnatilgan 

deyiladi,  agar  A  to’plamning  har  bir  elementiga  B  to’plamning  faqat  bitta 

elementi  mos  qo’yilsa  va  B to’pplamning har bir elementiga A to’plamning 

faqat  bitta  elementi  mos  qo’yilsa.  Bunday  hollarda  A  va  B  to’plamlar 

izomorf  deyiladi va A B kabi belgilanadi. 

Ta’rif.    Ikkita  A  va  B  to’plamlar  ekvivalent  yoki  teng  quvvatli 

deyiladi,  agar  orasida  bir  qiymatli  moslik  o’rnatilgan  bo’lsa.  Bunday 

hollarga  A B,  yoki   

,  yoziladi  va  A  hamda  B  to’plamalar  teng 

quvvatga  ega deyiladi. 

Ta’rif.  A  to’plam  chekli  deyiladi,  agar  dastlabki  n  ta  natual  sonlar 

to’plami J

n

= 1, 2, …, n  ga ekvivalent  bo’lsa. 

Ta’rif  .  A  chekli  to’plamning  quvvati  deb  uning  elementlari  soniga  k 

ga  aytiladi va  A =k kabi belgilanadi. Bo’sh to’plam chekli deb hisoblanadi 

va uning  elementlari soni nolga tengdir, ya’ni 

=0. 

Shunday  qilib,  agar  A  to’plam  chekli,  ya’ni  A =k,  bo’lsa,  u  holda  A 

to’plam  elementlarini  1  dan  k  gacha  bo’lgan  sonlar  orqali  belgilab 

(nomerlab)  chiqishimiz  mumkin.  Bunday  belgilashning  mavjudligini 

A= a

1

, a

2

, …, a

k

 ko’rinishidagi yozuvdan  foydalaniladi. 

Chekli  bo’lmagan  to’plamlarga  cheksiz  to’plamlar  deyiladi.  Agar 

qandaydir A to’plam natural sonlar to’plami N ga teng quvvatli, ya’ni A N 

bo’lsa,  u  holda  A  to’plam  sanoqli  to’plam  deyiladi  (ba’zi  adabiyotlar 

sanoqli  cheksiz).  Sanoqli  to’plam  A  –  shunday  to’plamki  uning  barcha 

elementlarini  cheksiz  ketma-ketlik  a

1

,  a

2

,  …,  a

n

,  …,lar  bilan  nomerlab 

chiqish  mumkin  bo’lib,  har  bir  element  bitta  n  nomerga  ega  va  har  bir 

natural  son  n  A  to’plamning  faqat  bitta  elementining  nomeridir.  Sanoqli 

to’plam quvvatini 

0

  (   –  qadim  yahudiy  alifboining  birinchi xarfi, “alef” 

deb ataladi, 

0

- esa “alef – nol” deb o’qiladi). Hususiy holda  N =

0

. 

A  to’plam  sanoqsiz  deyiladi  agar  uning  quvvati  N  natural  sonlar 

quvvatidan  katta  bo’lsa.  Bunday  hollarda  A  to’plam  kontinual  quvvatli 

yoki  kontinuum  deyiladi.  Kontinuumning  quvvati 

0

2

C

  kabi  belgilanadi. 

Quyodagi  teoremani  isbotsiz qabullaymiz. 

10 

 

Teorema  Barcha  xaqiqiy  sonlar  to’plami  kontinuum  quvvatlidir,  ya’ni 

R =C. 

           1.6.Qo’shish  va ko’paytirish  teoemalari. 

Qo’shib olish (inobatga olish) va ayirib  taslash formulalari. 

Teorema (Qo’shish teoremasi) 

1

2

,

,

,

n

X

X

X

  –  lar  chekli  o’zaro  kesishmaydigan  to’plamlar  bo’lib 

,

,

1, ,

1,

i

j

X

X

i

j i

n j

n

 bo’lsin.  

U holda 

1

2

1

2

n

n

X

X

X

X

X

X

 bo’ladi. 

Teorema (Ko’paytirish teoremasi) 

1

2

,

,

,

n

X

X

X

. 

Chekli 

to’plamlar 

berilgan 

bo’lsa, 

u 

holda 

1

2

1

2

n

n

X

X

X

X X

X

 

bo’ladi, 

ya’ni 

to’plamlarning 

dekart 

ko’paytmasi  elementlarining  soni,  ularning  har  birining  elementlari  soni 

ko’paytmasiga  tengdir. 

Teorema. (Qo’shib olish va ayirib tashlash) 

Chekli 

,

1,

i

X i

m

  to’plamlar  uchun  quyidagi  qo’shib  olish  va  ayirib 

tashlash formulasi o’rinlidir: 

1

2

1

1

1

1

1

1

m

i

i

j

i

j

k

i m

i j m

i j k m

m

i

j

l

i j

l m

X

X

X

X

X

X

X

X

X

X

X

X

       . 

Xususiy  holda  ikkita  to’plam  uchun  bu  formula 

A

B

A

B

A

B

 

ko’rinishga ega. 

Uchta  to’plam uchun  qo’shib olish va ayirib tashlash frmulasi 

1

2

3

1

2

3

1

2

1

3

2

3

1

2

3

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

 

ko’rinishga ega. 

Teoremaning  nomidan  ko’rinadiki,  to’plam  ostilarning  elementlarini 

qo’shib olish yoki olib tashlash kerak bo’ladi.