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
k
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
(
n
tamsayı \ 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
Dostları ilə paylaş: