Vii-bob. Matematik mantiqning texnikaga tatbiqi

VII-BOB. MATEMATIK MANTIQNING TEXNIKAGA TATBIQI

Matematik mantiqning muhim bo’limlaridan birini tashkil etuvchi mulohazalar algebrasini texnikaga (matematik kibernetikaga) tatbiq etilishini ko’rishga o’tamiz.

Ushbu bobda 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.

1-§. Funktsional elementlar va ulardan sxemalar yasash

Qandaydir qurilma berilgan bo’lsin, uning ichki tarkibi bizni qiziqtirmaydi. Qurilmaning n ta tartiblangan (masalan, 1 dan n gacha rakamlangan) “kirishi” va bitta “chiqishi” bo’lsin (1-shakl).

1 2 3 ............ n-1 n

1-shakl.

Qurilmaning har bir kirishiga ikki xil signal berish mumkin (tok bor yoki tok yo’q). Bu signallarni biz mos ravishda 1 yoki 0 bilan belgilaymiz. Qurilma kirishlariga berilgan har bir signallar majmuasi uchun uning chiqishida bitta signal paydo bo’ladi (1 yoki 0). CHiqishdagi signalning qiymati kirishlarga berilgan signallar majmuasiga bog’liq bo’ladi. SHunday aniqlangan qurilmaga biz funktsional element deb aytamiz. Ma’lumki, har bir funktsional elementga mantiq algebrasining bitta funktsiyasi to’g’ri keladi, bu holda har bir funktsional element mantiq algebrasining bitta funktsiyasini realizatsiya etadi deb aytamiz. Buning uchun kirishning har bir nomeriga o’zgaruvchini mos qilib qo’yamiz. U vaqtda o’zgaruvchilarning har bir qiymatlar majmuasiga funktsiyaning 0 yoki 1 ga teng qiymati mos keladi.

Agar bizda funktsional elementlar mavjud bo’lsa, u holda ulardan yangi murakkab funktsional elementlarni quyidagicha yasash mumkin.

1. Birorta funktsional elementning kirishini ikkinchi bir funktsional elementning chiqishi bilan tutashtirish natijasida murakkab funktsional element hosil qilish mumkin (2-shakl).

₃

₂

2-shakl.

Hosil etilgan qurilmani yangi funktsional element deb qabul qilish mumkin. Bu funktsional elementning chiqishi elementning chiqishidan, kirishlari esa, va elementlarning ozod bo’lgan kirishlaridan iborat bo’ladi. Agar yangi hosil bo’lgan qurilmaning kirishlariga signallar majmuasini yuborsak, u vaqtda elementning ozod kirishlariga signallar bir vaqtda yetib boradi, qolganiga bo’lsa, elementning chiqishidagi signal tushadi.

2. Biror funktsional elementning ikki va undan ortiq kirishlarini aynan tutashtirish natijasida yangi murakkab funktsional element hosil qilish mumkin (3-shakl).

₁

3-shakl.

Bu funktsional elementning chiqishi elementning chiqishidan iborat, kirishlari bo’lsa, tutashtirilmagan kirishlardan va aynan tutashtirilgan kirishlarga mos keladigan bitta kirishdan iborat bo’ladi.

3. Uchinchi usul birinchi va ikkinchi usullarning kombinatsiyasidan iborat. Masalan, birorta elementning biror kirishiga elementning chiqishi, ikkinchi biror kirishiga elementning chiqishi ulanadi va ayrim kirishlari aynan tenglashtiriladi va hokazo (4-shakl).



₁ ₂

4-shakl.

Hosil bo’lgan yangi murakkab funktsional elementga birinchi va ikkinchi usullarni qo’llab, yana yangi murakkab funktsional elementga ega bo’lamiz. SHu protsessni cheksiz davom ettirishimiz mumkin.

Agar funktsional elementlar mos ravishda funktsiyalarni realizatsiya etsa, u vaqtda hosil bo’lgan yangi murakkab funktsional element realizatsiya etadigan funktsiya funktsiyalarning superpozitsiyasidan iborat bo’ladi.

Haqiqatan ham, agar biror funktsiyani realizatsiya qiladigan elementning kirishiga funktsiyani realizatsiya qiladigan elementning chiqishi ulangan bo’lsa, u vaqtda funktsiyaning o’sha kirishiga mos bo’lgan argumenti o’rniga funktsiyani keltirib qo’yishimiz kerak. Hamma aynan tutashtirilgan kirishlar o’rniga ularga mos kelgan faqat bitta argument qo’yish kerak, shuning uchun 2-shaklga asosan, funktsional element realizatsiya qiladigan funktsiyaning argumenti o’rniga funktsional element realizatsiya qiladigan funktsiyani keltirib qo’yish kerak. Natijada, funktsiyani realizatsiya qiladigan murakkab funktsional elementga ega bo’lamiz, funktsiyasi bo’lsa, ta’rifga asosan, va funktsiyalar superpozitsiyasi mahsulidir. 3-shakldagi funktsional element funktsiyani, 4-shakldagi funktsional element esa

