Mantiqiy inkor - Kombinatsion turdagi funksional qurilmalar. Koderlar, shifratorlar va deshifratorlarni vizual muhitlarda...

|
Kombinatsion turdagi funksional qurilmalar. Koderlar, shifratorlar va deshifratorlarni vizual muhitlarda loyihalash
|
bet | 4/10 | Sana | 19.12.2023 | Hajmi | 3,11 Mb. | | #123920 |
Bog'liq Kombinatsion turdagi funksional qurilmalar. Koderlar, shifratorlar va deshifratorlarni vizual muhitlarda loyihalashMantiqiy inkor (inversiya, EMAS amali), mos o‘zgaruvchi ustiga «–»belgi qo‘yish bilan amalga oshiriladi;
Mantiqiy qo‘shish (diz’yunktsiya, YOKI amali), «+» belgi qo‘yish bilanamalga oshiriladi;
Mantiqiy ko‘paytirish(kon’yunktsiya, HAM amali), «·» belgi qo‘yishbilan amalga oshiriladi.
Ifodalar ekvivalentligini ifodalash uchun «=» belgisi qo‘yiladi.
Mantiqiy funktsiyalar va amallar turli ifodalanish shakllariga ega bo‘lishlari mumkin: algebraik, jadval, so‘z bilan va shartli grafik (sxemalarda). Mantiqiy funktsiyalarni berish uchun mumkin bo‘lgan argumentlar majmuidan talab qilinayotgan mantiqiy funktsiya qiymatini berish yetarli. Funktsiya qiymatlarini ifodalovchi jadval haqiqiylik jadvali deb ataladi. Ikki o‘zgaruvchi uchun to‘liq mantiqiy funktsiyalar majmui keltirilgan.
Mantiqiy amallarni ko‘rib chiqish uchun jadvalda keltirilgan aksioma va qonunlar qatoridan foydalanamiz.
|
|
|
|
0+x=x
|
|
|
|
0·x=0
|
|
|
|
1+x=x
|
|
|
Aksiomalar
|
1·x=x
|
|
|
x+x=x
|
|
|
|
|
x·x=x
|
|
|
|
|
x+
|
x
|
=1
|
|
|
|
|
|
|
|
|
x·
|
x
|
=0
|
|
|
|
|
|
|
|
|
|
= x
|
|
|
|
|
|
|
|
|
х
|
|
Kommutativlik qonunlari
|
x1+ x2= x2+ x1
|
|
|
|
x1· x2= x2· x1
|
|
|
Assotsiativlik qonunlari
|
x1+ x2+ x3= x1+ (x2+ x3)
|
|
|
|
x1· x2· x3= x1· (x2· x3)
|
|
|
Distributlik qonunlari
|
x1· (x2+ x3) = (x1· x2) + (x1· x3)
|
|
|
|
x1+ (x2· x3) = (x1+ x2) · (x1+ x3)
|
|
Duallik qonunlari
|
________
|
|
|
|
|
|
|
x1 x2
|
x1
|
x
|
|
|
|
(de - Morgan teoremasi)
|
2
|
|
________
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 x2
|
x1
|
x
|
2
|
|
|
Yutilish qonunlari
|
x1+ x1· x2= x1
|
|
|
|
|
x1· (x1+ x2) = x1
|
|
|
Raqamli sxemalarda turli mantiqiy funktsiyalarni amalga oshirish uchun minimal element bazis (yoki baza) deb ataluvchi mantiqiy elementlarmajmuasiga ega bo‘lish yetarli hisoblanadi.
Minimal element bazislar:
Biri HAM, ikkinchisi esa – EMAS amalini bajaruvchi ikki turdagi mantiqiy elementlar majmui;
Biri YOKI, ikkinchisi esa – EMAS amalini bajaruvchi ikki turdagi mantiqiy elementlar majmui;
YOKI-EMAS (EMAS-YOKI) amalini bajaruvchi Pirs mantiqiy elementlari majmui;
HAM-EMAS amalini bajaruvchi Sheffer mantiqiy elementlari majmui.
1-rasm
YOKI-EMAS elementi asosida HAM (a), YOKI (b) va EMAS (v) mantiqiy amallarini shakllaniishi.
2 -rasm
VA-EMAS elementi asosida VA (a), YOKI (b) va EMAS (v) mantiqiy amallarini shakllaniishi.
Amalda elementlar va boshqalar nomenklaturasini qisqartirish maqsadida HAM-EMAS yoki YOKI-EMAS amallarni bajaruvchi element bazasidan foydalaniladi. Lekin, faqat minimal bazis elementlaridan foydalangan holda raqamli tizimni shakllantirish qurilmaning murakkablashib ketishiga olib keladi.
U holda tizim parametrlarini yaxshilash maqsadida, HAM-EMAS yoki YOKI-EMAS minimal bazis elementlaridan tashqari, HAM-YOKI-EMAS, HAM, YOKI, istisnoli YOKI va boshqa amallarni bajaruvchi sxemalar ham qo‘llaniladi.
Minimal element bazisi mantiqiy elementlarning funktsional to‘liq tizimi hisoblanadi.Ya’ni, minimal bazis mantiqiy elementlari majmui ixtiyoriy murakkablikdagi mantiqiy sxemani shakllantirishga imkon beradi.
Misol tariqasida, YOKI-EMAS elementi yordamida (1-rasm) va faqat HAM-EMAS elementlari yordamida (2-rasm) HAM, YOKI va EMAS amallari qanday bajarilishini ko‘rib chiqamiz.
Murakkab mantiqiy qurilmalar sintezini boshlashdan avval, quyidagi amallar ketma-ketligini bajarish zarur:
- mazkur tugun (blok) bajarishi kerak bo‘lgan berilgan murakkab mantiqiy funktsiyani minimallash;
- element baza tanlash;
- minimallashgan mantiqiy funktsiyani tanlangan bazaga ko‘ra o‘zgartirish;
- elektr sxemani sintezlash.
O‘zgaruvchi kattaliklar orasidagi u=f(x) bog‘liqlik yoki funktsiya turli shaklda ifodalanishi mumkin.
Raqamli qurilmalarning ishlash algoritmi matematik mantiq yordamida ifodalanadi.Shu sababli qurilmalar mantiqiy qurilmalar sinfiga ta’lluqli.Mantiqiy qurilmalarda chiqishdagi o‘zgaruvchilar (funktsiya) ui ning kirishdagi o‘zgaruvchilar majmuasi xn-1…x2x1 orqali, mantiq algebrasi yordamida ifodalanishi mantiq algebrasi funktsiyasi (MAF) deb ataladi. Raqamli qurilmalarda qayta ulanuvchi elementlar (“ochiq” xolatidan “berk” holatiga o‘tuvchi va aksincha) qo‘llanilgani sababli mantiq algebra funktsiyasini yana qayta ulanuvchi funktsiya deb ham atashadi.
1.1. Mantiqiy funksiyalarning karno kartalari
Kombinatsion sxemalarda chiqishdagi signal mazkur vaqtda kirishga berilayotgan mantiqiy signallar kombinatsiyasiga aynan mos keladi. Shu sababli, bu turdagi sxemalarga xotira zarur emas.
Bul algebrasi yordamida mantiqiy sxemalarni tuzishda zarur sodda sxemalar sonini minimallash mumkin.Lekin, bul algebrasini yaxshi bilgan holdagina bunday natijalarga erishi mumkin. Optimallash (minimallash)ning boshqa grafik usuli - Karno kartalar ini qo‘llashga asoslangan bo‘lib, bu usul algebraik usuldan ancha sodda hisoblanadi. Kirishlar soni to‘rtdan ortiq bo‘lmagan sxemalarni Karno kartalari yordamida minimallash eng yaxshi usul hisoblanadi. Bu usul mantiqiy ifodalarni haqiqiylik jadvallari yordamida aniqlashga ham imkon beradi.
Karno kartalarini qo‘llash materialni ixcham va qulay ifolanishini ta’minlaydi. Karno kartalari haqiqiylik jadvaliga yaqin bo‘lib, ikkita o‘q bo‘ylab joylashgan o‘zgaruvchilardan tashkil topadi. O‘zgaruvchilar shunday joylashishi kerakki, har bir kvadrantdan keyingisiga o‘tganda, faqat bir kirishning holati o‘zgarsin. Ikkita (3.1 a-rasm), uchta (3.1 b-rasm), va to‘rtta (3.1 v-rasm), mantiqiy o‘zgaruvchili funktsiyalar uchun Karno kartalari keltirilgan. Ikkita o‘zgaruvchi uchun 22=4 kobinatsiya hosil bo‘ladi, shuning uchun karta 4 katakdan tashkil topadi. Uchta o‘zgaruvchi uchun 23=8 kombinatsiya hosil bo‘ladi, shuning uchun karta
8 katakdan takshil topadi va h.z.
Kartalardan ko‘rinib turibdiki, har bir katakga mantiqiy o‘zgaruvchilar majmui yozilgan bo‘lib, katak raqami ustun va qatorlar kesishmasidan aniqlanadi. Shu sababli haqiqiylik jadvali yordamida berilgan funktsiyalarni Karno kartalari orqali ifodalash qulay.Ba’zi mantiqiy funktsiyalarni Karno kartalari yordamida grafik ifodalash 3.2-rasmda keltirilgan.
O‘zgaruvchilar soni K=8÷9 gacha bo‘lgan funktsiyalarni ifodalashga imkon beradigan maxsus usullar mavjud. Lekin Karno kartalari har doim ham yaxshi minimallashga olib kelmaydi.
b) v)
3.1-rasm
Ikkita (a), uchta (b) va to‘rtta (v) o‘zgaruvchili funktsiyalar uchun mintermlari joylashgan Karno kartalari.
b)
У=х1 х2х1х2х3х2 х3
у х1 х2 х1х2 у х1 х2 х1х2х3 х2 х3
v )
у х1 х2 х3 х4 х1х2 х3 х4 х1 х2 х3
///////3.2-rasm.
Karno kartalari yordamida mantiqiy funktsiyalarni
grafik ifodalash namunalari.
O‘zgaruvchilar soni beshtadan ortiq bo‘lmagan MAFni minimallashda Veych kartalarini qo‘llash usulidan foydalanish mumkin. O‘zgaruvchilar soni to‘rtta bo‘lgan MAF uchun Veych kartalari (diagrammalari) hamda karta kvadratlarining raqamlanishi 3.3. a - rasmda keltirilgan.
MAFning o‘zi (3.1) funktsiya yordamida ifodalaniladi
у(х1 , х2 , х3 , х4 ) х1х 2 х1х2 х3 х4 х1 х2 х3 х1х3 х1х3 х4
/ a b
qoidaga asosan to‘rrta o‘zgaruvchili MAF uchun Veych kartalari (a) va kataklarning to‘ldirilishi (b): agar o‘zgaruvchilarning i-kiritilishda funktsiyaning qiymati birga teng bo‘lsa, u holda kartaning mos katagiga 1 yoziladi (b).
Darhaqiqiat, MAFni Veych kartalari yordamida minimallashda uning faqat birga teng bo‘lgan qiymatlarini emas, balki nol qiymatlarini ham qo‘llash mumkin. Ikkala holatda ham o‘zaro teng ifodalar hosil bo‘ladi, lekin qo‘shiluvchilar soni va bajaradigan mantiqiy amallari soni bilan farqlanishi mumkin.
Veych kartalari yordamida MAFni minimallash usulida mantiqiy o‘zgaruvchilarning soni beshtadan oshmasligi kerak. Agar bu shart bajarilmasa, ya’ni o‘zgaruvchilar soni beshtadan oshsa, usul o‘z kuchini yo‘qotadi, agar ishlab chiqaruvchi malakaga yoga bo‘lmasa MAFni minimallashda EHMlarni qo‘llay olmaydi.
|
| |