Alisher navoiy nomidagi samarqand davlat universiteti mexanika-matematika fakulteti

 
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. 
 
Minimallashtirish masalasining geometrik tarzda qo‘yilishi 
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 
                                                
29
 Яблонский С.В. Введение в дискретную математику. М.: Наука. 1979. 213- sahifaga qarang. 

 
 
 
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 1- shakldagidek tasvirlanishi mumkin. 
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, ushbu bobning 2- paragrafidagi 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. 
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 
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. 
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. 

 
 
 
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 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. 
3 -   m i s o l .  Ushbu  bobning 2- paragrafidagi 1-  jadval  bilan  berilgan 
)
,
,
(
3
2
1
x
x
x
f
 funksiya 
uchun 
3
2
1
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
x
x
x
D





, 
1
3
2
2
x
x
x
D


 
diz’yunktiv normal shakllar topilgan edi. Bu DNShlarga 
)}
1
,
1
,
1
(
),
0
,
1
,
1
(
),
1
,
0
,
1
(
),
0
,
0
,
1
(
),
0
,
0
,
0
{(

f
N
 
to‘plamning quyidagi ikkita qoplamasi mos keladi: 
1- shakl 
1
x
)
0
,
0
,
0
(
 
2
x
)
0
,
0
,
1
(
)
0
,
1
,
1
(
)
0
,
1
,
0
(
)
1
,
0
,
0
(
3
x  
)
1
,
1
,
0
(
)
1
,
1
,
1
(
 
)
1
,
0
,
1
(

 
 
 
5
4
3
2
1
k
k
k
k
k
f
N
N
N
N
N
N





, 
,
2
0
1
0
k
k
f
N
N
N


 
bu  yerda 
)}
0
,
0
,
0
{(
1

k
N
, 
)}
0
,
0
,
1
{(
2

k
N
, 
)}
1
,
0
,
1
{(
3

k
N
, 
)}
0
,
1
,
1
{(
4

k
N
, 
)}
1
,
1
,
1
{(
5

k
N
, 
)}
0
,
0
,
1
(
,
)
0
,
0
,
0
{(
0
1

k
N
, 
)}
1
,
1
,
1
(
,
)
0
,
1
,
1
(
,
)
1
,
0
,
1
(
,
)
0
,
0
,
1
{(
0
2

k
N
.  Birinchi  qoplama  beshta  nuqtadan, 
ikkinchisi  esa  qirra  va  ikki  o‘lchovli  yoqdan  iborat.  N
k
i
  intervalning  rangi 
i
r   bo‘lsin  (u 
i
K  
kon’yunksiyaning rangiga teng). U holda 
r
r
i
i
s



1
 
   
(4) 
qoplamaning rangi deb ataladi. 
Mantiq  algebrasi  funksiyasini  minimallashtirish  muammosiga  ekvivalent  qoplamalar 
haqidagi  geometrik  masala.  Mantiq  algebrasi  funksiyasi 
)
,...,
,
(
2
1
n
x
x
x
f
ni  minimallashtirish 
(minimizasiyalash)  muammosiga  ekvivalent  bo‘lgan  qoplamalar  haqidagi  geometrik  masala 
quyidagicha  qo‘yiladi.  Berilgan 
s
k
k
k
f
N
N
N
N



...
2
1

  to‘plamning 
s
k
k
k
N
N
N
,...,
,
2
1
  (
f
k
N
N
j

, 
s
j
,...,
2
,
1

)  intervallardan  iborat  shunday  qobig‘ini  topish  kerakki,  uning 
r   rangi  eng  kichik 
bo‘lsin, ya’ni qaralayotgan masala 
min
min
r
r
i
i
s



1
 
 
 
(5) 
topish masalasiga keladi. 
Demak,  mantiq  algebrasi  funksiyasini  minimallashtirish  masalasini  ikki  formada  ko‘rish 
mumkin:  birinchisi  –  analitik  formada,  ikkinchisi  –  geometrik  formada.  Shuning  uchun  adabiyotda 
ikki  til  ishlatiladi:  analitik  va  geometrik.  Ayrim  hollarda  ikki  tilning  kombinatsiyasidan 
foydalaniladi. Masalan, kon’yunksiyani interval va DNShni qoplama deb ataydilar. 
 
Joiz (ruxsat etilgan) kon’yunksiyalar 
Joiz  kon’yunksiya  tushunchasi.  Ma’lumki, 
n
x
x
x
,...,
,
2
1
  o‘zgaruvchilardan 
n
3 ta  elementar 
kon’yunksiya  va 
2
3
n
ta  diz’yunktiv  normal  shakl  tuzish  mumkin.  Masalan, 
3

n
  bo‘lsa,  ya’ni 
3
2
1
,
,
x
x
x
 o‘zgaruvchilardan 
1
, 
1
x , 
2
x , 
3
x  
1
x
, 
2
x
, 
3
x
, 
2
1
x
x
, 
3
1
x
x
, 
3
2
x
x
, 
2
1
x
x
, 
2
1
x
x
, 
3
1
x
x
, 
3
1
x
x
 
3
2
x
x
, 
3
2
x
x
, 
2
1
x
x
, 
3
1
x
x
, 
3
2
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
(1) 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
 
elementar  kon’yunksiya  tuzish  mumkin.  Ammo,  bu  elementar  kon’yunksiyalarning  hammasi  ham 
berilgan  ixtiyoriy 
)
,
,
(
3
2
1
x
x
x
f
  funksiyani  realizasiya  qiladigan  diz’yunktiv  normal  shakllarning 
ifodasida  ishtirok etavermaydi. Shuning uchun  “
n
3 ta kon’yunksiyalarning qaysilari 
)
,...,
,
(
2
1
n
x
x
x
f
 
funksiyaning  DNShda  ishtirok  qiladi?”  degan  masalani  yechishga  to‘g‘ri  keladi.  Buning  uchun, 
birinchi  navbatda, 
f
n
N
E \
  to‘plamning  elementlarida  1  qiymat  qabul  qiladigan  kon’yunksiyalarni 
topish kerak bo‘ladi. Masalan, 
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
f






)
,
,
(
1
 
(2) 
bo‘lsin. U holda 

 
 
 
)}
1
,
1
,
1
(
),
0
,
1
,
1
(
),
1
,
0
,
1
(
),
0
,
1
,
0
(
),
1
,
1
,
0
(
),
0
,
0
,
0
{(
1

f
N
 
(3) 
bo‘ladi. Demak, 1- jadvalga ega bo‘lamiz. 
1- jadval 
Е
N
n
f
\
1
  1 qiymat qabul qiladigan kon’yunksiyalar 
(0,0,0) 
z
y
x
z
y
z
x
y
x
z
y
x
,
,
,
,
,
,
,
1
 
(0,0,1) 
z
y
x
z
y
z
x
y
x
z
y
x
,
,
,
,
,
,
,
1
 
Ikkinchi 
navbatda, 
(1) 
kon’yunksiyalar 
orasidan 
1-jadvaldagi 
kon’yunksiyalarni 
chetlashtiramiz,  chunki 
)
,
,
(
z
y
x
f
  funksiyaga  N
f
1
  ((3)ga  qarang)  to‘plam  mos  kelgani  uchun  1-
jadvaldagi kon’yunksiyalar (2) funksiyani realizasiya qiladigan diz’yunktiv normal shakllar ifodasida 
umuman qatnashmaydi. Bu operatsiya natijasida 
)
,
,
(
1
z
y
x
f
 funksiyani realizasiya qiladigan DNShlar 
ifodasida  qatnashishi  mumkin  bo‘lgan  (qatnashishga  ruxsat  etilgan,  qatnashishga  joiz) 
kon’yunksiyalarga ega bo‘lamiz: 
x , 
y
, 
xy
, 
xz , 
y
x , 
z
x
, 
yz
, 
y
x ,  z
y , 
xyz
, 
z
xy , 
(4) 
yz
x
, 
z
y
x
, 
z
y
x
, 
z
y
x
. 
Shunday qilib, 
27
3
3

 kon’yunksiyadan 15tasining berilgan 
)
,
,
(
z
y
x
f
 funksiyani realizasiya 
qiladigan DNShlar ifodasida qatnashishi joiz ekan. 
1 -   t a ’ r i f .   Ixtiyoriy 
)
,...,
,
(
2
1
n
x
x
x
f
  funksiya  va  unga  mos 
f
N
  to‘plam  berilgan  bo‘lsin. 
)
,...,
,
(
2
1
n
x
x
x
f
  funksiyani  realizasiya  qiladigan  DNShlar  ifodasida  qatnashishi  mumkin  bo‘lgan 
kon’yunksiyalar, ya’ni 
f
n
N
E \
 to‘plamning nuqtalarida 1 qiymatga ega bo‘lgan kon’yunksiyalardan 
tashqari qolgan hamma kon’yunksiyalar joiz kon’yunksiyalar deb ataladi. 
Masalan, (4) dagi hamma kon’yunksiyalar joiz kon’yunksiyalar bo‘ladi. 
Joiz kon’yunksiyalarni topish. 
M i s o l .  Berilgan 
 
 



3
2
1
3
2
1
3
2
1
2
)
,
,
(
x
x
x
x
x
x
x
x
x
f
 
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x




 
(5) 
va unga mos   
 
)}
0
,
1
,
0
(
),
0
,
1
,
1
(
),
1
,
1
,
1
(
),
1
,
0
,
1
(
),
1
,
0
,
0
(
),
0
,
0
,
0
{(
2

f
N
 
(6) 
to‘plam berilgan bo‘lsin. 
Joiz kon’yunksiyalarni topish uchun 2- jadvalni tuzamiz. 
2- jadval 
f
n
N
E \
 
1 qiymat qabul qiladigan kon’yunksiyalar 
)
0
,
0
,
1
(
 
3
2
1
3
2
3
1
2
1
3
2
1
,
,
,
,
,
,
,
1
x
x
x
x
x
x
x
x
x
x
x
x
 
)
1
,
1
,
0
(
 
3
2
1
3
2
3
1
2
1
3
2
1
,
,
,
,
,
,
,
1
x
x
x
x
x
x
x
x
x
x
x
x
 
U holda (1) dagi kon’yunksiyalardan 2- jadvaldagi kon’yunksiyalarni chetlashtirish natijasida 
quyidagi joiz kon’yunksiyalarga ega bo‘lamiz: 
2
1
x
x
, 
3
1
x
x
, 
3
2
x
x
, 
3
2
x
x
, 
2
1
x
x
, 

 
 
 
3
1
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
(7) 
3
2
1
x
x
x
, 
3
2
1
x
x
x
, 
3
2
1
x
x
x
. ■ 
O’zgaruvchilar  soni 
n ta  bo‘lganda, 
n
3   ta  kon’yunksiya  va  ulardan  2
3
n
ta 
)
,...,
,
(
2
1
n
x
x
x
f
 
funksiyani  realizasiya  qilishi  mumkin  bo‘lgan  DNSh  tuzish  mumkinligini  aytgan  edik.  Demak, 
berilgan ixtiyoriy 
)
,...,
,
(
2
1
n
x
x
x
f
 funksiyani realizasiya qiladigan tupikli (minimal) DNShlarni 
2
3
n
ta 
DNShlar  orasidan  izlamasdan,  balki 

2   DNShlar  ichidan  izlash  kerak  degan  natijaga  keldik,  bu 
yerda 
  – joiz kon’yunksiyalar soni.