O’zbekiston respublikasi transport vazirligi toshkent davlat transport universiteti

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.