I kirish II. Asosiy qism matematik mantiq funksiyalarining minimallashtirish muammosi masalasining qo‘yilishi

3-ta’rif. Agar funksiyani realizatsiya etuvchi DNSH indeksga nisbatan minimal bo‘lsa, u holda bunday DNSH ga nisbatan minimal DNSH, indeksga nisbatan minimal bo‘lgan DNSH ga eng qisqa dizyunktiv normal shakl deb aytiladi.

Bundan keyin indeksga nisbatan minimal bo‘lgan DNSH ga minimal dizyunktiv shakl deb aytamiz.

1-misolni tahlil qilaylik.

1. DNSH minimal DNSH bo‘ladi, chunki ushbu DNSH orqali ifodalangan funksiyaning argumentlari muhim (soxta emas) argumentlardir. SHuning uchun uni uchta harfdan kam harf bilan ifodalash mumkin emas.

2. DNSH eng qisqa DNSH bo‘ladi, chunki ushbu DNSH bilan ifodalangan funksiya har qanday elementar konyunktsiyadan farq qiladi.

3. DNSH indeksga nisbatan minimal DNSH bo‘ladi, chunki ushbu DNSH bilan ifodalangan funksiya va o‘zgaruvchilari bo‘yicha o‘suvchi funksiya emas va demak, ikkita inkordan kam inkor qatnashgan DNSH ko‘rinishida uni ifodalash mumkin.

Bizning bu bobdagi asosiy vazifamiz, qanday usullar yordami bilan matematik mantiqning ixtiyoriy funksiyasi uchun indeksga nisbatan minimal dizyunktiv normal shaklni topishdan iborat bo‘ladi. Bu muammo matematik mantiq funksiyalarini minimallashtirish muammosi deb aytiladi. Bu masala yechimining trivial algoritmi mavjudligini ko‘rsatamiz.

1. o‘zgaruvchilar to‘plamida hamma ta dizyunktiv normal shakllarni ma’lum tartibda tuzamiz.

2. Keyin bu DNSH lardan funksiyani realizatsiya etadigan DNSHlarni ajratib olamiz.

3. Ajratib olingan DNSH lar soddalik indekslarining ( , , ) miqdorlarini hisoblab chiqamiz.

4. Hisoblab chiqilgan indekslar miqdorlarini bir-biriga taqqoslash yo‘li bilan ga nisbatan minimal bo‘lgan DNSH ni topamiz.

Keltirilgan algoritmni amaliy realizatsiya etish uchun juda ham ko‘p mehnat talab etiladi, chunki kamida ta kichik amalni (operatsiyani) bajarishga to‘g‘ri keladi. Masalan, bo‘lganda, funksiyani realizatsiya etadigan indeksga nisbatan minimal dizyunktiv normal shakllarni topish uchun kamida ta amalni bajarishga to‘g‘ri keladi. SHuning uchun dan boshlab bu algoritmdan foydalanish, mantiqqa to‘g‘ri kelmaydi. Faqatgina va hollar uchun foydalanish mumkin.

Demak, “birma-bir ko‘zdan kechirish” algoritmi minimal dizyunktiv normal shaklni topish masalasida amaliy yordam bermaydigan algoritmdir.

Shuning uchun mantiq algebrasi funksiyasini minimallashtirishning boshqa usullarini izlashga to‘g‘ri keladi.

Tupikli DNSh

- ixtiyoriy DNSH bo‘lsin va

, , (1)

qaerda - qandaydir DNSH, ning birorta elementar konyunktsiyasi, ning birorta ko‘paytuvchisi, ning qolgan ko‘paytuvchilari, . DNSHni soddalashtirishning ikki xil yo‘lini (tipini) ko‘rib o‘taylik.