funktsiyani realizatsiya qiladi. Demak, funktsiya va funktsiyalar, funktsiya funktsiya va funktsiya esa funktsiyalarning superpozitsiyasidir.

Birinchi va ikkinchi usullarni qo’llash natijasida hosil etilgan qurilmalar - sxemalar (to’g’ri sxemalar) deb aytiladi.

Endi sxemaning induktsiya metodi bo’yicha ta’rifini beraylik.

1-ta’rif. a) Har qanday funktsional element sxema bo’ladi. Uning kirishi funktsional elementning kirishidan, chiqishi bo’lsa - uning chiqishidan iborat bo’ladi.

b) Agar sxema va uning ikkita kirishi aynan tutashtirilgan bo’lsa, u holda hosil bo’lgan qurilma ham sxema bo’ladi. ning chiqishi ning chiqishidan va ning kirishlari bo’lsa, ning tutashtirilmagan kirishlaridan va aynan tutashtirilgan ikkita kirishga mos kelgan kirishdan iborat bo’ladi.

v) Agar va sxemalar bo’lsa, u holda sxemaning birorta kirishiga sxemaning chiqishini ulash natijasida hosil bo’lgan qurilma ham sxema bo’ladi. sxemaning chiqishi sxemaning chiqishidan va uning kirishlari ning hamma kirishlaridan hamda ning chiqishi bilan tutashtirilgan ning kirishidan tashqari ozod qolgan hamma kirishlaridan iboratdir.

g) b) va v) punktlarda tasvirlangan usullar orqali chekli qadamda har qanday sxemani funktsional elementlardan yasash mumkin.

Bu ta’rif oldingi paragraflarda funktsiyalar superpozitsiyasi haqida berilgan ta’rifdan forma jihatdan birmuncha farq qiladi. Bu farq birinchi navbatda sxemaning rangi (funktsional elementlardan sxema yasash uchun bajarilgan qadamlar soniga sxemaning rangi deb aytiladi) degan tushunchani kiritmaganimiz tufayli paydo bo’ldi. Ikkala ta’rifni taqqoslab tahlil etishni o’quvchiga havola etamiz.

Endi sxema realizatsiya etadigan mantiq algebrasining funktsiyasini induktsiya metodi orqali topaylik.

1.Induktsiya asosi. Har bir funktsional element bitta mantiq algebrasining funktsiyasini realizatsiya etishi aniqlangan.

2.Induktiv o’tish. a) Agar sxema funktsiyani realizatsiya etsa, u holda 1-ta’rifning b) punkti asosida qurilgan sxema aynan tutashtirilgan kirishlarga mos keladigan argumentlarni aynan tenglashtirish natijasida hosil etilgan funktsiyani realizatsiya etadi.

b) funktsiyani sxema va ni sxema realizatsiya qilsinlar, bu yerda lar bir-biriga teng bo’lmagan o’zgaruvchilar bo’lsin. U vaqtda 1-ta’rifning v) punktiga asosan qurilgan sxema , , ni realizatsiya etadi. Bu yerda funktsiya funktsiyaning argumenti o’rniga qo’yilgan.

Tengkuchli funktsiyalarni bir xil funktsional element realizatsiya etadi deb qabul qilamiz. Buning uchun soxta kirish degan tushunchani kiritamiz.

2-ta’rif. Agar funktsional element realizatsiya qiladigan funktsiyaning qiymati argumentga mos kelgan kirish signalining qiymati (0 yoki 1)ga bog’liq bo’lmasa (ya’ni ning soxta argumenti bo’lsa, u holda elementning argumentga mos kirishi soxta kirish deb ataladi.

3-ta’rif. Faqatgina kirishlarning raqamlanish tartibi va soxta kirishlari bilan farq qiladigan funktsional elementlar ekvivalent funktsional elementlar deb aytiladi.

Demak, funktsional elementni o’zgartirmasdan istalgancha soxta kirishlarni olib tashlash yoki qo’yish mumkin.

funktsional elementlar sistemasi va funktsional elementlar mos ravishda realizatsiya etadigan funktsiyalar sistemasi bo’lsin. sistema qanday shartlarni qanoatlantirganda, mantiq algebrasining istalgan funktsiyasini uning funktsional elementlari yasalgan sxema orqali realizatsiya etish mumkinligi masalasini ko’raylik.