Mavzu-Minimizasiya prinsipi (tartibi) va mantiqiy ifoda Mantiqiy algebra qonuni. Mantiqiy iboralarni minimallashtirish

Mavzu-Minimizasiya prinsipi (tartibi) va mantiqiy ifoda Mantiqiy algebra qonuni.

Mantiqiy iboralarni minimallashtirish

Reja

1. Minimallashtirish masalasi va usullari

2. Minimallashtirishni bevosita oʼzgartirish usuli

3. Kvayn va Veych-Karno jadvalli minimallashtirish usullari

4. Kombinatsion sxemalar va ularni sintezlash.

MINIMIZATSIYA PRINSIPI (lot. minimumdan - eng kichik).

Minimal til, nutq, ijtimoiy-madaniy materiallar, muloqot mavzulari va vaziyatlari, o'qish uchun matnlar, mintaqaviy voqeliklarni tanlashni o'z ichiga olgan o'qitishning metodik printsipi. Bir tomondan, til o'rganish o'rganish bosqichi va profilini hisobga olgan holda o'rganishning maqsad va vazifalariga mos keladi, ikkinchi tomondan, u nisbatan yopiq funktsional tizimni ifodalaydi va umuman tilning tuzilishini etarli darajada aks ettiradi. . Leksik, grammatik va boshqa minimumlarning o'quv materiali, qoida tariqasidaqurilgan.

Biror mantiqiy algebra funktsiyasini amalga oshiruvchi mantiqiy sxemani qurishdan avval bu funktsiyani minimallashtirishga urinib koʼrish lozim. Koʼpincha DNShda berilgan mantiqiy funktsiyalar minimallashtiriladi. Аsosiy maqsad - minimal DNShni olishdir. Mantiqiy algebra funktsiyasining minimal DNShda barcha dizʼyunktiv hadlardagi oʼzgaruvchilar va ularning inkorlari sonlarining yigʼindisi bu funktsiyaning barcha ekvivalentidagiga nisbatan kam boʼladi.

Minimallashtirish, yaʼni berilgan mantiqiy funktsiya uchun eng sodda ifodani topish, turli usullar boʼyicha amalga oshiriladi. Quyida baʼzilari bilan tanishib chiqamiz.

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. Аgar Аx va А x kabi konʼyunktsiyalar uchrasa, ular orasida biriktirish amalga oshiriladi:АхАх= АхАх А

Natijada А(n-1) darajali konʼyunktsiya olinadi. Аx va А 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 va n 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 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:

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 dagidek tagiga chiziladi. Natijada dastlabki mantiqiy funktsiya quyidagicha yozilishi mumkin:

Olingan ifodada 3-9 va 4-6 konʼyunktsiyalar juftlarini tagiga chizib, ular orasida biriktirish amalini bajaramiz. Natijada dastlabki (12) mantiqiy funktsiyaning 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 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

11-жадвал (2.9)нинг имликанта жадвали ҳисобланади.

Бошқа тупик шакллар учдан ортиқ оддий импликантларга эга ва, демак, минимал бўлмайди.

Квайн усулининг камчилиги сифатида r-даражали (1 r  n) конъюнкциялар жуфтларини бир-бири билан тўла таққослаш заруриятини кўрсатиш мумкин. Бу эса, ўз навбатида, дастлабки МДНШдаги конъюнкцияларнинг катта сонида усулнинг қўлланишига қийинчиликлар туғдиради.