Mavzu: Chekli avtomatlar. Mur va Mili avtomatlari

1- ta’rif. Har bir qutbdan bir marta o‘tgan zanjir muhim (jiddiy) zanjir deb ataladi.
Ya’ni, sxemaning kirishi va chiqishiga bittadan kontakt va zanjirning qolgan qutblariga ikkitadan kontakt to‘g‘ri keladigan zanjir muhim zanjirdir.
Har bir sxemada chekli sondagi muhim zanjirlar mavjud bo‘lishini ko‘rsatish mumkin. Bundan tashqari, muhim zanjirlarga mos keluvchi kon’yunksiyalarning diz’yunksiyasi sxemaning o‘tkazuvchanlik funksiyasiga teng kuchli ekanligini ham isbot qilish mumkin. Bularga asosan, sxemaga qarab uning o‘tkazuvchanlik funksiyasini yozsa bo‘ladi.
Bundan keyin bo‘yalmagan doiracha bilan sxemaning kirishi va qora rangli doiracha bilan sxemaning chiqishi belgilaymiz.
3- misol. 10- shaklda berilgan sxemalarning o‘tkazuvchanlik funksiyalarini topaylik.

a) ,
b) ,

d)
formulalar mos ravishda 10- shaklning a), b) va d) qismlarida tasvirlangan sxemalarning o‘tkazuvchanlik funksiyalari bo‘lishini ko‘rsatish qiyin emas. ■
Endi teskari masalani ko‘raylik, ya’ni berilgan funksiyaga qarab uni realizatsiya qiladigan sxemani yasash masalasini ko‘ramiz. Buning uchun funksiyani DNSh ko‘rinishiga keltiramiz. DNSh ifodasidagi har bir elementar kon’yunksiyaga mos ravishda bitta ketma-ket ulangan kontaktlarni mos qo‘yamiz (9- shakl). Bundan keyin hamma kirishlarni va chiqishlarni mos ravishda aynan tutashtiramiz. Hosil qilingan sxema DNSh ko‘rinishidagi funksiyani realizatsiya qiladi.
4- misol. Berilgan a) , b) , d) funksiyalarni kontakt sxemalar orqali realizatsiya qilaylik. Buning uchun berilgan funksiyalarni DNSh ko‘rinishiga keltiramiz:
a) (11-a shakl);
b)
(11-b shakl);
d) (11-d shakl). ■

Biz yuqorida DNSh ko‘rinishdagi funksiyani kontakt sxema orqali realizatsiya qilishni ko‘rdik. Tabiiyki, KNSh ko‘rinishdagi funksiyani ham kontakt sxema orqali realizatsiya qilish mumkin. Buning uchun, birinchi navbatda, har bir elementar diz’yunksiyalarni realizatsiya qiladigan sxemalar tuzamiz (12- shakl). Ikkinchi navbatda, elementar diz’yunksiyalarga mos kelgan sxemalardan bittasining chiqishini ikkinchisining kirishiga, ikkinchisining chiqishini uchinchisining kirishiga va hokazo ulab chiqamiz (13- shakl). Birinchisining kirishi kontaktli sxemaning kirishi va oxirgisining chiqishi sxemaning chiqishi bo‘ladi. Hosil qilingan sxema KNSh ko‘rinishdagi funksiyani realizatsiya qiladi.

5- misol. Yuqorida keltirilgan algoritmdan foydalanib, a) , b) va d) funksiyalarni kontaktli sxemalar orqali realizatsiya qilish kerak bo‘lsin.
a) funksiyani KNSh ko‘rinishga keltiramiz va uni soddalashtirish uchun tanish bo‘lgan ushbu
, ,
, ,
,
teng kuchli formulalardan foydalanamiz:
(14-a shakl),
b)
(14-b shakl),
d)
(14-d shakl). ■
Parallel-ketma-ket ulash natijasida hosil qilingan sxemalar klassini induktiv tarzda ifodalaylik.