Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

3. Minimallashtirish masalasining geometrik tarzda qo‘yilishi

3.1. Birlik kub va uning elementlariga mos keladigan funksiya. Hamma

{₁, ₂ ,...,_n}
majmua to‘plamini E ⁿ
bilan belgilaymiz. E ⁿ
to‘plamni birlik kubning

hamma uchlari to‘plami sifatida qarash mumkin. Shu sababli E ⁿ to‘plam ⁿ o‘lchovli

kub, {₁, ₂ ,...,_n}
esa kub uchlari deb ataladi.

n  3 o‘lchovli kub 3.1-shakldagidek tasvirlanishi mumkin.

3.1 - t a ’ r i f .

_i ,_i ,...,_i
shunday 0 va 1 sonlardan iborat tayinlangan sonlar

1 2 r

sistemasi bo‘lib,
1  i₁  i₂  ...  i_r  n , uchun _i  _i , _i  _i ,..., _i  _i
bajarilganda

1 1 2 2 r r

E ⁿ kubning uchlaridan tuzilgan to‘plam
(n  r)
o‘lchovli yoq deb ataladi.

Mantiq algebrasining
f (x₁ , x₂
,..., x_n )
funksiyasi berilgan bo‘lsin. E ⁿ
kubning

f (₁, ₂ ,...,_n )  1
shartni qanoatlantiradigan barcha uchlaridan tashkil topgan

to‘plamni N _f
bilan belgilaymiz, ya’ni
f (₁, ₂ ,...,_n )  1
bajarilganda va faqat

shunda
(₁,₂ ,...,_n )  N _f , bo‘ladi. Masalan, 2-bo’limdagi 2.1-jadvalda berilgan

f (x₁, x₂ , x₃ )
funksiyaga
N_f


 {(0,0,0), (0,0,1), (0,1,1), (1,0,0), (1,1,0), (1,1,1)}

to‘plam mos keladi.

Ravshanki,
N  Eⁿ . Agar N
to‘plam berilgan bo‘lsa, u holda unga mos f

f

f
funksiyaning analitik ko‘rinishini yozish mumkin.

1. 
   - m i s o l . Quyidagi to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi topamiz:
   

f
N  {(0, 0, 0),(1, 0, 0),(1, 0,1)};
1

f
N  {(1,1,1),(1,1, 0),(1, 0,1),(0, 0,1)}.
2
Berilgan to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi



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

quyidagicha bo‘ladi:
f₁ (x₁, x₂ , x₃ )  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃ ;
f₂ (x₁, x₂ , x₃ )  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃ . ■

Shunday qilib, N _f
to‘plam berilgan bo‘lsa, u holda unga mos f funksiyani,

f (x₁, x₂ ,..., x_n )
funksiya berilganda esa, N _f
to‘plamni topish mumkin.

Dastlabki funksiya sifatida r rangli
k(x , x ,..., x )  x^1 x^2 ... x^r
elementar

kon’yunksiyani olaylik.
1 2 n
i₁ i₂ i_r

2. 
   - t a ’ r i f . K kon’yunksiyaga mos N_k
   

ataladi.
to‘plam r rangli interval deb

^{O’z-o‘zidan ravshanki,} r ^rangli N ^{interval (n  r) o‘lchovli yoqni ifodalaydi.}

2. - m i s o l .

k₁ (x₁, x₂ , x₃ )  x₂ x₃ ,
k₂ (x₁, x₂ , x₃ )  x₁ x₂ ,


k₃ (x₁, x₂ , x₃ )  x₁

kon’yunksiyalarga
N  {(1,1,1),(0,1,1)},

k
1
N  {(0, 0, 0),(0, 0,1)},

k
2

k
N  {(0, 0, 0),(0,1, 0),(0, 0,1),(0,1,1)} intervallar mos keladi. Bu intervallar mos ravishda
3
2, 2 va 1 rangli, hamda va 1 o‘lchovli yoq (qirra), 1 o‘lchovli yoq (qirra) va 2 o‘lchovli yoqdir. ■

