O. S. Rayimjonova M. G. Tillaboyev sh. U. Ergashev


-rasm.Karno kartasi yordamida minimallashtirish


Download 3.09 Mb.
Pdf ko'rish
bet11/51
Sana21.11.2023
Hajmi3.09 Mb.
#1791839
1   ...   7   8   9   10   11   12   13   14   ...   51
Bog'liq
РАҚАМЛИ техника merged

1.3.6.1-rasm.Karno kartasi yordamida minimallashtirish 
Uchta o'zgaruvchining funktsiyasi bo'lsa, siz uch o'lchovli kub bilan 
shug'ullanishingiz kerak. Bu qiyinroq va kamroq vizual, ammo texnik jihatdan 
mumkin. Rasmda uchta o'zgaruvchining Boolean funktsiyasi uchun haqiqat jadvali 
va 
unga 
mos 
keladigan 
kub 
misol 
sifatida 
ko'rsatilgan 
1.3.6.2-rasm.Karno kartasi yordamida minimallashtirish 


32 
rasmdan ko'rinib turibdiki, uch o'lchovli holat uchun atamalarning yanada murakkab 
konfiguratsiyasi mumkin. Masalan, kubning bir yuziga tegishli to'rtta atama ikkita 
o'zgaruvchining 
yutilishi 
bilan 
bitta 
atamaga 
birlashtiriladi: 
umuman olganda, giperkubning bitta k o'lchovli yuziga tegishli bo'lgan 2K atamalar 
bitta 
atamaga 
yopishtiriladi 
va 

o'zgaruvchilar 
so'riladi. 
Ko'p sonli o'zgaruvchilarning mantiqiy funktsiyalari bilan ishlashni soddalashtirish 
uchun quyidagi qulay usul taklif qilindi. Termlarning tuzilishi bo'lgan kub rasmda 
ko'rsatilgandek tekislikka ochiladi. Shunday qilib, o'zgaruvchilar soni ikkitadan ko'p 
bo'lgan mantiqiy funktsiyalarni tekis jadval shaklida ifodalash mumkin bo'ladi. 
Shuni esda tutish kerakki, jadvaldagi term kodlarining tartibi (00 01 11 10) ikkilik 
raqamlarning tartibiga mos kelmaydi va jadvalning ekstremal ustunlarida joylashgan 
hujayralar bir-biriga qo'shni. 
1.3.6.3-rasm.Karno kartasi yordamida minimallashtirish 
Xuddi shunday, to'rt, besh yoki undan ortiq o'zgaruvchilarning funktsiyalari bilan 
ishlash mumkin. N \ u003d 4 va N \ u003d 5 uchun jadvallarga misollar rasmda


33 
1.3.6.1-rasm.Karno kartasi yordamida minimallashtirish 
keltirilgan. Ushbu jadvallar uchun shuni esda tutish kerakki, qo'shni hujayralar 
ekstremal ustunlarning mos keladigan hujayralarida va yuqori va pastki qatorlarning 
mos keladigan hujayralarida joylashgan hujayralardir. 5 va undan ortiq 
o'zgaruvchilar jadvallari uchun, shuningdek, 4x4 kvadratchalar deyarli uchinchi 
o'lchovda bir-birining ustida joylashganligini hisobga olish kerak, shuning uchun 
ikkita qo'shni 4x4 kvadratlarning mos keladigan hujayralari tutashi bir-biriga qo'shni 
bo'lib, 
ularga 
mos 
kelishi 
mumkin. 
Karno xaritasi har qanday miqdordagi o'zgaruvchilar uchun tuzilishi mumkin,
ammo beshdan ko'p bo'lmagan o'zgaruvchilar soni bilan ishlash qulay. Aslida, Karno 
xaritasi 2 o'lchovli shaklda tuzilgan haqiqat jadvalidir. Unda Grey kodidan 
foydalanish tufayli yuqori satr pastki qatorga qo'shni, o'ng ustun esa chap tomonga 
qo'shni, ya'ni.butun Karno kartasi tor (Bagel) shakliga o'ralgan. Satr va ustunning 
kesishmasida haqiqat jadvalidan tegishli qiymat qo'yiladi. Karta to'ldirilgandan 
so'ng, 
siz 
minimallashtirishni 
boshlashingiz 
mumkin. 
Agar siz minimal dnf olishingiz kerak bo'lsa, unda xaritada biz faqat birliklarni o'z 
ichiga olgan hujayralarni ko'rib chiqamiz, agar KNF kerak bo'lsa, unda nollarni o'z 
ichiga olgan hujayralarni ko'rib chiqamiz. Minimallashtirishning o'zi quyidagi 
qoidalarga 
muvofiq 
amalga 
oshiriladi:
1. Biz birliklarni o'z ichiga olgan qo'shni hujayralarni mintaqaga birlashtiramiz, 
shunda bitta maydon 2
n
(ntamsayı \ u003d 0...
) hujayralarni o'z ichiga 
oladi(ekstremal qatorlar va ustunlar bir-biriga qo'shni ekanligini eslang), 
mintaqada nollarni o'z ichiga olgan hujayralar bo'lmasligi kerak; 
2. Mintaqa eksa(lar) ga nosimmetrik tarzda joylashtirilishi kerak (o'qlar har to'rt 
hujayrada joylashgan); 
3. Nosimmetrik joylashgan qo'shni bo'lmagan joylar o'qlar (lar) biriga 
birlashtirilishi mumkin; 


34 
4. Hudud iloji boricha kattaroq bo'lishi kerak va hududlar soni iloji boricha 
kamroq bo'lishi kerak; 
5. Hududlar kesishishi mumkin
6. Bir nechta qoplash variantlari mumkin. 
Keyinchalik, biz birinchi mintaqani olamiz va ushbu sohada qanday o'zgaruvchilar 
o'zgarmasligini ko'rib chiqamiz, agar o'zgarmaydigan o'zgaruvchi nolga teng bo'lsa, 
biz uning ustiga inversiya qo'yamiz. Biz keyingi maydonni olamiz, birinchisi bilan 
bir xil narsani qilamiz va hokazo. Hududlarning birlashishi disjunktsiya bilan 
birlashtiriladi. 
Masalan 
(2-chi 
O'zgaruvchilardagi 
kartalar 
uchun): 
1.3.6.3-rasm.Karno kartasi yordamida minimallashtirish 
KNF uchun hamma narsa bir xil, biz faqat nolga ega bo'lgan hujayralarni ko'rib 
chiqamiz, biz bitta domen ichidagi o'zgaruvchilarni disjunktsiyada birlashtiramiz 
(inversiyalarni bitta o'zgaruvchilar ustiga qo'yamiz) va mintaqalarning 
disjunktsiyalarini birlashtiramiz. Bunda minimallashtirish tugallangan deb 
hisoblanadi.
:KNFformatida: 


35 
Shunday qilib, rasmdagi Karno xaritasi uchun.1 dnf formatidagi ifoda quyidagi 
shaklga ega bo'ladi 

Download 3.09 Mb.

Do'stlaringiz bilan baham:
1   ...   7   8   9   10   11   12   13   14   ...   51




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling