Diskret qurilmalar nazariyasi nisbatan yosh va tez rivojlanayotgan fan sohalaridan biri hisoblanadi

MAFni Kvayn va Mak-Klaski usulida minimizasiyalash. Kvayn i Mak-Klaski usuli algebra mantiqiy funksiyalarda minimizasiyalash hisoblanadi, shuning uchun ushbu usulda funksiya ifodasini aylantirishda quyidagi ketma-ketlikda ikki bosqichli aylantirish bajariladi: birinchi holatda kanonik shakldan qisqartirilganga, ikkinchisida – mantiqiy ifodani qisqartirilgan shakldan minimalga o’tkaziladi.
Sodda implikantlarni shakllantirish va qisqartirilgan diz’yunktiv normal shaklni (DNSh) hosil qilish uchun n o’zgaruvchilarni minimizasiyalanadigan MAF hamma konstituantlari ikkilik raqamlar ko’rinishida yoziladi. Keyin m birliklar miqdori ikkilik sonlarini indeksi deb ataladi. m-lik guruhlarga m birlikka teng, o’zining ikkilik yoziladigan qismiga ega hamma raqamlar kiradi.
Bir xil indeksli ikkilik raqamlar m indeksda oshib boradigan tartibli gorizontal chiziqda bo’lib turilgan guruhlari ustunda joylashadi. Keyin quyidagi operasiyalar bajariladi: hamma hadlarni ikkilik raqamlari juftma-juft, guruh hadlaridagi m indekslari m+1 ega bo’lgan indekslar bilan taqqoslanadi, shunda agar taqqoslanadigan ikkilik kodlari faqat bitta razryadda farq qilsa birinchi qoldiqlar ustunidagi ushbu razryad joyiga kodlar chiziqcha bilan yoziladi, yelimlash oprasiyasida ishtirok etadigan ikkilik kodlar raqamlarin shartl belgi bilan farqlanadi, masalan V.
Ko’rsatilgan operasiyalar m o’sish tartibida ketma-ket ravishda hamma guruhlar uchun qaytariladi. Hamma V bilan belgilanmaganlari ikkilik raqamlar sodda implikantlarga mos bo’ladi.
Qisqartirilgan ikkilik raqamlar qoldiqlari bo’yicha hosil qilingan birinchi ustuni yana bir marta ko’rib chiqilgan operasiya qo’llaniladi va qoldiqlarni ikkinchi ustuni shakllantiriladi.
Yelimlashga bir xil razryadlarda chiziqqa ega qisqartirilgan ikkilik raqamlari tegishli bo’ladi va ular faqat bitta razryad qiymati bilan farqlanadi. Qoldiqlarni ikkinchi ustunida qisqartirilgan ikkilik raqamlari endi ikkita chiziqqa ega bo’ladi.
Qisqartirilgan ikkilik kodlarini shakllantirish jarayoni yelimlash imkoni bo’lguncha davom ettiriladi.
Masalan. Raqamli usulda berilgan MAF:
f={3, 4, 5, 7, 9, 11, 12, 13} x₁, x₂, x₃, x₄.

O’nlik raqamlarini ikkilik ekvivalentiga o’tganda, konstituant, birlik soni bo’yicha guruhlarda qisqartirib va taqqoslash operasiyasi o’tkazilib hamda yuqorida keltirilgan yelimlash uslubi ta’rifiga mos ravishda quyidagini hosil qilamiz:

Keyingi jarayon diz’yunksiya belgisi bilan belgilanmagan implikantlarni yolimlash imkoni yo’qdir. Bu implikantlar sodda bo’lib, ularni A, V, S, D, E, F harflari bilan belgilaymiz. Qisqartirilgan DNShning minimizasiyalashgan funksiyasi f=A\/B\/C\/D\/E\/F ko’rinishga ega. Mantiqiy ifodalarni keyingi qisqartirish holati ortiqcha hadlarni olib tashlash orqali erishiladi.

Sodda implikantlardan boshi berk shakllarni tuzish va qoplash jadvali deb nom olgan implikantlar jadvalini qo’llash orqali minimal shakllarni olinadi. Uning qatorlari sodda implikantlar bilan mos keladi, graflari esa – funksiya konstituantlari (DMNSh hadlari) bilan mos keladi. DMNSh hadlarining ustunlarini hozirgi mavjud shakllangan implikant bilan yelimlashda, X belgisi bilan belgilanadi. Bu implikant ushbu konstituyentni qoplaydi (yutib yuboradi) deb aytiladi. Ko’rib chiqilayotgan funksiya implikant jadvaliga (3.1-jadval) mos keladi.
Agar tuzilgan jadvaldagi har qanday ustunda mos qatorda joylashgan sodda implikantda bitta belgi bo’lsa, ahamiyatli deb ataladi va belgi aylanaga olinadi. Ahamiyatli implikantni olib tashlash mumkin emas, chunki u siz funksiyaning qoplangan hamma konstituyent to’plami hosil qilinmaydi.
3.1-jadval

Ahamiyatli implikantlar yig’indisi funksiyaning yadrosi deb ataladi. Ko’rib chiqilayotgan ahamiyatli implikantni ajratishdan keyin implikant jadvalidagi shunday ustunlar olib tashlanaliki, ular ahamiyatli implikantni yutib yuboradigan konstituyentga mos bo’ladi.

Minimal shaklni olish uchun yadroga kirmagan implikantlan shunday bir minimal soni tanlash kerakki hamma qolgan ustunlardagi belgilarni o’z ichiga olishi kerak. Bunday tanlovni bir qancha imkoni bor variantlarda qoplashni hosil qiladigan sodda implitkatlardagi o’zgaruvchilar sonini minimal yig’indisi bilan qoplash variantiga bersa bo’ladi.
Ko’rib chiqilayotgan A va D funksiya implikantlari birgalikda qolgan hamma konstituyentlarni qoplaydi. Shunday qilib, minimal DNSh (MDNSh) quyidagicha bo’ladi:
.
MDNSh algebrali usulni qo’llash orqali implikant jadvali bo’yicha aniqlanishi mumkin. Funksiya yadrosi bo’yicha yutib olinmaydigan konstituyentlar, shunday implikantlar diz’yunksiya belgilanishi yozib boriladiki, shunda ular qoplanmaydigan bo’ladi. Ko’paytma algebra mantig’i qoidalari bo’yicha ochiladi va diz’yunktiv normal shaklda yoziladi. Ushbu shaklning har bir hadi ortiqchaligi bo’lmagan hamma berilgan fnuksiyaning konstituyent implikant to’plamlariga mos bo’ladi. Funksiya yadrosining har bir to’plamiga mos bo’lgan implikant diz’yunksiyasi, boshi berk funksiya shaklini beradi.
3.1-jadvalga mos ravishda quyidagini yozish mumkin


.
To’rtta boshi berk DNSh hosil bo’ldi, ulardan biri minimal bo’lib u A, D hamda ahamiyatli F implikantdan tashkil topgan.

3.2-jadval

Kvayn i Mak-Klaski usulini qo’llashda minimal kon’yuktiv normal shaklni (MKNSh) hosil qilish uchun MAFda quyidagi xususiyatlar mavjud: MAFning boshlang’ich shakli MKNSh bo’ladi; yelimlanadigan hadlar juftligi a\/x i a\/ ko’rinishda bo’ladi, MKNSh o’zgaruvchilarni diz’yunksiyasi ko’rinishida bo’ladi va u to’plamdagi belgilar bilan inversli belgini taqqoslasa funksiya “0”ga teng bo’ladi.

φ funksiyasi uchun berilgan haqoniylik jadvali qisqartirilgan shakllarni aniqlash algoritmi qo’llab quyidagini hosil qilamiz:



Qisqartirilgan KNSh

Minimal shaklga o’tish uchun implikat jadvali qo’llaniladi (3.3-jadval).

3.3-jadval

Jadvalning hamma ustunlari ahamiyatli implikantlari bilan qoplanadi, shunda x₁\/ hadi ortiqcha va MKNSh funksiyasi quyidagicha