Matematik mantiq va diskret matematika

O‘ZBEKISTON RESPUBLIKASI OLIY VA
O‘RTA MAXSUS TA’LIM VAZIRLIGI


H.T. To‘rayev, I. Azizov


MATEMATIK MANTIQ VA
DISKRET MATEMATIKA


Qayta ishlangan va to‘ldirilgan ikkinchi nashri


O’zbekiston Respublikasi Oliy va o’rta maxsus ta’lim vazirligi
oliy o’quv yurtlarining talabalari uchun o’quv qo’llanma sifatida tavsiya etgan

TOSHKENT – 2008

To‘rayev H.T., Azizov I. Matematik mantiq va diskret matematika. Darslik. Qayta ishlangan va to‘ldirilgan 2- nashri. Toshkent: 2007. – ____ bet.

Darslikda to‘plamlar va kombinatorika haqida umumiy tushunchalar, mulohazalar algebrasi, mulohazalar hisobi, predikatlar mantiqi, matematik nazariyalar, algoritmlar, matematik mantiqning texnikaga tatbiqi, matematik mantiq funksiyalarini minimallashtirish muammosi, graflar nazariyasining elementlari, tarmoqlar va tarmoqdagi oqimlar bayon qilinlan.

Darslik bakalavriatning 5480100 – amaliy matematika va informatika yo‘nalishi bo‘yicha ta’lim olayotgan talabalarga mo‘ljallangan.
Darslikdan bakalavriatning 5460100 – matematika, 5140100 – matematika va informatika yo‘nalishlari hamda 5A460104, 5A480101, 5A480107 va 5A480108 magistratura mutaxassisliklari bo‘yicha ta’lim olayotgan talabalar hamda aspirantlar, radiotexnika, elektrotexnika va amaliy matematika sohalarida ishlayotgan muhandislar, matematiklar va mutaxassislar foydalanishlari mumkin.
Mas’ul muharrir: dotsent A.M.Musayev

Taqrizchilar: TATU kafedrasi mudiri, O‘zR FA

akademigi M.M. Komilov,
SamDU kafedrasi mudiri,
professor A.S.Soleyev,
O’zMU dotsenti, fizika-
matematika fanlari nomzodi
R. Dodajonov.

O’zbekiston Respublikasi mustaqilligining

17 yilligiga bag’ishlanadi.


1- NASHRGA SO‘Z BOSHI

Diskret matematika – matematikaning bir qismi bo‘lib, meloddan avval IV asrda yaratila boshlangan. Diskret matematika matematikaning takomillashgan sonlar nazariyasi, algebra, matematik mantiq qismlaridan tashqari XX asr o‘rtalaridagi fan-texnika taraqqiyoti tufayli jadal rivojlanayotgan funksional sistemalar nazariyasi, graf va to‘rlar nazariyasi, kodlashtirish nazariyasi, kombinator analiz kabi bo‘limlarni ham o‘z ichiga oladi.

