Chirchiq davlat pedagogika instituti

O‘ZBEKISTON RESPUBLIKASI

OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI


CHIRCHIQ DAVLAT PEDAGOGIKA INSTITUTI

“TASDIQLAYMAN” TVCHDPI rektori G‘.I.Muxamedov _______________ 2020 yil “___”___________

“KELISHILDI” Oliy va o‘rta maxsus ta’lim vazirligi ______________________ 2020 yil “_____”__________

Ro‘yxatga olindi: № BD-_______________ 2020 yil “___”____

MATEMATIK MANTIQ VA ALGORITMLAR

NAZARIYASI FANINING
FAN DASTURI

Bilim sohasi:	100000 - Gumanitar soha
Ta’lim sohasi:	110000 - Pedagogika
Ta’lim yo‘nalishi:	5110100 - Matematika va informatika

CHIRCHIQ - 2020

Fan/modul kodi IT 1165		O‘quv yili 2020-2021	Semestr 2	ECTS - Kreditlar 5
Fan/modul turi Majburiy		Ta’lim tili O‘zbek/rus		Haftadagi dars soatlari 4
1.	Fanning nomi		Auditoriya mashg‘ulotlari (soat)	Mustaqil ta’lim (soat)	Jami yuklama (soat)
	Matematik mantiq va algoritmlar nazariyasi		60	90	150
