Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Algoritmlash va matematik modellashtirish kafedrasi Diskret tuzilmalar fani Oqituvchi: Mamadaliyev Xusniddin Abdijalilovich

Reja 1. Diskretlik tushunchasi 2. Diskret tuzilmalarga misollar 1-Maruza. Kirish. Diskret tuzilmalar, ularga misollar

Matematika moddiy olamni abstrakt tarzda aks ettiradi, ammo bu matematika haqiqiy olamdan ajralib qolgan, degan gap emas. Matematikaning taraqqiyoti, uning nazariy fizika, kvant mexanikasi, axborot texnologiyalari va boshqa fanlarga samarali tatbiqi matematikada yangi yonalishlar paydo bolishi va takomillashishiga olib kelayapti. Xususan, diskret matematika ham ana shunday yonalishlardan biri bolib tabiat yoki biror obektda kechayotgan jarayonni organishda vaqtning yoki obektning malum bir diskret nuqtalaridagi xolatidan tahlil qilish maqulligidan kelib chiqqan.

Diskret sozining matematikadagi manosi ajralgan sifatida olinsa haqiqatga mos keladi. Fikrimizni izohi sifatida bir misolni olamiz. Natural sonlar to`plamida 3 sonining chapdan qoshnisi 2, ongdan qoshnisi 4 ekanini va bu sonlar orasida boshqa butun son yoq ekanligini bilamiz. Shuningdek, boshqa turdagi to`plamlarda ham to`plam elementlarini nomerlash mumkin bolsa, masalan kochadagi uylar nomeri, guruh jurnalidagi talabaning tartib nomeridan bu to`plamlar ham diskret xarakterga ega ekanligini koramiz.

Fikrimiz toliq bolishi uchun diskret bolmagan to`plamga misol keltiramiz. Masalan (0,1) oraliqdagi haqiqiy sonlar to`plamini oladigan bolsak va undagi 0,5 sonini olsak, uning shu to`plamga taalluqli chapdan yoki ongdan yon qoshnisini korsating desa buning iloji yoq. Xususan, 0.49; 0.499; ;... sonlari 0.5 dan chap tarafda, lekin yon qoshnisi degan savolga javob yoq. Chunki soni uchun qanday sonini olmaylik ular orasida hech bolmaganda bitta soni mavjud ekanligini korsatish mumkin.

Demak (0;1) dagi haqiqiy sonlar to`plami diskret bola olmas ekan. Biz ushbu kursda asosan diskret to`plamlar bilan shugullanamiz. Nazariy jihatdan bizni orab turgan olam olchamlari yuqoridan ham, quyidan ham cheklanmagan desakda, amaliy jihatdan imorat gishtlardan, ximiyaviy elementlar atomlardan tuzilganligini bilamiz. Shuning uchun ham deb uzluksiz modelga otish doimo ham samarali bolavermas ekan. Masalan, axborot texnologiyalarida raqamli tizimga otish bunga yorqin dalil boladi.

Hech kimga sir emas, hozir barcha axborotlar u kitob boladimi, kino filim boladimi, qoshiq boladimi, yoki kimnidur dil sozlari boladimi barchasi raqamlashtirilib, biror fleshkagami yoki kompyuter xotirasiga yozib qoyiiladi. Kerak paytda uni ekran orqali korishimiz va eshitishimiz mumkin. Bunda kompyuter, telefon, televizor tarkibiga kiruvchi signal protsessori efirdan kelayotgan analogli signallarni raqamli korinishdan yana tabiiy signal korinishga qaytaradi va biz ovozni eshitamiz, tasvirni koramiz.

Buni multfilimlarni yaratishdagi ananaviy usulda korishimiz mumkin. Multiplikator – rassomlar chizgan minglab rasmlar ketma – ketligi ekranda malum tezlikda otkazilganda real vaqtda kechayotgan jarayon gavdalanadi, ovozlar eshitiladi. Aslida esa bu diskret vaqtlar paytiga mos keluvchi tasvirlar ketma – ketigidan iborat edi. Bu xolat songi yillarda multfilmlarni ham rassomlar emas, kompyuter yordamida dasturiy asosida yaratish imkoniyatini beradi.

Shunday qilib diskret matematika yonalishi paydo boldi va uning bir tarmogi diskret tuzilmalar (strukturalar) elementlariga extiyoj kelib chiqdi. Biz bu yerda vaqtincha real obekt va jarayondan chetlashgan holda asosiy tushunchalar va ularning tariflarida to`xtalamiz. Agar malum bir to`plam elementlari uchun amal va bu amal xossalari kiritilgan bolsa uni matematik tuzilma deymiz. Agar to`plam elementlari diskret xarakterga ega bolsa diskret tuzilma deymiz. Biz bu yerda to`plam sifatida malum bir belgiga nisbatan ajratilgan elementlar jamlanmasini tushunamiz.

to`plam elementlari turli – tuman sifatlarga, nafaqat matematik xususiyatlariga ega bolishi mumkin. Masalan natural sonlar to`plami guruhdagi talabalar to`plami, xirmondagi tarvuzlar to`plami, alifbodagi harflar to`plamini korishimiz mumkin. to`plam elementlari orasida binar munosabat (amal) kiritilgan bolib u boysinadigan shartlar (aksiomalar) berilgan bolsin. U holda to`plamda tuzilma aniqlangan deymiz. Kiritilgan amal va uning xossalari asosida tuzilmaning aksiomatik nazariyasini yaratish mumkin.

Matematik tuzilmalar (strukturalar) ni asosan uchta turga bolish mumkin: algebraik tuzilmalar, tartib tuzilmalari, topologik tuzilmalar. Algebraik tuzilmalar to`plam elementlari uchun har qanday ikki elementga mos keluvchi uchinchi elementni bir qiymatli aniqlash usuli berilsa buni kompozitsiya qonuni deyiladi. Kompozitsiya qonuni aniqlangan tuzilma algebraik tuzilma deyiladi.

Ortiqcha izohlarsiz algebraik strukturalarga misollar keltiramiz. Umumiyatni saqlash uchun amal belgisi sifatida dan foydalanamiz. 1.Amal sifatida qoshish olingan natural sonlar to`plamini olaylik. Uning aksiomatik tarifi quyidagicha boladi.

Kopaytirish amaliga nisbatan natural sonlar to`plami uchun aksiomatik tarif yuqoridagidek bolishi tushunarli. 3. Natural sonlar to`plami bolish amaliga nisbatan algebraik tuzilma bola olmaydi.

5.Bir xil olchamli matritsalar to`plami ham qoshish amaliga nisbatan algebraik tuzilmaga tashkil etadi. Buni amal tarifidan korish mumkin.

Algebraik strukturaga yana bir misol sifatida Bul tuzilmasini kiritish mumkin. Bu yerda korilayotgan to`plam sifatida elementlari mantiqiy ozgaruvchilar bolgan (qiymatlari faqat chin yoki yolgon) to`plamni, amal sifatida esa qoshish va inkor amali kiritilgan bolsin. To`plamda birlik chin elementi deb w belgilangan bolsin. Bu holda Bul tuzilmasi aksiomatik nazariyasi quyidagicha beriladi.

Bu yerda inkor amali korinishda ifodalangan. Tartib tuzilmalari to`plamning ixtiyoriy ikki elementi lar uchun dan kichik, yoki ga teng munosabat berilgan bolsin. Bu munosabatni kabi belgilaylik. Munosabat aksiomalarini quyidagicha ifodalash mumkin.

Shuningdek, to`plamlar uchun qism to`plam tushunchasi korinishda ifodalansa, yani ning barcha elementlari ga ham tegishli, da undan boshqa elementlar ham bolishi mumkin bolsa ning qism to`plami deyiladi. Bu holda S amaliga nisbatan to`plam qism to`plamlari tartib tuzilmasini tashkil etadi. Haqiqatan ham aksiomalar bajarilishi korinib turibdi.

Yuqoridagi keltirilgan to`plamlar, munosabatlar, mulohazalar(fikrlar) algebrasi, to`plamlar quvvatlari va ularni aniqlash qoidalari haqida keyingi maruzalarda batafsil to`xtalamiz. Avval takidlaganimizdek biz asosan diskret to`plamlar va diskret tuzilmalar bilan ish koramiz.