Dastlab faqat matematik mantiq, algebra, matematik analiz, matematika asoslari, ehtimollar nazariyasi, geometriya, topologiya, sonlar nazariyasi, modellar nazariyasi kabi matematik fanlarda tatbiq etib kelingan diskret matematika XX asrning 40- yillaridan boshlab hisoblash matematikasi, kibernetika, axborot nazariyasi, iqtisodiyot, psixologiya, matematik lingvistika, tibbiyot fanlari va diskret texnikada ham keng qo‘llanilmoqda. Diskret matematika elektr sxemalarni loyihalashda va tekshirishda, avtomatik hisoblash mashinalarini loyihalash va programmalashda, diskret avtomatlarni mantiqiy loyihalashda, EHM elementlari va qismlarini loyihalashda, har xil texnik sistemalar, qurilmalar va avtomatik mashinalarni analiz va sintez qilishda keng miqyosda tatbiq etiladi. Matematik mantiq fani elektron hisoblash mashinalarining vujudga kelishiga va uni mukammalashtirishga katta hissa qo‘shdi.
Diskret matematika matematik kibernetikaning poydevori bo‘lishi bilan birga, hozirgi zamon matematik ta’limning muhim bo‘g‘ini ham hisoblanadi.
Kitobning asosi sifatida muallif tomonidan 1973 yildan beri Samarqand davlat universiteti amaliy matematika va informatika fakulteti talabalariga uzluksiz o‘qilayotgan ma’ruzalar olingan. Uning strukturasi va mazmuniga fakultet bazasida “Diskret matematika va uning tatbiqlari” mavzusida o‘tkazilgan Xalqaro ilmiy anjumanlar, Moskva davlat universitetining «Diskret matematika» kafedrasi bilan o‘quv-uslubiy sohalardagi hamkorlik hamda fakultet talabalariga diskret matematika fanining yetuk olimlari A.Dorodnitsin, Yu.Juravlyov, M.Komilov, V.Kudryavsev, A.Zikov va V.Qobulov tomonidan o‘qilgan ma’ruzalarning ham ijobiy ta’siri bor.
Kitob diskret matematikaning rivojlanish tarixi (kirish) va 9 bobdan iborat.
Qo‘llanmaning birinchi bobida to‘plamlar nazariyasining elementlari, munosabatlar, binar munosabati, funksiyalar superpozisiyasi, tartiblash munosabati va panjara haqida tushunchalar beriladi.
Ikkinchi bobi mulohazalar algebrasiga bag‘ishlangan bo‘lib, unda mulohazalar va ular ustida mantiqiy amallar, formulalar, teng kuchli, aynan chin, aynan yolg‘on va bajariluvchi formulalar, teng kuchli formulalarga doir teoremalar, formulalarning normal shakllari, mukammal diz’yunktiv va kon’yunktiv normal shakllar, mulohazalar algebrasi funksiyalari, Bul algebrasi, mantiq algebrasidagi ikkitaraflama qonun va arifmetik amallar, Jegalkin ko‘phadi, monoton funksiyalar, funksional yopiq sinflar va Post teoremasi kabi masalalar ko‘rib chiqiladi.
Kitobning uchinchi bobi mulohazalar hisobiga bag‘ishlangan bo‘lib, unda mulohazalar hisobi formulasi tushunchasi, isbotlanuvchi formula ta’rifi, mulohazalar hisobining aksiomalar sistemasi (tizimi), keltirib chiqarish qoidalari, keltirib chiqarish qoidasining hosilalari bo‘lgan bir vaqtda o‘rniga qo‘yish, murakkab xulosa, sillogizm, kontrpozitsiya, ikki karra inkorni tushirish qoidalari, formulalar majmuasidan formulani keltirib chiqarish qoidasi, keltirib chiqarilgan formula (isbotlash) tushunchasi, deduksiya va umumlashgan deduksiya teoremalari, ayrim mantiq (asoslarni o‘rin almashtirish, asoslarni qo‘shish, asoslarni ajratish) qonunlarining isboti, mulohazalar algebrasi va mulohazalar hisobi o‘rtasidagi munosabatlar, mulohazalar hisobida yechilish, zidsizlik, to‘liqlilik va erkinlik muammolari kabi masalalar ko‘rib chiqiladi.
To‘rtinchi bobda predikatlar mantiqi bayon etilgan. Bu yerda predikat tushunchasi, predikatlar ustida mantiqiy amallar, umumiylik va mavjudlik kvantorlari, predikatlar mantiqining formulasi va uning qiymati, predikatlar mantiqining teng kuchli formulalari, predikatlar mantiqi formulasining normal shakli, bajariluvchi va umumqiymatli formulalar, yechilish muammosi, xususiy hollarda formulaning umumqiymatliligini topish algoritmlari, predikatlar mantiqining matematikaga tatbiqi, aksiomatik predikatlar hisobi haqida ma’lumotlar keltiriladi.
Kitobning beshinchi bobi matematik nazariyalarga bag‘ishlangan bo‘lib, aksiomatik nazariya tushunchasi, birinchi tartibli til, term va formulalar, mantiqiy va xos (maxsus) aksiomalar, keltirib chiqarish qoidasi, algebra, geometriya va analizda mavjud bo‘lgan matematik nazariyalar, nazariyada isbotlash tushunchasi, tavtalogiya xususiy hollarining isbotlanuvchanligi, deduksiya teoremasi, nazariya tilining interpretasiyasi (talqini), berilgan interpretasiyada formulalarning chinlik qiymatlari, nazariyaning modeli, interpretasiyaning izomorfizmligi, nazariyaning qat’iyligi, nazariyaning zidsizlik, to‘liqlilik va yechilish muammolari, predikatlar hisobining zidsizligi, natural sonlar nazariyasi, Gyodelning to‘liqsizlik haqidagi teoremasi singari masalalar yoritilgan.
Kitobning oltinchi bobida algoritmlar nazariyasining elementlari atroflicha bayon etilgan. Bu yerda algoritm tushunchasi va uning xarakterli xususiyatlari, yechiluvchi va sanaluvchi to‘plamlar, Post teoremasi, algoritm tushunchasini aniqlash, hisoblanuvchi funksiyalar, qismiy rekursiv va umumrekursiv funksiyalar, A.Chyorch va S.Klini tezislari, Tyuring mashinalari, Tyuring mashinasida algoritmni realizasiya qilish, natural sonlarni qo‘shish algoritmi, Evklid algoritmi, algoritmlar nazariyasining asosiy gipotezasi, Markovning normal algoritmlari, Markov bo‘yicha qisman hisoblanuvchi va hisoblanuvchi funksiyalar, qismiy rekursiv (umumrekursiv) funksiya bilan Markov bo‘yicha qismiy hisoblanuvchi (hisoblanuvchi) funksiya o‘rtasidagi munosabat, normallashtirish prinsipi, algoritmik yechilmovchi muammolar, matematik mantiqda keltirib chiqaruvchanlikni tanish muammosi, o‘z-o‘ziga tatbiq etuvchanlikni tanish muammosi kabi masallar ko‘rilgan.
Kitobning yettinchi bobida matematik mantiqning texnikaga tatbiqlari keltirilgan. Bu yerda rele-kontaktli sxemalar, kontaktli sxemalar va ularning sintezi, funksional elementlar va ulardan sxemalar yasash, ko‘p taktli sxemalar, funksional elementlar sistemasining to‘liqligi, sxemalarni minimallashtirish muammosi, teskari bog‘lanishi bo‘lmagan avtomatlar, chekli avtomat haqida umumiy tushunchalar, Mili va Mur avtomatlari kabi masalalar ko‘rib chiqilgan. Mantiq algebrasi funksiyalarini sxemalar (avtomatlar) orqali realizatsiya etish masalasiga alohida ahamiyat berilgan.
Sakkizinchi bobda matematik mantiq funksiyalarini minimallashtirish muammosi bayon etilgan. Bu yerda diz’yunktiv normal shakl (DNSh)ni soddalashtirish, eng qisqa DNSh, qisqartirilgan DNSh, tupikli DNSh, Kvayn DNSh va minimal DNShlarni yasash algoritmlari keltirilgan. Analitik va geometrik tarzdagi algoritmlarning ekvivalentligi ko‘rsatilgan.
To‘qqizinchi bobda graflar nazariyasining elementlari yoritilgan. Bu yerda oddiy graflar, graflarning izomorfligi, marshrutlar, zanjirlar, sikllar, bog‘liqlilik, daraxtlar, xromatik son va xromatik sinf, to‘rlar va to‘rdagi oqimlar, Ford-Falkerson teoremasi kabi masalalar qarab chiqilgan.
Nazariy masalalarni bayon etishda misollardan keng foydalanilgan, deyarli har bir paragrafning oxirida mustaqil ishlash uchun mashqlar, savol va topshiriqlar berilgan.
Kitobda yoritilgan masalalar «Matematik mantiq va diskret matematika» va «Matematik mantiq va algoritmlar nazariyasi» fanlaridan tashqari davlat ta’lim standartlarida ko‘rsatilgan «Mashinalar arifmetikasi va avtomatlar nazariyasi», «Informatika asoslari va hisoblash texnikasi», «EHM va dasturlash», «Operatsiyalarni tekshirish» kabi fanlarni o‘qitishda ham muhim ahamiyat kasb etadi.
Kitobni tayyorlashda amerikalik S.Klini va A.Chyorch, avstriyalik K.Gyodel, angliyalik A.Tyuring va E.Mendelson hamda rossiyalik A.A.Markov, A.I.Malsev, P.S.Novikov, S.V.Yablonskiy, O.B.Lupanov, V.B.Kudryavsev, V.A.Gorbatov, S.G.Gindikin, A.A.Zikov, L.Lixtarnikov va T.Sukachyova, o‘zbekistonlik R.Iskandarov, T.Yoqubov kabi matematiklar tomonidan yaratilgan monografiya, darslik, o‘quv qo‘llanma va ilmiy maqolalari va samarqandlik M.Isroilovning mulohazalar algebrasiga bag‘ishlangan qo‘lyozmasidan foydalanildi.
Oliy o‘quv yurtlari matematika fakultetlari talabalari uchun o‘zbek tilida yozilgan dastlabki kitoblar marhum ustozimiz R.I.Iskandarovning “Matematik logika elementlari” (1970) nomli darsligi va T.Yoqubovning “Matematik logika elementlari” (1983) o‘quv qo‘llanmasidir. Bu kitoblar matematik mantiq fanini o‘qitishda, tabiiyki, ijobiy rol o‘ynadi.
O‘quvchilarga tavsiya etilayotgan ushbu kitob “Matematik mantiq va diskret matematika” hamda «Matematik mantiq va algoritmlar nazariyasi» fanlari bo‘yicha Respublikamiz davlat ta’lim standartlarida ko‘rsatilgan o‘quv dasturlariga to‘liq javob beradi.
Kitob universitet va pedagogika institutlarida 5460100 – matematika, 5480100 – amaliy matematika va informatika, 5140100 – matematika va informatika, 5521900 – informatika va informasion texnologiyalar bakalavrlik yo‘nalishlari hamda 5A460104, 5A480101 va 5A480107 magistratura mutaxassisliklari bo‘yicha ta’lim olayotgan talabalarga mo‘ljallangan. Kitob kamchiliklardan xoli bo‘lmaganligi tufayli, muallif kitob haqidagi tanqidiy fikr va mulohazalarni minnatdorlik bilan qabul qiladi va oldindan o‘z tashakkurini izhor etadi.
Kitobning qo‘lyozmasi bilan mufassal tanishib, uning sifatini yaxshilash yo‘lida foydali ko‘rsatma va maslahatlar bergan taqrizchilar O‘zR FA akademigi N.Satimov, professorlar A.Soleyev, A.Po‘latov, dotsentlar R.G‘ulomov va G‘.Ergashevga, muharrirlik ishini bajargan dotsent A.Musayevga, matnini kompyuterga kiritgan va maketini tuzib nashr etishga tayyorlagan X.Yaqubova, E.O‘rinboyev va F.Murodovga o‘z minnatdorchiligimni bildiraman.