2-ma’ruza: oddiy kombinatsion qurilmalarni qurish. Kombinatsion qurilmalar va ularni tasvirlash usullari. Reja

2.Mantiqiy funksiyalar

n - mantiqiy o‘zgaruvchilar (argumentlar) uchun ularning 2ⁿ kombinatsiyasi yoki ikkilik tuplami mavjuddir. To’plamlarning har biri uchun funksiyaning 0 yoki 1 qiymatlari aniqlanishi mumkin. Agar funksiya qiymatlarining hech bo‘lmasa bir tuplamda bir-birlari bilan farqlansa, bunday funksiyalar-turlidir.
n uzgaruvchilik mantiqiy funksiyalar N=2n tengdir. n=2 uchun N=16. n=3 uchun esa N=256 va undan keyin funksiyalar soni keskin o‘sib ketadi. Amaliy jihatdan 2-uzgaruvchilik 16 funksiya axamiyatiga ega, chunki har bir murrakab ifodani oddiy ifodalarning kompozitsiyasi deb karash mumkindir. 1 jadvalda n=2ga teng bo‘lgan mantiqiy funksiyalar keltirilgan bo‘lib, i-nomer o‘zgaruvchi kirishlarning x₁ va x₀ aniqlaydi.

3.Mantiqiy funksiyalarning sxemada shartli belgilanish

Mantiqiy funksiyalarni tashkil etishda ishtirok etuvchi mantiqiy element kirishlar soni Kob birlashtirish koeffitsienti deb ataladi. (tarmoklanish koeffitsienti bilan almashtirmang). Yuqorida keltirilgan sxemalarda, faqat invertorda tashqari birlashtirish koeffitsienti ikkiga teng. Sanoatda sxemalar Kob=2,3,4,8 teng qurinishda ishlab chikariladi. Sxemalarning boshqa sonli kirishlar bilan xosil kilish uchun asosiy elementlarni birlashtirish mumkin. Masalan, agarda “I” elemenligini belgilash kirishligini hosil qilish uchun, quyidagi gruhlash qonuni asosida x0*x1*x2*x3*x4=(x0*x1)*(x2*x3*x4)=(x0*x1)*x2* x3*x4 ikkita ikki kirishli va bitta 3 kirishli “I” sxema birinchi varianti uchun, yoki bitta ikki kirishli va bitta turt kirishli ikkinchi variant uchun foydalanish mumkin (1 rasm). Sonsiz kirishli “I” elementi olinib, ortiqcha kirishlarga "1",

yoki (5) yoki (7) ifodalarga asosan uzgartirish mumkin.

4. Mantiqiy funksiyalarni tasvirlash usullari

Mantiqiy qurilmalarning loyixalash asosida uning Mantiqiy funksiyasini (mf) aniklash va unga mos sxemani kurish maksadi yotadi. MF turli formalarda tasvirlanishi mumkin: 1) suz, 2) grafik, 3) jadval, 4) algebraik, 5) alyuritmik til bilan, masala VHDL va 6) sxemalar bilan. Misol uchun ikki x1 va x0 uzgaruvchini funksiyaning suz bilan tasvirlanishi kurib chikamiz, agar u=1, uzgaruvchilar bir biriga teng bulmasa u=0, agar x1=x0 bulsa. Bunday funksiyani TENGSIZLIK funksiyasi deb ataladi. Tasvirlash navbatini jadval kurinishiga utamiz (2 jadval). MF ning xamma uzgaruvchilariga boglik bulgan xolatlarni tasvirlash uning xolatlar jadval deb ataladi. Umuman aytganda jadval kurinishdan algebarik usulga utish (12) formula asosida olib berish, Mantiqiy algebraning asoslaridan biridir.

Жадвал 2


