|
2.2. Karno kartalari yordamida mantiqiy funksiyalarni miniumga
keltirish
25
Mantiqiy funksiyani algebraik usul bilan miniumga keltirish ma’lum
ko‘nikmalarni talab etiladi. Har doim ham olingan shakl yechimga ega
bo‘lmaydigan bo‘lavermaydi; ba’zida elimlanayotgan qo‘shimchalarni aniqlash
qiyin bo‘ladi. “Yelimlashtirlayotgan qo‘shiluvchilarni avtomatik ravishda qidirish
usuli – Karno kartalari usuli mavjud.
Karno kartasi – bu funksiyaning barcha imkoni bo‘lgan mintermalar uchun
yacheykalar ega bo‘lgan jadvaldir. Karno kartalari mintermalari ikki uch va undan
ko‘p o‘zgaruvchanlarga ega bo‘lgan funksiyalar uchun tuzish mumkin. Karno
kartasi 2.3. rasmda ikki o‘zgaruvchanli funksiya uchun keltirilgan. Yuqori qirra
chegara bo‘yicha o‘zgaruvchan x
1
uchun barcha mumkin bo‘lgan qiymatlari
keltirilgan, chap qirra bo‘yicha esa - (“0” va “1”) o‘zgaruvchanning barcha
qiymatlari.
2.3. rasm.
Ikkita o‘zgaruvchan uchun Karno kartasi to‘rtta katakdan iborat bo‘ladi. Har
bir katakda ikkita o‘zgaruvchan funksiya mumkin bo‘lgan mintermalari
qiymatlaridan biri qo‘yiladi: x
2
x
1
, x
2
x
1
, x
2
x
1
, x
2
x
1
. Agar MDNSHda bu
mintermalarning biri bo‘lsa, unda unga to‘g‘ri keluvchi Karno katagida “1”
yoziladi. Agar qandaydir minterma bo‘lmasa, unga to‘g‘ri keluvchi katakda “0”
yoziladi.
Uch va to‘rt o‘zgaruvchan funksiyalar uchun 2.4. va.2.5. rasmlarda mos
ravishda keltirilgan. 2.4. rasmda karta kataklarida uchta o‘zgaruvchanlarning
barcha imkon bo‘lgan son qiymatlari kombinatsiyalari qo‘yilgan.
O‘zgaruvchanlarning bu kombinatsiyalari berilgan MFning minermalarini
yozish uchun koordinatalarini beradi.va 2.4. rasmda tushintirish uchun kataklarga
26
kiritilgan, lekin MF berilgan bo‘lsa Karno kataklari bo‘sh bo‘lishi kerak.,
2.5.rasmda to‘rtta o‘zgaruvchanlar uchun ko‘rsatilganidek. Odatda kartaning
yuqori chap qirralarida ko‘rsatilgan mintermalarga mos kelishini aniqlash kerak
bo‘ladi. Uch va to‘rtta o‘zgaruvchanlar uchun Karno kartasining o‘ziga xosligi
karta kataklarida ikkita o‘zgaruvchanlarning kombinatsiyalari odatiy pozitsion
ikkili 8-4-2-1 kodida emas, balki Grey kodi deb nomlanuvchi kodda ya’ni ikkilik
sonni qo‘shni songa o‘tishda faqat ikkilik razryadning bitta qiymati o‘zgaradi (00,
01, 10, 11).
2.4. rasm.
Boshqacha aytganda Karno kartasi asosida elimlash operatsiyasi noto‘g‘ri
natijaga olib kelar edi.
Yelimlash karno kartasi qo‘shni kataklarida “1” qiymatlari yozilgan
mintermalar orasida amalga oshiriladi (qo‘shni vertikal yoki gorizontal, faqat
iogonal bo‘yicha emas bo‘lishi kerak). Shunigdek qo‘shni kataklar deb kartaning
eng yuqori va eng pastki kataklari, hamda eng chap va eng o‘ng kataklari
hisoblanadi (ya’ni birlashtilishiga ko‘ra karta silindrining vertikal yoki gorizontal
o‘qi bo‘yicha olingan yoymasi).
27
2.5. rasm
Yelimlash operatsiyasi natijasida qo‘shni kataklarda joylashgan ikkita
mintermalar bitta o‘zgaruvchanlarning mantiqiy ko‘paytmasi ko‘rinishida
ifodalanishi mumkin (bu erda ularning soni kam bo‘ladi). Agar qo‘shni
mintermalar birdaniga to‘rtta bo‘lsa “1” unda bunday mintermalar guruhini har bir
mintermada ikkita “1” ga kam bo‘lgan o‘zgaruvchanlarning kon’yuksiyasi bilan
almashtirish mumkin.
Mantiq algebrasida (a+a+a+….+a=a) hisobga olgan holda, mintermani aks
ettiruvchi bitta birni bir necha marotaba guruhlarga birlashtirish mumkin. Masalan,
birinchi martta vertikal bo‘yicha qo‘shni bir bilan, ikkinchi – gorizontal bo‘yicha
qo‘shni bir bilan.
Masalan, quyidagi funksiyani miniumga keltirish kerak:
1
3
3 2
3
2 1
2 1
3 2 1
у х х х
х х х
х х х
х х х
Berilgan funksiyaga mos ravishda to‘ldirilgan Karno kartasi 2.6. rasmda
keltirilgan. Kartada
x
3
x
2
x
1
va
x
3
x
2
x
1
aks ettiruvchi minterma birdaniga “a”, “v”,
“s” konturlar bilan o‘ralgan uchta birlashmaga kiradi. Kontur “a” ga to‘g‘ri
keluvchi birlashma
x
3
x
2
x
1
va
x
3
x
2
x
1
mintremalarni elimlanishini aks ettiradi:
3 2 1
3
2 1
3 1
2
2
3 1
(
)
х х х
х х х
х х х
х
х х
x
2
x
1
x
4
x
3
00 01 11 10
00
01
11
10
0000
0001
0011 0010
0100
0101
0111 0110
1100
1101
1111 1110
1000
1001
1011 1010
28
2.6. rasm.
Kontur “v” bilan o‘ralgan birlashma 2.6. rasmda
x
3
x
2
x
1
va
x
3
x
2
x
1
mintermalarni elimlanishi aks ettiradi:
1
1
3 2
3 2 1
3 2
1
3 2
(
)
х х х
х х х
х х х
х
х х
Kontur “s” bilan o‘ralgan birlashma 2.6. rasmda
x
3
x
2
x
1
va
x
3
x
2
x
1
mintermalarni elimlanishini aks ettiradi:
3
3 2 1
2 1
2 1
3
3
2 1
(
)
х х х
х х х
х х х
х
х х
“Elimlash” operatsiyalarin o‘tkazish natijasida berilgan funksiyaga kiruvchi
va uchta o‘zgaruvchanlarning kon’yuksiyasi bo‘lgan to‘rtta mintermalardan faqat
x
2
x
1
,
x
3
x
2
, x
3
x
1
, yig‘indilari qoladi. Bu erdan
2 1
3 2
3 1
у х х
х х
х х
Berilga funksiya uchun xuddi shunday natijani miniumga keltirishning
algebraik usuli ham beradi. Karno kartasi “elimlanuvchi” mintermalarni engil
aniqlashga va funksiyani miniumga keltirishga imkon berdi.
Karno kartasi bo‘yicha miniumga keltirish orqali olingan strukturaviy
formula MFni yechimsiz shaklini algebraik usul bilan olingani kabi kombinatsion
sxemalarni mantiqiy loyixalashda qo‘llaniladi.
Umumiy xolatda “elimlash” operatsiyasini o‘tkazishda Karno kartasini birlik
kataklarini o‘ragan konturlar, 2
n
kataklar (minterma)dan iborat bo‘lishi mumkin,
bu erda n= 0, 1,2,3,4… .
29
Karno kartasi bo‘yicha miniumga keltirishni yana bir misolini ko‘rib
chiqamiz. Agar uchta o‘zgaruvchanlar uchun MF 2.1 jadval bilan berilgan bo‘lsin.
2.1 jadval
“Birlik” mintermalar bilan to‘ldirishdan so‘ng Karno kartasi 2.7. rasmda
ko‘rsatilgan shaklga ega bo‘ladi. Bu erda “elimlash” operatsiyasi uchun faqat
ikkita birlashmani xosil qilish mumkin, х
3
х
2
х
1
mintermasi esa xech qanday
qo‘shnilarga ega emas, shuning uchun “elimlash” amalga oshirilmaydi va alohida
hisobga olinadi.
2.7. rasm.
Miniumga keltirish natijasida quyidagi strukturaviy formulani olamiz:
2
1
3
3
3 2 1
F
х х
х х
х х х
Ushbu formula avval algebraik usul bilan olingani bilan mos tushadi.
Xulosa.
Karno kartalari bo‘yicha miniumga keltirish usuli algebraik usuliga
nisbatan yanada ko‘rgazmali bo‘lib analogik natijaga olib keladi. Undan tashqari
Do'stlaringiz bilan baham: | 
