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

2.1 - t e o r e m a .

 

Soddalashtirish  algoritmini  qo‘llash  natijasida  hosil 

qilingan  diz’yunktiv  normal  shakl  (I  va  II  almashtirishlarga  nisbatan)  minimal 

DNSh bo‘ladi. 

2.2 - m i s o l .

  Chinlik  jadvali  vositasida  berilgan  (2.1-jadval) 

)

,

,

(

3

2

1

x

x

x

f

 

funksiyani ko‘rib o‘taylik. 

2.1-jadval 

1

x

 

2

x

 

3

x

 

)

,

,

(

3

2

1

x

x

x

f

 

1

x

 

2

x

 

3

x

 

)

,

,

(

3

2

1

x

x

x

f

 

0  0  0 

1 

1  0  0 

1 

0  0  1 

1 

1  0  1 

0 

0  1  0 

0 

1  1  0 

1 

0  1  1 

1 

1  1  1 

1 

 

)

,

,

(

3

2

1

x

x

x

f

  funksiya  uchun  dastlabki  DNSh  sifatida  MDNShni  olamiz  va  ikki 

tartiblashni o‘tkazamiz: 

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

'

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

D













, 

3

2

1

2

1

3

3

2

1

3

1

2

2

1

3

3

2

1

''

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

D













.

 

Tartibga solingan 

'

D

 DNSh uchun algoritmning ishlashini ko‘ramiz. 

1. 

3

2

1

x

x

x

  kon’yunksiyani  chetlashtirish  mumkin  emas,  ammo 

1

x

 

ko‘paytuvchini chetlashtirish mumkin, chunki 

3

2

1

3

2

1

3

2

x

x

x

x

x

x

x

x





. Natijada 

3

2

x

x

kon’yunksiyaga  ega  bo‘lamiz,  undan  birorta  ham  ko‘paytuvchini  chetlashtirish 

mumkin emas. 

---

2. 

3

2

1

x

x

x

  kon’yunksiyani  ham  chetlashtirish  mumkin  emas.  Bu 

kon’yunksiyadan 

1

x

  ko‘paytuvchini  chetlashtirish  mumkin  emasligini  osongina 

ko‘rish  mumkin,  lekin 

2

x

  ko‘paytuvchiga  nisbatan 

2

x

  ko‘paytuvchini 

chetlashtirish  operatsiyasini  qo‘llash  mumkin. 

3

1

x

x

  kon’yunksiyani  hosil  qilamiz. 

Ko‘paytuvchini chetlashtirish operatsiyasini ishlatib soddalashtirish mumkin emas. 

3. 

3

2

1

x

x

x

 kon’yunksiyani chetlashtirish mumkin, chunki 

3

2

1

3

2

1

3

1

x

x

x

x

x

x

x

x





. 

4. 

3

2

1

x

x

x

 

kon’yunksiyani  ham  chetlashtirish  mumkin,  chunki 

3

2

1

3

2

1

3

2

x

x

x

x

x

x

x

x





. 

5. 

3

2

1

x

x

x

  kon’yunksiyani  chetlashtirish  mumkin  emas,  biroq 

2

x

 

ko‘paytuvchini  tashlab  yuborish  mumkin.  Natijada 

3

1

x

x

  kon’yunksiyaga  ega 

bo‘lamiz. Bu kon’yunksiyaga nisbatan ko‘paytuvchini chetlashtirish operatsiyasini 

ishlatib, uni soddalashtirish mumkin emas. 

6. 

3

2

1

x

x

x

 kon’yunksiyani ham chetlashtirish mumkin emas, ammo undan 

1

x

 

ko‘paytuvchini chetlashtirish mumkin. Natijada, 

3

2

x

x

 kon’yunksiyani hosil qilamiz 

va uni boshqa soddalashtirish mumkin emas. 

Shunday  qilib, 

3

2

3

1

3

1

3

2

x

x

x

x

x

x

x

x







  DNShni  hosil  qilamiz.  Bu  DNShga 

nisbatan kon’yunksiyani chetlashtirish operatsiyasini ishlatish natija bermaydi. 

Demak, soddalashtirish algoritmini ishlatish natijasida 

3

2

3

1

3

1

3

2

1

x

x

x

x

x

x

x

x

D









 

(2) 

DNShni hosil qilamiz. Yuqorida keltirilgan hisoblashlar 2.2-jadvalda aks ettirilgan. 

Agar soddalashtirish algoritmini 

'

'

D

ga nisbatan ishlatsak, u holda 

2

1

3

1

3

2

2

x

x

x

x

x

x

D







 

(3) 

diz’yunktiv normal shaklga ega bo‘lamiz. 

2.3-jadvalda 

'

'

D

ga  nisbatan  ishlatilgan  soddalashtirish  algoritmi  ishining 

asosiy bosqichlari keltirilgan. ■ 

2.2-misoldan ko‘rinib turibdiki, soddalashtirish algoritmi tatbiqining natijasi 

dastlabki DNShni qanday tartiblashga bog‘liq bo‘lar ekan. 

2.2-jadval 

Qadam 

tartib 

raqami 

DNSh va 

ko‘rilayotgan 

tartib 

Tekshiri- 

layotgan 

kon’yunksiya 

Operatsiya 

turi 

1 





3

2

1

3

2

1

x

x

x

x

x

x

 







3

2

1

3

2

1

x

x

x

x

x

x

 

3

2

1

3

2

1

x

x

x

x

x

x





 

 

 

3

2

1

x

x

x

 

 

1

x

ni 

chetlashtirish 

---

2 





3

2

1

3

2

x

x

x

x

x

 







3

2

1

3

2

1

x

x

x

x

x

x

 

3

2

1

3

2

1

x

x

x

x

x

x





 

 

 

3

2

1

x

x

x

 

 

2

x

ni 

chetlashtirish 

3 





3

1

3

2

x

x

x

x

 







3

2

1

3

2

1

x

x

x

x

x

x

 

3

2

1

3

2

1

x

x

x

x

x

x





 

 

 

3

2

1

x

x

x

 

 

3

2

1

x

x

x

ni 

chetlashtirish 

4 







3

2

1

3

1

3

2

x

x

x

x

x

x

x

 

3

2

1

3

2

1

x

x

x

x

x

x





 

 

3

2

1

x

x

x

 

3

2

1

x

x

x

ni 

chetlashtirish 

5 





3

1

3

2

x

x

x

x

 

3

2

1

3

2

1

x

x

x

x

x

x





 

 

3

2

1

x

x

x

 

2

x

ni 

chetlashtirish 

6 





3

1

3

2

x

x

x

x

 

3

2

1

3

1

x

x

x

x

x





 

 

3

2

1

x

x

x

 

1

x

ni 

chetlashtirish 

7 





3

1

3

2

x

x

x

x

 

3

2

3

1

x

x

x

x





 

 

 

 

Ikkinchi ko‘rish yangi 

natija bermaydi 

Algoritmning 

ishi tugadi 

 

Masalan, 

8

)