MF (SOND) mantiqiy funksiyaning barkamol dizyunktiv normal formasi (BDNF) deb atalib, mi-minteri yoki i-ikkilik to‘plamning hamma o‘zgaruvchilarning mantiqiy ko‘paytmasi bo‘lib, o‘zgaruvchi tug‘ri ko‘rinishda ifodalanadi, agar o‘zgaruvchi to‘plamda 1 teng bo‘lsa va inversiya ko‘rinishida ifodalanadi, agar o‘zgaruvchi tuplamda 0 ga teng bulsa, 12-ifodaning isboti, ajratish (yoyish) teoremasiga asoslanib, unga asosan n uzgaruvchiga teng mantiqiy funksiya xi uzgaruvchi asosida quyidagi ko‘rinishda ajratib yozish mumkin:
f(x(p-1), . . . xi, . . ., x0)= ~xi*f(x(n-1), . . . ,0, . . . x0)+xi*f(x(n-1), . . . f . . .x0)
Bu ifoda xi=0 bo‘lganda ~ 0*f (x (n-1), . . . 0, . . . x0)+0*f (x (n-1), . . .1, . . .x0) = f (x (n-1), . . . 0, . . .x0).
Xi=0 holda u teng buladi: ~ 1*f (x (n-1), . . .1, . . x0)+1*f (x(n-1), . . .1, . . .x0)=f (x (n-1), . . . 1, . . .x0)ga. Boshqacha qilib aytganda ajralish teoremasi ixtiyoriy xi uchun o‘rinlidir. Ajralish teoremasi n marta qo‘llash natijasida mantiqiy funksiya hamma o‘zgaruvchilari bo‘yicha ajralib chiqish mumkindir. Misol tariqasida ikki o‘zgaruvchiga bog‘lik bo‘lgan F=f(x1,x0) funksiyani ko‘rib chiqamiz. Bu funksiyaning x asosida ajralish quyidagi ifodani beradi:
F= ~ x1*x1*f(0,x0)+x1*f (f,x0)
Keltirilgan ifodani x0 uchun davom ettirib quyidagi ifoda xosil buladi:
F =~x1*(~x0*(f(0,0) + x0*(f(0,1)) + x1*(~x0*(f(1,0) + x0*(f(1,1)) =
~x1*~x0*f(0,0) + ~x1*x0*f(0,1) + x1*~x0*f(1,0) + x1*x0*f(1,1). (12.1)
Ifoda ikki o‘zgaruvchiga boglik bo‘lgan hamma mantiqiy funksiyasi, fakat uchta asosiy mantiqiy operatsiyalar bilan ta’svirlash imkonini beradi. F7- "ILI" va /1-"I" funksiyalarning yoyish jarayonini ko‘rib chiqamiz, buning uchun 1 jadvalning mos qatorlariga murojaat etamiz. "I" funksiya x1 va x0 larning ikkilik to‘plamlarida (00,01,10,11) qiymatlarida 0,0,0,1 qiymatlarni oladi. (12.1) ifodani yuqoridagi qiymatlari uchun yozib, quyidagilarni hosil qilamiz:
F1(x1,x2)= ~ x1*~x0*0+~x1*x0*0+x1*~x0*0+x1*x0+1=x1*x0.
Bu esa aniqlangan bilan mosdir. Shunday qilib, F7 "ILI" uchun algebarik ifodani aniqlaymiz, ular uchun ham ko‘rilgan yo‘nalishlarda 0,1,1,1 qiymatlar oladi. Bunda (12.1) ifodaga asosan,
F7 (x1,x2)=~x1*x0*0+~x1+~x0*1+~x1*x0*1+x1*x0*1
oxirgi ifodalarda x1 qavsdan tashqariga, F7=~x1*x0*1+x1*(~x0+1+x0*1) (6) aksiomaga asosan qavsdagi ifoda 1ga tengdir va F7=~x1*x0*1+x1 taqsimlanish qonunini qo‘llab, (~x1+x1)*(x0+x1)=x1+x0 aniqlaymiz.
2 - jadvalga kaytib,
Y=0*~x1*~x0+1*~x1*x0+1*x1+~x0+0x1*x0= ~x1+x0+x1*~x0= x1+x0=F6 (tengsizlik funksiyasi) topamiz.
(12) formula bilan ihtiyoriy kurinishlik murrakkab funksiyalarni uch asosiy mantiqiy funksiyalar asosida keltirish mumkindir.