Raqamli qurilmalarni loyihalashga kirish” fanidan laboratoriya ishlari farg’ona 2022

Kvayn usuli. Ushbu usul minimallashtiriluvchi mantiqiy funktsiyaning MDNSHda berilishiga asoslanadi. Minimallashtirish ikkita bosqichda amalga oshiriladi.
Birinchi bosqichda MDNSHdan qisqartirilgan DNSHga o`tiladi. Bunda dastlabki mantiqiy funktsiyaning barcha kon’yunktsiyalari juftlari o`zaro taqqoslanadi. Agar AxvaAx kabi kon’yunktsiyalar uchrasa, ular orasida biriktirish amalga oshiriladi:
AxAx= AxAx A
Natijada A(n-1) darajali kon’yunktsiya olinadi. AxvaAx kon’yunktsiyalari esa dastlabki ifodada qolib, MDNSHning boshqa hadlari bilan taqqoslanadi. Dastlabki MDNSHning biriktirish bajarilgan n-darajali kon’yunktsiyalari belgilanadi. Natijada (n-1) darajali elementar kon’yunktsiyalar guruhi van darajali belgilanmagan kon’yunktsiyalar hosil bo`ladi. Belgilanmagan kon’yunktsiyalar oddiy implikantlar hisoblanib, keyinchalik qisqartirilgan DNSHga qo`shiladi. So`ngra tavsiflangan muolaja olingan (n-1) darajali elementar kon’yunktsiyalar guruhiga qo`llaniladi, natijada (n-r) darajali elementar kon’yunktsiyalar guruhi va (n-1) darajali belgilanmagan kon’yunktsiyalar (oddiy implikantlar) olinadi va h. Bosqich yangidan olingan r-darajali (1r n) elementar kon’yunktsiyalar bir-biri bilan birikmay qolgandagina, ya’ni r-darajali oddiy implikantaga aylangandagina tugaydi. Birinchi bosqich bajarilishi natijasida barcha oddiy implikantlarni o`z ichiga oluvchi DNSHning qisqartirilgan yozuvi olinadi.
Misol. Quyidagi mantiqiy funktsiyaning qisqartirilgan DNSHi olinishi talab qilinsin:
(1)
Yechish. Biriktirish amali 1-4, 1-6, 2-3, 2-7, 3-4, 3-8, 5-6, 5-8, 7-8 kon’yunktsiyalari orasida amalga oshiriladi. Dastlabki MDNSHning barcha kon’yunktsiyalari biriktirishda qatnashadi va (1) dagidek tagiga chiziladi. Natijada dastlabki (1) mantiqiy funktsiya quyidagicha yozilishi mumkin:
Olingan ifodada 3-9 va 4-6 kon’yunktsiyalar juftlarini tagiga chizib, ular orasida biriktirish amalini bajaramiz. Natijada dastlabki (1) mantiqiy funktsiyaning qisqartirilgan DNSH olinadi:

Minimallashtirishni bevosita o`zgartirish usuli. Minimallashtirishning ikkinchi bosqichida qisqartirilgan DNSHdan tupik DNSHga o`tiladi va ularning ichidan minimal DNSH tanlab olinadi. Tupik DNSH qisqartirilgan DNSHdan ortiqcha oddiy implikantlarini aniqlab chiqarib tashlash yo`li bilan olinadi. Ortiqcha oddiy implikantlar deganda mantiqiy funktsiya qiymatining o`zgarishiga olib kelmaydigan qisqartirilgan DNSHning chiqarib tashlangan hadlari tushuniladi. Tupik DNSHni olish uchun implikant jadvali (matritsasi) tuziladi. Jadvalning qatorlari qisqartirilgan DNSHning oddiy implikantlari bilan belgilansa, ustunlari dastlabki mantiqiy funktsiya MDNSHning mintermlari bilan belgilanadi. Qatorda har bir oddiy implikanta qarshisiga u 1 qiymatini qabul qiluvchi naborlar tagi  belgisi bilan belgilanadi; mos mintermlar ushbu oddiy implikanta bilan singdiriladi (qoplanadi).
4.1-jadval (1)ning imlikanta jadvali hisoblanadi.
4.1-jadval.

Oddiy implikantlarning umumiy sonidan implikantlari mantiqiy funktsiyaning birlik qiymatlarini qoplovchi qismini ajratib olish zarur; qolgan implikantlar ortiqcha hisoblanadi.
Tupik shakllarni shakllantirish va minimal qoplanishni tanlash mantiqiy funktsiyaning birlik qiymatlarini qoplovchi majburiy oddiy implikantlarni aniqlashdan boshlanadi.
4.1-jadvaldan ko`rinib turibdiki, 6-oddiy implikanta majburiy hisoblanadi, chunki faqat u 2 va 7-to`plamlarda mantiqiy funktsiyaning birlik qiymatini qoplaydi (bu to`plamlarga mos ustunlarda faqat bittadan  belgisi bor). Ammo 6-implikanta 3 va 8-to`plamga mos keluvchi mantiqiy funktsiyaning birlik qiymatini VA qoplaydi.