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

3. Minimallashtirish masalasining geometrik tarzda qo‘yilishi 

3.1. Birlik kub va uning elementlariga mos keladigan funksiya.

 Hamma 

}

,...,

,

{

2

1

n







 

majmua to‘plamini 

n

E

 bilan belgilaymiz. 

n

E

 to‘plamni birlik kubning 

hamma uchlari to‘plami sifatida qarash mumkin. Shu sababli 

n

E

 to‘plam 

n

 

o‘lchovli 

kub

, 

}

,...,

,

{

2

1

n







 esa

 kub uchlari

 deb ataladi. 

3



n

 o‘lchovli kub 3.1-shakldagidek tasvirlanishi mumkin. 

3.1 - t a ’ r i f .

 

r

i

i

i







,...,

,

2

1

 shunday 0 va 1 sonlardan iborat tayinlangan sonlar 

sistemasi bo‘lib, 

n

i

i

i

r











...

1

2

1

,  uchun 

r

r

i

i

i

i

i

i



















,...,

,

2

2

1

1

 bajarilganda 

n

E

 kubning uchlaridan tuzilgan to‘plam 

)

(

r

n



 o‘lchovli yoq deb ataladi. 

Mantiq algebrasining 

)

,...,

,

(

2

1

n

x

x

x

f

 funksiyasi berilgan bo‘lsin. 

n

E

 kubning 

1

)

,...,

,

(

2

1



n

f







  shartni  qanoatlantiradigan  barcha  uchlaridan  tashkil  topgan 

to‘plamni 

f

N

  bilan  belgilaymiz,  ya’ni 

1

)

,...,

,

(

2

1



n

f







  bajarilganda  va  faqat 

shunda 

f

n

N



)

,...,

,

(

2

1







,  bo‘ladi.  Masalan,  2-bo’limdagi  2.1-jadvalda  berilgan 

)

,

,

(

3

2

1

x

x

x

f

 

funksiyaga 

)}

1

,

1

,

1

(

),

0

,

1

,

1

(

),

0

,

0

,

1

(

),

1

,

1

,

0

(

),

1

,

0

,

0

(

),

0

,

0

,

0

{(



f

N

 

to‘plam mos keladi. 

Ravshanki, 

n

f

E

N



. Agar 

f

N

 to‘plam berilgan bo‘lsa, u holda unga mos 

f

 

funksiyaning analitik ko‘rinishini yozish mumkin. 

3.1 - m i s o l .

 Quyidagi to‘plamlarga mos keladigan funksiyalarning analitik 

ko‘rinishi topamiz: 

)}

1

,

0

,

1

(

),

0

,

0

,

1

(

),

0

,

0

,

0

{(

1



f

N

; 

)}

1

,

0

,

0

(

),

1

,

0

,

1

(

),

0

,

1

,

1

(

),

1

,

1

,

1

{(

2



f

N

. 

Berilgan to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi 

                                           

1

 Яблонский С.В. Введение в дискретную математику. М.: Наука. 1979. 213- sahifaga qarang. 

---

quyidagicha bo‘ladi: 

3

2

1

3

2

1

3

2

1

3

2

1

1

)

,

,

(

x

x

x

x

x

x

x

x

x

x

x

x

f







; 

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

2

)

,

,

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f









. ■ 

Shunday qilib, 

f

N

 to‘plam berilgan bo‘lsa, u holda unga mos 

f

 funksiyani, 

)

,...,

,

(

2

1

n

x

x

x

f

 funksiya berilganda esa, 

f

N

 to‘plamni topish mumkin. 

Dastlabki  funksiya  sifatida 

r

  rangli 

r

r

i

i

i

n

x

x

x

x

x

x

k







...

)

,...,

,

(

2

2

1

1

2

1



  elementar 

kon’yunksiyani olaylik. 

3.2 - t a ’ r i f .

 

K

  kon’yunksiyaga  mos 

k

N

  to‘plam 

r

  rangli  interval  deb 

ataladi. 

O’z-o‘zidan ravshanki, 

r

 rangli 

N

 interval 

)

(

r

n



 o‘lchovli yoqni ifodalaydi. 

3.2 - m i s o l .

 

3

2

3

2

1

1

)

,

,

(

x

x

x

x

x

k



, 

2

1

3

2

1

2

)

,

,

(

x

x

x

x

x

k



, 

1

3

2

1

3

)

,

,

(

x

x

x

x

k



 

kon’yunksiyalarga 

)}

1

,

1

,

0

(

),

1

,

1

,

1

{(

1



k

N

, 

)}

1

,

0

,

0

(

),

0

,

0

,

0

{(

2



k

N

, 

)}

1

,

1

,

0

(

),

1

,

0

,

0

(

),

0

,

1

,

0

(

),

0

,

0

,

0

{(

3



k

N

 intervallar mos keladi. Bu intervallar mos ravishda 

2,  2  va  1  rangli,  hamda  va  1  o‘lchovli  yoq  (qirra),  1  o‘lchovli  yoq  (qirra)  va  2 

o‘lchovli yoqdir. ■ 

Agar 

)

,...,

,

(

)

,...,

,

(

)

,...,

,

(

2

1

2

1

2

1

n

n

n

x

x

x

h

x

x

x

g

x

x

x

f





 

bo‘lsa, u holda 

1) 

f

g

N

N



, 

f

h

N

N



; 

2) 

h

g

f

N

N

N





 

bo‘ladi. 

Umuman  olganda,  agar 

D

x

x

x

f

n



)

,...,

,

(

2

1

  va 

s

K

K

K

D









...

2

1

  bo‘lsa,  u 

holda yuqoridagi xossalarga asosan 

f

k

N

N

i



 

)

,...,

2

,

1

(

s

i



 va

 

s

k

k

k

f

N

N

N

N







...

2

1



, 

ya’ni 

f

 funksiyaga 

f

N

 to‘plamning 

N

k

1

, 

N

k

2

, ... ,

N

k

s

 intervallardan iborat 

qobiq 

1- shakl  

 

 

 

 

 

 

 

 

 

 

 

---

mos  keladi  va  har  bir 

N

k

1

, 

N

k

2

,...,

N

k

s

  intervallardan  iborat 

f

N

  to‘plamning 

qobig‘iga 

D

 diz’yunktiv normal shaklda ifodalangan 

f

 funksiya mos keladi. 

Demak,  mantiq  algebrasining  har  bir 

)

,...,

,

(

2

1

n

x

x

x

f

  funksiyasiga  bitta 

f

N

 

to‘plamning 

n

k

k

k

N

N

N

...,

,

,

2

1

 intervallardan 

)

(

f

k

N

N

j



 iborat qobig‘i va, aksincha, har 

bir 

f

N

 to‘plamning 

n

k

k

k

N

N

N

...,

,

,

2

1

 intervallardan iborat qobig‘iga bitta 

)

,...,

,

(

2

1

n

x

x

x

f

 

funksiya mos keladi, ya’ni 

f

N

 

ning qobig‘i bilan 

)

,...,

,

(

2

1

n

x

x

x

f

 

funksiya o‘rtasida 

o‘zaro bir qiymatli moslik bor.