Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

Matematik mantiq funksiyalarini minimallashtirish muammosini hal qilish algoritmining mavjudligi. Bu bo’limda 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. {x , x ,..., x }
o‘zgaruvchilar to‘plamida barcha
2³n ta
D , D ,..., D

1 2 n
^{1 2} ₂3ⁿ

diz’yunktiv normal shakllarni ma’lum tartibda tuzamiz.

2. 
   Bu DNSh lardan ajratib olamiz.
   

f (x₁, x₂ ,..., x_n )
funksiyani realizatsiya qiladigan DNShlarni

2. 
   Ajratib olingan DNShlar soddalik indekslarining ( L_h ,
   

hisoblaymiz.
L_k ,
L_i ) miqdorlarini

2. 
   L_h ,
   

L_k , L_i
indekslar miqdorlarini bir-biri bilan taqqoslash yo‘li bilan L ga

nisbatan minimal bo‘lgan DNShni topamiz. ■
Keltirilgan algoritmni amaliy realizatsiya qilish uchun juda ham ko‘p mehnat
n
talab etiladi, chunki kamida 2³ ta sodda amalni (operasiyani) bajarishga to‘g‘ri

keladi. Masalan,
n  3
bo‘lganda,
f (x₁ , x₂ , x₃ )
funksiyani realizatsiya qiladigan L

indeksga nisbatan minimal diz’yunktiv normal shakllarni topish uchun kamida

2³n  2³3  134 217 728
ta amalni bajarishga to‘g‘ri keladi. Shuning uchun
n  3
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
n  1 ^va
n  2
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.

uchun