O`zbekiston respublikasi oliy va o`rta maxsus ta’lim vazirligi urganch davlat universiteti diskret matematika va matematik mantiq

14-Mavzu. Tyuring mashinasi. Chyorch-Tyuring tezisi. Algoritmik yechimga 
ega bo’lmagan muammolar. 
15-Mavzu. Norekursiv sanaluvchi to’plamlar. To’xtash muammosi. 
Algoritmik yechilmas muammolar. Norekursiv sanaluvchi to’plamlar. To’xtash 
muammosi. Algoritmik yechilmas muammolar. Solishtirilmaydigan sanaluvchi 
Tyuring darajalari. Algoritmik murakkablik, vaqt va xotira, P=NP muammosi. NP-

---

6 
to’la va Np-qiyin masalalar.. 
III. Amaliy mashg`ulotlari bo`yicha ko`rsatma va tavsiyalar 
Amaliy 
mashg`ulotlardan 
maqsad 
ma’ruza materiallari bo`yicha 
talabalarning bilim va ko`nikmalarini chuqurlashtirish va kengaytirishdan iborat. 
Bunda talabalar amaliy mashg`ulotlarda misol va masalalarni yechishda, 
yechimlarni tahlil qilishda olgan nazariy bilimlarini qo`llay olishlari nazarda 
tutiladi. 
Amaliy mashg`ulotlar uchun quyidagi mavzular tavsiya etiladi: 
1. To‘plamlar va ular ustida amallar. Munosabatlar. Binar munosabatlar. 
Funksiya, algoritm. Ekvivalentlik va qisman tartiblar. Ordinal va kordinallar. 
Kantor teoremasi. Transfinit induksiya. Maksimum prinsipi. Filtrlar, 
ultrafiltrlar. 
2. Mantiqiy bog‘lovchilar. Chinlilik jadvali. Formula, qism formula. Bul 
funksiyalari. Ekvivalent formulalar va tavtologiyalar. 
3. DNF, KNF, MDNF, MKNF. Mukammal dizyunktiv va konyunktiv normal 
formalar. Jegalkin ko’phadi. 
4. Elementar Bul funktsiyalari. Bul funktsiyalarining o‘zgaruvchilar bo‘yicha 
yoyilmasi. Ikkilamchi funksiyalar. Ikkilamchilik printsipi. Matematik mantiqni 
texnikaga tatbiqi. Rele-kontakt sxemalar. 
5. Funktsiyalar sistemasining to‘liqligi va yopiqligi. Post teoremasi va uning 
natijalari. Muxim yopiq sinflar. 
6. Mulohazalar xisobi. Keltirib chiqarish qoidalariga oid misollar yechish. Isbot 
tushunchasi. Teorema tushunchasi. Isbotlanuvchi formulalarga doir misollar 
yechish. Mulohazalar hisobining aksiomalari. Deduksiya teoremasi. 
7. Hosilaviy keltirib chiqarish qoidalari. Formulalar majmuasidan formula 
keltirib chiqarish. To’liqlik haqida teoremalar. Gyodelning to’liqlik teoremasi. 
8. Predikatlar algebrasi va uning formulalari. Predikat tushunchasi. O‘zgarmas 
predmetlar va o‘zgaruvchi muloxazalar. Elementar formulalar. Kvantorlar. 
Formula ta’rifi. Teng kuchli formulalar. Bajariluvchi formulalar. 
9. Umumqiymatli formulalar. Formulaning normal shakli. Yopiq formula. 
10. Formulaning normal shakli. Yopiq formula. Predikatlar xisobining aksiomalari 
sistemasi. Umumiylik va mavjudlik kvantorlarini kiritish qoidasi.
11. Kombinatorika asoslari. ”Kaptar uyasi” prinspi. O’rin almashtirishlar va 
kombinatsiyalar. Rekurrent munosabatlar. Kiritish chiqarish formulasi. 
12. Rekurrent munosabatlar. Kiritish chiqarish formulasi. 
13. Graflar ularning tiplari, insidentlik matritsasi, marshrutlar, sikl, zanjir, Eyler 
va Gamilton graflari.
14. Daraxtlar,ularni tatbiqlari. Daraxtlarda yurish. Graflarni bo’yash, xromatik 

---

7 
son, kodlashtirish. Tayanch daraxtlar. 
15. 
Algoritm tushunchasi. Sonli funktsiyalar. Hisoblanuvchi funktsiyalar. Tyuring 
mashinasi. Primitiv rekursiv funktsiyalar. Algoritmik murakkablik, vaqt va 
xotira, P=NP muammosi. Np-to’la va Np-qiyin masalalar.
Amaliy mashg`ulotlar multimediya qurulmalari bilan jihozlangan auditoriyada 
bir akademik guruhga bir o`qituvchi tomonidan o`tkazilishi lozim. Mashg`ulotlar 
faol va interaktiv usullar yordamida o`tilishi, mos ravishda munosib pedagogik va 
axborot texnologiyalar qo`llanishi maqsadga muvofiq. 
Izoh: Ishchi dasturni shakllantirish jarayonida mazkur mashg`ulot turiga 
ishchi o`quv rejada ajratilgan soat xajmiga mos mavzular tanlab o`qitish tavsiya 
etiladi.