2.	I. Fanning mazmuni "Matematik mantiq va algoritmlar nazariyasi" fani o‘qitishdan maqsad, talabalarni matematik mantiqning fundamental asoslari bilan bir qatorda algoritmlarning murakkabligi va ularni ishlab chiqish usullarini baholashning zamonaviy usullari bilan tanishtirishdir. Kurs, talabalarda matematik mantiqning turli masalalari echimlarini mustaqil ravishda tahlil qilish ko‘nikmalarini rivojlantirishga alohida e’tibor beradi. Fanning vazifasi - asosiy mantiqiy hisoblashlar, algoritmlar nazariyasining asoslarini va hisoblashlarning murakkabligini, modellar nazariyasining asoslarini o‘rganishdir. Kursni o‘zlashtirgandan so‘ng talaba, matematik mantiq va algoritmlar nazariyasining asosiy tushunchalari va usullarini tezda o‘zlashtirishi, hal qilinadigan nazariyalarning aksiomatizatsiyasini tuza olishi kerak II. Asosiy nazariy qism (ma’ruza mashg‘ulotlari) II.I. Fan tarkibiga quyidagi mavzular kiradi: Kirish. Zamonaviy ta’lim tizimida matematik mantiq va algoritmlar nazariyasi fanining o‘rni. To‘plamlar nazariyasi. To‘plamlar va ular ustida amallar. Munosabatlar. Binar munosabatlar. Maxsus binar munosabatlar.Ekvivalentlik munosabati. Tartiblangan to‘plamlar. Mulohazalar algebrasi. Mantiqiy bog‘lovchilar. Formula, qism formula. Formulalarning teng kuchliligi. Chinlilik jadvali. Qo‘shma formulalar. Muloxazalar algebrasi formulasining normal shakllari. Mukammal diz’yunktiv va konyunktiv normal formalar. Bul funksiyalari. Ularning berilish usullari. Bul funksiyalari soni. Elementar bul funksiyalari. Formula tushunchasi. Funksiyalarni formulalar ko‘rinishda ifodalash. Formulalarning ekvivalentligi. Ikkilamchi funksiyalar. Ikkilamchilik prinsipi. Bul funksiyalarining o‘zgaruvchilar bo‘yicha yoyilmasi. Jegalkin ko‘pxadi. Funksiyalar sistemasining to‘liqligi va yopiqligi. Muxim yopiq sinflar. Post teoremasi va uning natijalari. Aksiomatik nazariya. Hisob tushunchasi. Mulohazalar xisobi. Keltirib chiqarish. Isbot tushunchasi. Teorema tushunchasi. Mulohazalar hisobining aksiomalari. Deduksiya teoremasi. Mos keltirib chiqarish xaqida lemma. To‘liqlik xaqida Gyodel teoremasi. Mulohazalar hisobining ziddiyatli emasligi. Mulohazalar hisobining to‘liqligi. Predikatlar mantiqi. Predikat (mantiqiy funksiya) tushunchasi. Predmetlar sohasi. O‘zgarmas predmetlar va o‘zgaruvchi muloxazalar. Elementar formulalar. Kvantorlar. Predikatlar mantiqining alfaviti. Formula ta’rifi. Teng kuchli formulalar. Asosiy teng kuchli formulalar. Bajariluvchi formulalar. Aynan chin formula. Aynan yolgon formula. Algoritmlar nazariyasi. Algoritmlar. Algoritmlar murakkabligi. Sonli funksiyalar. Hisoblanuvchi funksiyalar. Tyuring mashinasi. Primitiv rekursiv funksiyalar. Minimizatsiya operatori. Qisman rekursiv va rekursiv funksiyalar. Chyorch-Tyuring tezisi. Rekursiv to‘plam. Rekursiv sanaluvchi to‘plam. Post teoremasi. Rekursiv sanaluvchi to‘plamlar xaqida asosiy teorema. Rekursiv sanaluvchi to‘plamlar panjarasi. III. Amaliy mashg‘ulotlari buyicha ko‘rsatma va tavsiyalar To‘plamlar nazariyasi.To‘plamlar va ular ustida amallar. Munosabatlar. Binar munosabatlar. Maxsus binar munosabatlar. Tartiblangan to‘plamlar. Muloxazalar algebrasi.Muloxazalar va ular ustida amallar. Muloxazalar va muloxazali shakllar. Muloxoza inkori. Kon’yunksiya va diz’yunksiya. Mantiqiy amallar. Implikatsiya, ekvivalensiya, modul ikki buyicha yig‘indi, Sheffer shtrixi, Pirs strelkasi. Rostlik jadvali. Muloxazalar rostligi kiymatini aniqlash. Murakkab muloxazalarni qurish. Muloxazalar algebrasining normal formalari. Mantiq formulalarini minimal dizyunktiv normal formagacha(MDNF) soddalashtirish Bul funksiyalari. Ularning berilish usullari. Bul funksiyalari soni. Elementar bul funksiyalari. Formula tushunchasi. Funksiyalarni formulalar ko‘rinishda ifodalash. Formulalarning ekvivalentligi. Jegalkin ko‘pxadi. Funksiyalar sistemasining to‘liqligi va yopiqligi. Muxim yopiq sinflar. Post teoremasi va uning natijalari. Aksiomatik nazariya. Mulohazalar hisobi. Keltib chiqarish. Isbot tushunchasi. Mulohazalar hisobining aksiomalari. Predikatlar mantiqi. Predikat tushunchasi. Kvantorlar. Predikatlar algebrasi. Elementar formulalar. Formula ta’rifi. Teng kuchli formulalar. Bajariluvchi formulalar. Sonli funksiyalar. Hisoblanuvchi funksiyalar. Primitiv rekursiv funksiyalar. Minimizatsiya operatori. Qisman rekursiv va rekursiv funksiyalar. Algoritmlar nazariyasi. Sonli funksiyalar. Hisoblanuvchi funksiyalar. Primitiv rekursiv funksiyalar. Minimizatsiya operatori. Qisman rekursiv va rekursiv funksiyalar. Tyuring mashinasi. Rekursiv va sanaluvchi tuplamlar. Amaliy mashg‘ulotlar multimedia qurulmalari bilan jihozlangan auditoriyada bir akademik guruhga bir professor-o‘qituvchi tomonidan o‘tkazilishi zarur. Mashg‘ulotlar faol va interfaktiv usullar yordamida o‘tilishi, mos ravishda munosib pedagogik va axborot texnologiyalar qo‘llanilishi maqsadga muvofiq. III. Mustaqil ta’lim va mustaqil ishlar Mustaqil ta’limning mazmuni talabalar tomonidan - leksiya va amaliy mashg‘ulotlarga tayyorgarlik; - uy vazifalarini bajarish; - nazariy bilimlarni o‘zlashtirish; - tabaqalashtirilgan yakka tartibdagi topshiriqlarni bajarish; - mustaqil ta’lim uchun mo‘ljallangan mavzularini o‘zlashtirishdan iboratdir. Mustaqil ta’lim uchun tavsiya etiladigan mavzular: Binar munosabatlar ustida amallar. Qisman tartiblangan to‘plamlar. Formula, qism formula.
3.	IV Fan o‘qitilishining natijalari (shakllanadigan kompetensiyalar) Fanni o‘zlashtirish natijasida talaba: Matematik mantiq va algoritmlar nazariyasi fani bo‘yicha talaba matematik isbotlar va nazariyani; komponentalar(aksioma va keltirib chiqarish qoidalari)va mulohazalarning hisoblash xususiyatlari(xossalari) va birinchi tartibli nazariyani; qism rekursiv funksiya tushunchasi, Tyuring mashinasini o‘rganish uchun matematik mantiqning metodi va koidalari,matematik mantiqning asosiy prinsiplari, to‘plamlar va algoritmlar nazariyasi, mulohazalar algebrasi formulasi haqida, algebraik almashtirishlar minimizatsiyalash metodlari haqida tasavvurga ega bo‘lishi; Mulohazalar mantiqi tilining chinlik formulalarni anglash;Tyuring mashinasini qurish, primitiv rekursiv va qism rekursiv funksiyani isbotlash ko‘nikmalariga ega bo‘lishi kerak; Formulalarning tengkuchli almashtirishva ayniy chin formulalarni anglash, mantiqiy xarakterdagi masalalarni ifoda qila olish va matematik mantiq vositalari yerdamida ularni yecha olish, malakasiga ega bo‘lishi kerak.
4.	V. Ta’lim texnologiyalari va metodlari: ma’ruzalar; interfaol keys-stadilar; seminarlar (mantiqiy fiklash, tezkor savol-javoblar); guruhlarda ishlash; taqdimotlarni qilish; individual loyihalar; jamoa bo‘lib ishlash va himoya qilish uchun loyihalar.
5.	VI. Kreditlarni olish uchun talablar: Fanga oid nazariy va uslubiy tushunchalarni to‘la o‘zlashtirish, tahlil natijalarini to‘g‘ri aks ettira olish, o‘rganilayotgan jarayonlar haqida mustaqil mushohada yuritish va joriy, oraliq nazorat shakllarida berilgan vazifa va topshiriqlarni bajarish, yakuniy nazorat bo‘yicha yozma ishni topshirish.
6.	Asosiy adabiyotlar Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012 Mendelson E. Vvedenie v matematicheskuyu logiku. M.: Nauka, 1984 Yablonskiy S. V. Vvedenie v diskretnuyu matematiku. – M.: Nauka, 1986. Qo‘shimcha adabiyotlar Mirziyoev Sh.M. Buyuk kelajagimizni mard va olijanob xalqimiz bilan birga quramiz. – Toshkent: “O‘zbekiston”, 2017. – 488 b. N.Kh.Kasymov, R.N.Dadajanov,F.N.Ibragimov. Diskret matematika va matematik mantiq asoslari. O’quv qollanma. Toshkent 2018. To‘raev X.T., Matematik mantik vadiskret matematika.- T., O‘qituvchi,2003. Yershov Yu. L., Palyutin Ye. A. Matematicheskaya logika. M.: Nauka, 1987. Klini S. K. Matematicheskaya logika. M.: Mir, 1973 Partee B., terMeulen A., Wall R. Mathematical Methods in Linguistics. Dordrecht: Reidel, 1989. Axborot manbaalari http://dimacs.rutgers.edu/ http://epubs.siam.org/sam-bin/dbq/toclist/SIDMA http://www.vsppub.com/journals/jn-DisMatApp.html
7.	Fan dasturi O‘zbekiston Respublikasi Oliy va o‘rta maxsus ta’lim vazirligining Oliy, o‘rta maxsus va professional ta’lim yo‘nalishlari bo‘yicha o‘quv-uslubiy birlashmalar faoliyatini Muvofiqlashtiruvchi Kengashning 2020 yil “___”_________ dagi ____ -sonli bayonnomasi bilan ma’qullangan. O‘zbekiston Respublikasi Oliy va o‘rta maxsus ta’lim vazirligining 2020 yil “___” _____dagi ______ - sonli buyrug‘i bilan ma’qullangan fan dasturlarini tayanch oliy ta’lim muassasasi tomonidan tasdiqlashga rozilik berilgan.
8.	Fan/modul uchun mas’ullar: D.G’.Axmedjanov − Chirchiq davlat pedagogika instituti aniq fanlar fakulteti Informatika kafedrasi mudiri, texnika fanlari doktori N. V. Juraeva - Chirchiq davlat pedagogika instituti aniq fanlar fakulteti Informatika kafedrasi dotsent v.b, texnika fanlari nomzodi
9.	Taqrizchilar: M.S. Yakubov – TATU, Axborot texnologiyalari kafedrasi professori, texnika fanlari doktori B.Sh.Radjabov – TVCHDPI, Matematika kafedrasi professori, texnika fanlari doktori