Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

- t e o r e m a .

f (x₁, x₂ ,..., x_n )
n
– matematik mantiq algebrasining ixtiyoriy

funksiyasi
( f  0) va
D   K

i
i1
uning ixtiyoriy (I va II almashtirishlarga nisbatan)

tupikli DNSh bo‘lsin. U holda MDNShning shunday tartiblashi mavjud bo‘ladiki, undan soddalashtirish algoritmi yordami bilan D tupikli DNShni hosil qilish mumkin.
N a t i j a . Tupikli DNShlar orasida albatta L indeksga nisbatan minimal DNShlar (hammasi bo‘lishi shart emas) mavjud bo‘lgani uchun, soddalashtirish algoritmi, MDNShni ma’lum ravishda tartiblash natijasida, minimal DNShni ham topishga imkon yaratadi.
Shunday qilib, minimal DNShni topish uchun MDNShni tartiblash kerak va unga nisbatan soddalashtirish algoritmini ishlatish kerak.

Teoremaning isbotidan¹ soddalashtirish algoritmi yordami bilan tupikli DNShlarni mukammal DNShdan yasash uchun faqat kon’yunksiyalar ifodasida ko‘paytuvchilar joylashishini variatsiyalash yetarligi kelib chiqadi.
Hozirgi vaqtda kon’yunksiyalarni DNSh ifodasidan chetlashtirish va ko‘paytuvchilarni kon’yunksiyalar ifodasidan chetlashtirish mumkinligini tekshirishlar soni (MDNSh tartiblashning hamma turi bo‘yicha)
^ n log ⁿ 1^2 n




₂ ₂ 
 (n  2)  2ⁿ

sondan ortiq emasligi isbotlangan. Bu son 2³n sondan ancha kamdir, ya’ni soddalashtirish algoritmi birma-bir ko‘zdan kechirish algoritmidan yaxshiroq ekanligi ma’lum bo‘ladi.