Urganch davlat universiteti fizika-matematika fakulteti matematika yo’nalishi 182-guruh talabasi holbayeva malikaning

2.4. MILI VA MUR AVTOMATLARI

Chekli avtomat modeli. Avtomat ishining kanonik tenglamasi. Initsial va noinitsial avtomatlar. Mili va Mur avtomatlari va ular orasidagi munosabatlar.

Chekli xotirali diskret qurilmalar chekli avtomat modeli bo’ladi. Bu avtomatning ta kirishi, ta chiqishi va chekli ichki holati mavjud.

CHekli avtomat diskret vaqt momentlarida ishlaydi. Agar momentdagi kirishning, chiqishning va holatining qiymatlarini mos ravishda (t), va bilan belgilasak, u holda avtomatning ishi quyidagi kanonik tenglama bilan ifodalanadi:

,, ,

, (1)

(1) tenglamalardagi va funksiyalar mos ravishda - chiqishning funksiyasi va o’tishlar funksiyasi deb aytiladi. Avtomatning ish jarayonini aniqlash uchun uning boshlang’ich holatini ko’rsatish kerak.

Agar va 1-momentdagi kirish qiymatlari ma’lum bo’lsa, u holda (1) kanonik tenglamadan foydalanib 1-momentdagi chiqish va

holatning qiymatini, va asosida 2-momentdagi chiqish va holatlarini aniqlash mumkin va h.k. Ikki turdagi avtomatlar mavjud: - initsial va initsialmas (noinitsial). Initsial avtomatlarda boshlang’ich holat tayinlangan (mahkamlangan) bo’ladi. Noinitsial avtomatlarda boshlang’ich holat sifatida istalgan holatni olish mumkin.

Ixtiyoriy sondagi kirish va chiqishga ega bo’lgan avtomat ishini aniqlash masalasi 1 ta kirish va 1 ta chiqishga ega bo’lgan avtomatning ishini aniqlash masalasiga keltiriladi. SHuning uchun asosiy model sifatida 1 ta kirishga va 1 ta chiqishga ega bo’lgan avtomatlarni ko’ramiz. Bunday avtomatlar quyidagi kanonik tenglama bilan ifodalanadi:

, .

Bunday turdagi avtomatga Mili avtomati deb aytiladi.

Mili avtomati chekli xotirali diskret qurilmaning yagona modeli emas. Ikkinchi model - Mur avtomati mavjud. Mur avtomatida chiqish qiymati o’sha momentning o’zidayoq ichki holatning qiymati bilan aniqlanadi. Mur avtomatining kanonik tenglamasi quyidagi ko’rinishda bo’ladi

, .

Agar birinchi tenglamadan ikkinchisiga qiymatini qo’ysak va deb belgilasak, u holda ikkinchi tenglama quyidagi ko’rinishga keladi

, .

Demak, Mur avtomatini Mili avtomatining xususiy holi deb qarash mumkin. Bu yerda o’tish funksiyasi maxsus ko’rinishda bo’ladi. Xuddi shunday, Mili avtomatini ham (ayrim ma’noda) Mur avtomatiga keltirish mumkin.

Demak, har qanday initsial va noinitsial Mili avtomatlari uchun ularga ekvivalent bo’lgan initsial va noinitsial Mur avtomatlari mavjud (Isboti A.A.SHolomovning “Osnov teorii diskretnix logicheskix i vchislitelnix ustroystv” kitobida mavjud).

3. 
   XULOSA
   

Kurs ishi tayyorlashda Matematik mantiqning muhim bo’limlaridan birini tashkil etuvchi mulohazalar algebrasini texnikaga (matematik kibernetikaga) tatbiq etilishini to’g’risida. Ushbu kurs ishida rele-kontaktli sxemalar, kontaktli sxemalar va ularning sintezi, funktsional elementlar va ulardan sxemalar yasash, ko’ptaktli sxemalar, funktsional 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 funktsiyalarini sxemalar(avtomatlar) orqali realizatsiya etish masalasiga alohida ahamiyat berilgan. Mulohazalar algebrasi va m ulohazalar hisobida formulaning tavtalogiya bo’lishi yoki bo‘lmasligini aniqlashning samarali usullaridan biri chinlik jadvalidir. Ammo predikatlar mantiqida bu holat batamom o’zgaradi. Predikatlar mantiqida ixtiyoriy formulaning umumqiymatli yoki umum qiymatli emasligi haqidagi masalani yechadigan samarali usul mavjud emas. Shuning uchun ham predikat va u bilan bog‘liq kvantor tushunchalaridan foydalanadigan matematik nazariyalarda aksiomatik usullardan foydalanish zarur bo‘lib qoladi. Berilgan aksiomalar sistemasi negizida qurilgan aksiomatik nazariya deb shu aksiomalar sistemasiga tayanib isbotlanuvchi hamma teoremalar majmuasiga aytiladi. Aksiomatik nazariya formal va formalmas nazariyalarga bo‘linadi. Mantiq jarayonini turli matematik belgilar bilan ifodalashga intilish Aksiomatik mantiqiy sistema bo’lib, mulohazalar algebrasi esa uning interpretasiyasidir (talqinidir). Berilgan aksiomalar sistemasi negizida (bazasida) qurilgan aksiomatik nazariya deb shu aksiomalar sistemasiga tayanib isbotlanuvchi hamma teoremalar majmuasiga aytiladi.

4. 
   FOYDALANGAN ADABIYOTLAR
   

1. 
   H.T. To’rayev, I. Azizov Matematik mantiq va diskret matematika. 1,2 jild. ―Tafakkur-Bo’stoni, Toshkent, 2011y.
   
2. 
   Qasimov N.X., Dadajonov R.N., Ibragimov F.N. Diskret Matematika va matematik mantiq asoslari (o’quv qo’llanma), T., O’zbekiston Milliy universiteti, 2016.
   
3. 
   To’xtasinov M., Diskret matematika va matematik mantik.- T., Universitet, 2005.
   
4. 
   To’rayev X.T., Matematik mantiq va diskret matematika.- T., O’qituvchi, 2003.
   
5. 
   Yunusov A.S. Matematik mantiq va algoritmlar nazariyasi elementlari, T., 2003.
   

INTERNET RESURSLAR:
1. www.ziyo-net.uz

2. http://dimacs.rutgers.edu/

3. http://epubs.siam.org/sam-bin/dbq/toclist/SIDMA

4. http://www.vsppub.com/journals/jn-DisMatApp.html

5. http://www.uni-bonn.de/logic/world.html

6. http://www.math.uni-bonn.de/people/logic/

7. http://www.math.uu.se/logik/logic-server/