Ma’ruza: Formulalarni minimallashtirish muammosi Reja: Masalaning qo‘yilishi

2.2 - t e o r e m a .

 

)

,...,

,

(

2

1

n

x

x

x

f

  –  matematik  mantiq  algebrasining  ixtiyoriy 

funksiyasi 

)

0

(



f

  va 

i

n

i

K

D

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

1

  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

n

n

n

n

2

)

2

(

2

2

1

2

log























 

sondan  ortiq  emasligi  isbotlangan.  Bu  son 

2

3

n

sondan  ancha  kamdir,  ya’ni 

soddalashtirish  algoritmi  birma-bir  ko‘zdan  kechirish  algoritmidan  yaxshiroq 

ekanligi ma’lum bo‘ladi.