(

1



D

L

h

, 

6

)

(

2



D

L

h

, 

4

)

(

1



D

L

k

, 

3

)

(

2



D

L

k

, 

4

)

(

1



D

L

i

, 

3

)

(

2



D

L

i

 va 

bu  yerdan 

)

(

)

(

2

1

D

L

D

L

h

h



, 

)

(

)

(

2

1

D

L

D

L

k

k



, 

)

(

)

(

2

1

D

L

D

L

i

i



  munosabatlar  kelib 

chiqadi. 

2.3-jadval 

Qadam 

tartib 

raqami 

DNSh va 

ko‘rilayotgan 

tartib 

Tekshiri- 

layotgan 

kon’yunksiya 

Operatsiya 

turi 

1 





2

1

3

3

2

1

x

x

x

x

x

x

 







3

2

1

3

1

2

x

x

x

x

x

x

 

3

2

1

2

1

3

x

x

x

x

x

x





 

 

 

3

2

1

x

x

x

 

 

1

x

ni 

chetlashtirish 

2 





2

1

3

3

2

x

x

x

x

x

 







3

2

1

3

1

2

x

x

x

x

x

x

 

3

2

1

2

1

3

x

x

x

x

x

x





 

 

 

2

1

3

x

x

x

 

 

3

x

ni 

chetlashtirish 

3 





2

1

3

2

x

x

x

x

 







3

2

1

3

1

2

x

x

x

x

x

x

 

3

2

1

2

1

3

x

x

x

x

x

x





 

 

 

3

1

2

x

x

x

 

 

2

x

ni 

chetlashtirish 

4 





2

1

3

2

x

x

x

x

 

 

 

---





3

2

1

3

1

x

x

x

x

x

 

3

2

1

2

1

3

x

x

x

x

x

x





 

 

3

2

1

x

x

x

 

1

x

ni 

chetlashtirish 

5 





2

1

3

2

x

x

x

x

 







3

2

3

1

x

x

x

x

 

3

2

1

2

1

3

x

x

x

x

x

x





 

 

 

2

1

3

x

x

x

 

 

3

x

ni 

chetlashtirish 

6 





2

1

3

2

x

x

x

x

 







3

2

3

1

x

x

x

x

 

3

2

1

2

1

x

x

x

x

x





 

 

 

3

2

1

x

x

x

 

 

3

2

1

x

x

x

ni 

chetlashtirish 

7 





2

1

3

2

x

x

x

x

 

2

1

3

2

3

1

x

x

x

x

x

x







 

 

3

2

x

x

 

 

qo‘llanilmaydi 

8 





2

1

3

2

x

x

x

x

 

2

1

3

2

3

1

x

x

x

x

x

x







 

 

2

1

x

x

 

2

1

x

x

ni 

chetlashtirish 

9 





3

1

3

2

x

x

x

x

 

2

1

3

2

x

x

x

x





 

 

3

1

x

x

 

 

qo‘llanilmaydi 

10 





3

1

3

2

x

x

x

x

 

2

1

3

2

x

x

x

x





 

 

3

2

x

x

 

3

2

x

x

ni 

chetlashtirish 

11 

2

1

3

1

3

2

x

x

x

x

x

x





 

2

1

x

x

 

qo‘llanilmaydi 

12 

2

1

3

1

3

2

x

x

x

x

x

x





 

Algoritmning 

ishi tugadi 

 

“Istalgan 

)

,...,

,

(

2

1

n

x

x

x

f

  funksiya  uchun  biror  tartiblash  oqibatida 

soddalashtirish algoritmini tatbiq etib minimal DNShni hosil etish mumkinmi yoki 

yo‘qmi?” degan savol tug‘iladi. Bu savolga quyidagi teorema javob beradi.