asosida biz quyidagilarni olamiz

Biror mantiqiy algebra funktsiyasini amalga oshiruvchi mantiqiy sxemaniqurishdan avval bu funktsiyani minimallashtirishga urinib ko`rish lozim. Ko`pinchaDNSHda berilgan mantiqiy funktsiyalar minimallashtiriladi. Asosiy maqsad –minimalDNSHni olishdir.Mantiqiy algebra funktsiyasining minimal DNSHdabarcha diz’yunktiv hadlardagi o`zgaruvchilar va ularning inkorlari sonlariningyig`indisi bu funktsiyaning barcha ekvivalentidagiga nisbatan kam bo`ladi.Minimallashtirish, ya’ni berilgan mantiqiy funktsiya uchun eng sodda ifodanitopish, turli usullar bo`yicha amalga oshiriladi. Quyida ba’zilari bilan tanishibchiqamiz.Kvayn usuli. Ushbu usul minimallashtiriluvchi mantiqiy funktsiyaningMDNSHda berilishiga asoslanadi. Minimallashtirish ikkita bosqichda amalgaoshiriladi.Birinchi bosqichda MDNSHdan qisqartirilgan DNSHga o`tiladi. Bundadastlabki mantiqiy funktsiyaning barcha kon’yunktsiyalari juftlari o`zarotaqqoslanadi. Agar AxvaAx kabi kon’yunktsiyalar uchrasa, ular orasida biriktirishamalga oshiriladi:AxAx= AxAx ANatijada A(n-1) darajali kon’yunktsiya olinadi. AxvaAx kon’yunktsiyalariesa dastlabki ifodada qolib, MDNSHning boshqa hadlari bilan taqqoslanadi.Dastlabki MDNSHning biriktirish bajarilgan n-darajali kon’yunktsiyalaribelgilanadi. Natijada (n-1) darajali elementar kon’yunktsiyalar guruhi van darajalibelgilanmagan kon’yunktsiyalar hosil bo`ladi. Belgilanmagan kon’yunktsiyalaroddiy implikantlar hisoblanib, keyinchalik qisqartirilgan DNSHga qo`shiladi.So`ngra tavsiflangan muolaja olingan (n-1) darajali elementar kon’yunktsiyalarguruhiga 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-biribilan birikmay qolgandagina, ya’ni r-darajali oddiy implikantaga aylangandaginatugaydi. Birinchi bosqich bajarilishi natijasida barcha oddiy implikantlarni o`zichiga oluvchi DNSHning qisqartirilgan yozuvi olinadi.Misol. Quyidagi mantiqiy funktsiyaning qisqartirilgan DNSHi olinishi talabqilinsin:8(1)1 2 3 471 2 3 461 2 3 451 2 3 441 2 3 431 2 3 421 2 3 411 2 3 4 x x x x x x x x x x x x x x x xf x x x x x x x x x x x x x x x x       Yechish. Biriktirish amali 1-4, 1-6, 2-3, 2-7, 3-4, 3-8, 5-6, 5-8, 7-8kon’yunktsiyalari orasida amalga oshiriladi. Dastlabki MDNSHning barchakon’yunktsiyalari biriktirishda qatnashadi va (1) dagidek tagiga chiziladi. Natijadadastlabki (1) mantiqiy funktsiya quyidagicha yozilishi mumkin:Olingan ifodada 3-9 va 4-6 kon’yunktsiyalar juftlarini tagiga chizib, ular orasidabiriktirish amalini bajaramiz. Natijada dastlabki (1) mantiqiy funktsiyaningqisqartirilgan DNSH olinadi:.62 351 3 441 2 431 2 422 3 411 3 4f  x x x  x x x  x x x  x x x  x x x  x xMinimallashtirishni bevosita o`zgartirish usuli. Minimallashtirishningikkinchi bosqichida qisqartirilgan DNSHdan tupik DNSHga o`tiladi va ularningichidan minimal DNSH tanlab olinadi. Tupik DNSH qisqartirilgan DNSHdanortiqcha oddiy implikantlarini aniqlab chiqarib tashlash yo`li bilan olinadi.Ortiqcha oddiy implikantlar deganda mantiqiy funktsiya qiymatiningo`zgarishiga olib kelmaydigan qisqartirilgan DNSHning chiqarib tashlanganhadlari tushuniladi. Tupik DNSHni olish uchun implikant jadvali (matritsasi)tuziladi. Jadvalning qatorlari qisqartirilgan DNSHning oddiy implikantlari bilanbelgilansa, ustunlari dastlabki mantiqiy funktsiya MDNSHning mintermlari bilanbelgilanadi. Qatorda har bir oddiy implikanta qarshisiga u 1 qiymatini qabulqiluvchi naborlar tagi  belgisi bilan belgilanadi; mos mintermlar ushbu oddiyimplikanta bilan singdiriladi (qoplanadi).1-jadval (1)ning imlikanta jadvali hisoblanadi.1-jadval.Oddiy implikantlarning umumiy sonidan implikantlari mantiqiyfunktsiyaning birlik qiymatlarini qoplovchi qismini ajratib olish zarur; qolganimplikantlar ortiqcha hisoblanadi.91 2 381 3 471 2 462 3 451 2 442 3 431 2 322 3 411 3 4x x x x x xf x x x x x x x x x x x x x x x x x x x x x        Tupik shakllarni shakllantirish va minimal qoplanishni tanlash mantiqiyfunktsiyaning birlik qiymatlarini qoplovchi majburiy oddiy implikantlarnianiqlashdan boshlanadi.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-implikanta3 va 8-to`plamga mos keluvchi mantiqiy funktsiyaning birlik qiymatini hamqoplaydi. Shunday qilib, 1-5 oddiy implikantlar qoplanmagan 1, 4-6 to`plamlardagimantiqiy funktsiya qiymatini qoplashi kerak bo`ladi. Bu to`rtta to`plamlarni 1-5implikantlarning turli birikmalari yordamida qoplash mumkin, ya’ni bir talay tupikshakllar shakllanib, ularning ichidan minimal DNSH tanlab olinadi.Ko`rilayotgan misol uchun implikanta jadvali bo`yicha quyidagi minimalDNSHni aniqlash qiyin emas..2 3 1 3 4 1 2 4f x x x x x x x xмин  Boshqa tupik shakllar uchdan ortiq oddiy implikantlarga ega va, demak,minimal bo`lmaydi.Kvayn usulining kamchiligi sifatida r-darajali (1r n) kon’yunktsiyalarjuftlarini bir-biri bilan to`la taqqoslash zaruriyatini ko`rsatish mumkin. Bu esa, o`znavbatida, dastlabki MDNSHdagi kon’yunktsiyalarning katta sonida usulningqo`llanishiga qiyinchiliklar tug`diradi.Kvayn-Mak-Klaski usuli. Ushbu usul taqqoslanuvchi kon’yunktsiyalarjuftlari sonini aytarlicha kamaytirish imkonini beradi. Buning uchun barchaelementar kon’yunktsiyalar taqqoslashdan avval guruhlarga ajratiladi. Har birguruhga inkorsiz o`zgaruvchilarning soni bir xil bo`lgan kon’yunktsiyalar kiritiladi:i-guruhga (i=0,1, ..., n) inkorsiz i ta o`zgaruvchiga ega bo`lgan kon’yunktsiyalarkiritiladi. Masalan, n=4 da birinchi guruhga (i=1)1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4x x x x , x x x x , x x x x , x x x x ,ko`rinishdagi kon’yunktsiyalar, ikkinchi guruhga (i=2)1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4x x x x , x x x x , x x x x , x x x x , x x x x , x x x xko`rinishdagi kon’yunktsiyalar kiritiladi va h. Juftliklarni taqqoslash faqattartib raqami bo`yicha qo`shni bo`lgan guruhlar orasida amalga oshirilishi mumkin,chunki birikuvchi kon’yunktsiyalar faqat qo`shni guruhlarda bo`lishi mumkin.Minimallashtirishning Mak-Klaski usulining qolgan muolajalariminimallashtirishning Kvayn usulidagidek amalga oshiriladi.Amaliy qism.Misol.F(x)={1,2,3,6,7,8} funksiyani Kvayn usulida minimizatsiya qiling.Yechish:Berilgan funksiya ko`rsatilgan nuqtalarda chin qiymat qabul qilib,qolgan barcha nuqtalarida esa yolg`on qiymat qabul qiladi. Mazkur funksiyanichinlik jadvalidagi ko`rinishi quyidagi jadvalda o`z aksini topgan.1. Chinlik jadvalida funksiya qiymatlarini hosilqilamiz. Jadvaldagi chin qiymatlar soni, funksiyaningko`rsatilgan nuqtalari soni bilan teng bo`lishi kerak.2. Jadval yordamida Kvayn usulini qo`llagan holdafunksiyaning ko`rinishi hosil qilamiz. Chin qiymatga egasatrlarni inobatga olamiz, qolganlari esa o`z nomi bilanyolg`on qiymatli.Chin qiymat bo`lsa, o`zi agar yolg`on qiymatga egabo`lsa, inkori olinadi. Ya’ni rostda A,B,C yoki D olinadi,yolg`on bo`lsa, uning inkori olinadi.Nazorat savollari:1. funktsiyalarni minimallashtirishda asosiy maqsad nimadan iborat?2. Mantiq algebrasi funksiyalarini qanday minimallashtiriladi?3. Kvayn usuliga misol keltiring?4. Kvayn-Mak-Klaski usuli.