Agar
f (x₁, x₂ ,..., x_n )  g(x₁, x₂ ,..., x_n )  h(x₁, x₂ ,..., x_n )
bo‘lsa, u holda

1. 
   N_g  N _f , N_h  N _f ;
   

2. 
   N _f
   

bo‘ladi.
 N_g ∪ N_h

Umuman olganda, agar
f (x₁, x₂ ,..., x_n )  D
va D  K₁  K₂  ...  K_s
bo‘lsa, u

holda yuqoridagi xossalarga asosan
N  N

k

f
i
(i  1,2,..., s) va
N  N

f

k
1
∪ N

k
2
∪... ∪ N ,

k
s

1 2 s
ya’ni ^f funksiyaga N _f to‘plamning ^N_k , ^N_k , ... , ^N_k intervallardan iborat qobiq

1 2 s
mos keladi va har bir ^N_k , ^N_k ,..., ^N_k intervallardan iborat N _f
to‘plamning

qobig‘iga D diz’yunktiv normal shaklda ifodalangan f funksiya mos keladi.

Demak, mantiq algebrasining har bir
f (x₁, x₂ ,..., x_n )
funksiyasiga bitta N _f

to‘plamning
N_k ,N_k ,..., N_k intervallardan (N_k
 N _f )
iborat qobig‘i va, aksincha, har

1 2 n j

bir N _f
to‘plamning
N_k ,N_k ,..., N_k
intervallardan iborat qobig‘iga bitta
f (x₁, x₂ ,..., x_n )

1 2 n

funksiya mos keladi, ya’ni N _f
ning qobig‘i bilan
f (x₁, x₂ ,..., x_n )
funksiya o‘rtasida

o‘zaro bir qiymatli moslik bor.

2. 
   - m i s o l . 2-bo’limdagi 2.1-jadval bilan berilgan
   

f (x₁ , x₂ , x₃ )

funksiya

uchun


D₁  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃ ,


D₂  x₂ x₃  x₁

diz’yunktiv normal shakllar topilgan edi. Bu DNShlarga
N_f  {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)} to‘plamning quyidagi ikkita qoplamasi mos

keladi:



k k
N_f  N_k ∪ N_k ∪ N_k ∪ N_k ∪ N_k , ^N _f ^{ N} ₁ ^{∪ N} ₂ ^,

1 2 3 4 5 _{0 0}

bu yerda
N  {(0,0,0)},

k
1
N  {(1,0,0)},

k
2
N  {(1,0,1)},

k
3
N  {(1,1,0)} ,

k
4
N  {(1,1,1)},

k
5

k
N ₀  {(0,0,0), (1,0,0)},
1
N ₀  {(1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Birinchi qoplama beshta

k
2

i
nuqtadan, ikkinchisi esa qirra va ikki o‘lchovli yoqdan iborat. N_k intervalning rangi

r_i bo‘lsin (u
K_i kon’yunksiyaning rangiga teng). U holda

_s

r  _r_i
i 1
(4)

qoplamaning rangi deb ataladi.
3.2. Mantiq algebrasi funksiyasini minimallashtirish muammosiga ekvivalent qoplamalar haqidagi geometrik masala. Mantiq algebrasi funksiyasi f (x₁, x₂ ,..., x_n ) ni minimallashtirish (minimizasiyalash) muammosiga ekvivalent bo‘lgan qoplamalar haqidagi geometrik masala quyidagicha qo‘yiladi. Berilgan

N_f  N_k ∪ N_k ∪... ∪ N_k to‘plamning N_k , N_k ,..., N_k ( N_k
 N _f ,
j  1,2,..., s )

1 2 s 1 2 s j
intervallardan iborat shunday qobig‘ini topish kerakki, uning r rangi eng kichik bo‘lsin, ya’ni qaralayotgan masala

topish masalasiga keladi.

_s

min r  min_r_i
i 1
(5)

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.

4.