Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

3- misol. 1- misoldagi va DNShlarni tahlil qilamiz. DNSh minimal DNShdir, chunki ushbu DNSh orqali ifodalangan funksiyaning argumentlari muhim (soxta emas) argumentlardir. Shuning uchun uni uchtadan kam harf bilan ifodalash mumkin emas.
DNSh eng qisqa DNShdir, chunki ushbu DNSh bilan ifodalangan funksiya har qanday elementar kon’yunksiyadan farq qiladi.
DNSh indeksga nisbatan ham minimal DNShdir, chunki ushbu DNSh bilan ifodalangan funksiya va o‘zgaruvchilari bo‘yicha o‘suvchi funksiya emas va demak, uni ikkita inkordan kam inkor qatnashgan DNSh ko‘rinishida ifodalash mumkin. ■
Shunday qilib, asosiy muammo matematik mantiqning ixtiyoriy funksiyasi uchun indeksga nisbatan minimal diz’yunktiv normal shaklni topishdan iboratdir. Bu muammo matematik mantiq funksiyalarini minimallashtirish muammosi deb ataladi.

Matematik mantiq funksiyalarini minimallashtirish muammosini hal qilish algoritmining mavjudligi. Bu bobda matematik mantiq funksiyalarini minimallashtirish muammosini hal qilish usullari bilan shug‘ullanamiz. Avvalo bu masala yechimining trivial algoritmi mavjudligini ta’kidlaymiz. Bu algoritm birma-bir ko‘zdan kechirish algoritmi deb yuritiladi va quyidagi 4 bandda ifodalangan jarayonlarni bajarishni taqazo qiladi.
1. o‘zgaruvchilar to‘plamida barcha ta diz’yunktiv normal shakllarni ma’lum tartibda tuzamiz.
2. Bu DNSh lardan funksiyani realizatsiya qiladigan DNShlarni ajratib olamiz.
3. Ajratib olingan DNShlar soddalik indekslarining ( , , ) miqdorlarini hisoblaymiz.
4. , , indekslar miqdorlarini bir-biri bilan taqqoslash yo‘li bilan ga nisbatan minimal bo‘lgan DNShni topamiz. ■
Keltirilgan algoritmni amaliy realizatsiya qilish uchun juda ham ko‘p mehnat talab etiladi, chunki kamida ta sodda amalni (operasiyani) bajarishga to‘g‘ri keladi. Masalan, bo‘lganda, funksiyani realizatsiya qiladigan indeksga nisbatan minimal diz’yunktiv normal shakllarni topish uchun kamida ta amalni bajarishga to‘g‘ri keladi. Shuning uchun dan boshlab bu algoritmdan foydalanish (hattoki tez hisoblah imkoniyatiga ega bo‘lgan hozilrgi zamon hisoblash mashinalarini ishlatganda ham) mantiqqa to‘g‘ri kelmaydi. Bu algoritmdan faqatgina va bo‘lgan hollar uchun foydalanish mumkin.
Demak, umuman olganda, birma-bir ko‘zdan kechirish algoritmi minimal diz’yunktiv normal shaklni topish masalasida amaliy yordam bermaydigan algoritmdir. Shuning uchun mantiq algebrasi funksiyasini minimallashtirishning boshqa usullarini izlashga to‘g‘ri keladi.