Mantiqiy algebra funksiyalarini minimallashtirish kombinatsion sxemalar va ularni sintezlash

Reja: Minimallashtirish masalasi va usullari Minimallashtirishni bevosita o'zgartirish usuli Kvayn va Veych-Karno jadvalli minimallashtirish usullari Kombinatsion sxemalar va ularni sintezlash. Biror mantiqiy algebra funksiyasini amalga oshiruvchi mantiqiy sxemani qurishdan avval bu funksiyani minimallashtirishga urinib ko'rish lozim. Ko'pincha DNShda berilgan mantiqiy funksiyalar minimallashtiriladi. Asosiy maqsad - minimal DNShni olishdir. Mantiqiy algebra funksiyasining minimal DNShda barcha dizyunktiv hadlardagi o'zgaruvchilar va ularning inkorlari sonlarining yig'indisi bu funksiyaning barcha ekvivalentidagiga nisbatan kam bo'ladi. Minimallashtirish, yani berilgan mantiqiy funksiya uchun eng sodda ifodani topish, turli usullar bo'yicha amalga oshiriladi. Quyida bazilari bilan tanishib chiqamiz. Kvayn usuli. Ushbu usul minimallashtiriluvchi mantiqiy funksiyaning MDNShda berilishiga asoslanadi. Minimallashtirish ikkita bosqichda amalga oshiriladi. Birinchi bosqichda MDNShdan qisqartirilgan DNShga o'tiladi. Bunda dastlabki mantiqiy funksiyaning barcha konyunksiyalari juftlari o'zaro taqqoslanadi. Agar Ax va Ax kabi konyunksiyalar uchrasa, ular orasida biriktirish amalga oshiriladi: AxAx= AxAx A Natijada A(n-1) darajali konyunksiya olinadi. Ax va Ax konyunksiyalari esa dastlabki ifodada qolib, MDNShning boshqa hadlari bilan taqqoslanadi. Dastlabki MDNShning biriktirish bajarilgan n-darajali konyunksiyalari belgilanadi. Natijada (n-1) darajali elementar konyunksiyalar guruhi va n darajali belgilanmagan konyunksiyalar hosil bo'ladi. Belgilanmagan konyunksiyalar oddiy implikantlar hisoblanib, keyinchalik qisqartirilgan DNShga qo'shiladi. So'ngra tavsiflangan muolaja olingan (n-1) darajali elementar konyunksiyalar guruhiga qo'llaniladi, natijada (n-r) darajali elementar konyunksiyalar guruhi va (n-1) darajali belgilanmagan konyunksiyalar (oddiy implikantlar) olinadi va h. Bosqich yangidan olingan r-darajali (1 r n) elementar konyunksiyalar bir-biri bilan birikmay qolgandagina, yani r-darajali oddiy implikantaga aylangandagina tugaydi. Birinchi bosqich bajarilishi natijasida barcha oddiy implikantlarni o'z ichiga oluvchi DNShning qisqartirilgan yozuvi olinadi. Misol. Quyidagi mantiqiy funksiyaning qisqartirilgan DNShi olinishi talab qilinsin: (8.1) yechish. Biriktirish amali 1-4, 1-6, 2-3, 2-7, 3-4, 3-8, 5-6, 5-8, 7-8 konyunksiyalari orasida amalga oshiriladi. Dastlabki MDNShning barcha konyunksiyalari biriktirishda qatnashadi va (8.1) dagidek tagiga chiziladi. Natijada dastlabki (8.1) mantiqiy funksiya quyidagicha yozilishi mumkin: Olingan ifodada 3-9 va 4-6 konyunksiyalar juftlarini tagiga chizib, ular orasida biriktirish amalini bajaramiz. Natijada dastlabki (8.1) mantiqiy funksiyaning qisqartirilgan DNSh olinadi: 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 funksiya 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 funksiya 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). 8.1-jadval ...