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

 

1.1-t a ’ r i f . Ushbu

 

r

r

i

i

i

x

x

x

K















...

2

2

1

1

 

(

 



 bo‘lganda 





i

i



)

 

(1) 

ifoda  elementar  kon’yunksiya  deb  ataladi. 

r

  son  elementar  kon’yunksiyaning 

rangi deyiladi. Konstanta 1 ni rangi 0 ga teng bo‘lgan elementar kon’yunksiya deb 

hisoblaymiz. 

1.2-t a ’ r i f . Ushbu 

)

 

 

(

1

j

i

i

s

i

K

K

ganda

bo'l

j

i

K

D











 

(2) 

ifoda diz’yunktiv normal shakl (DNSh) deb ataladi, bu yerda 

i

K

– rangi 

i

ga teng

 

bo‘lgan eyementar kon’yunksiya. 

Ma’lumki, 

D

  diz’yunktiv  normal  shakl  mantiq  algebrasining  ma’lum  bir 

)

,...,

,

(

2

1

n

x

x

x

f

  funksiyasini  realizatsiya  qiladi  va  mantiq  algebrasining  berilgan 

funksiyasi bir nechta DNSh ko‘rinishida ifodalanishi mumkin. Mantiq algebrasining 

har  qanday 

)

,...,

,

(

2

1

n

x

x

x

f

 

)

0

(



f

funksiyasini  DNSh  ko‘rinishiga  keltirish 

mumkinligini, ya’ni 

)

,...,

,

(

2

1

n

x

x

x

f

D



 

(3) 

 

Bunday  DNSh  sifatida 

f

  funksiyaning  mukammal  diz’yunktiv  normal 

shaklini (MDNSh) olish mumkin, ya’ni 

n

n

n

n

f

x

x

x

D



















...

2

1

2

1

2

1

2

1

1

)

,...,

,

(

)

,...,

,

(







. 

(4) 

 

 

---

1.1-m i s o l . 

)

,

,

(

3

2

1

x

x

x

f

 funksiya 1.1-chinlik jadvali bilan berilgan bo‘lsin. 

1.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 

0 

1  0  1 

1 

0  1  0 

0 

1  1  0 

1 

0  1  1 

0 

1  1  1 

1 

U holda 

)

,

,

(

3

2

1

x

x

x

f

 funksiya 

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











 

(5) 

MDNSh ko‘rinishida ifodalanishi mumkin. 

Ikkinchi tarafdan, shu funksiyaning o‘zini 

1

3

2

2

x

x

x

D





 

(6) 

DNSh ko‘rinishida ham ifodalash mumkin. 

Agar 

1

D

  bilan 

2

D

  ko‘rinishlarini  taqqoslasak,  u  holda 

1

D

  ifodasida  15ta 

o‘zgaruvchi simvollari va 5ta elementar kon’yunksiyalar qatnashayotganligini, 

2

D

 

ifodasida  esa,  3ta  o‘zgaruvchi  simvollari  va  2ta  elementar  kon’yunksiyalar 

qatnashayotganligini  ko‘ramiz.  Demak, 

2

D

  formula  o‘zgaruvchilar  simvoli 

(elementar  kon’yunksiyalar)  soniga  nisbatan 

1

D

  DNShga  qaraganda  soddaroq 

formula hisoblanadi. 

Agar 

1

D

 va 

2

D

 ko‘rinishdagi funksiyani: 

a) kontaktli sxema orqali realizatsiya qilsak, u holda 

1

D

 DNShni realizatsiya 

qilish uchun 15ta kontakt, 

2

D

 DNShni realizatsiya qilish uchun esa 3ta kontakt talab 

qilinadi; 

b)  nol  taktli  funksional  elementlardan  yasalgan  sxema  orqali  realizatsiya 

qilsak, u holda 

1

D

ni realizatsiya qilish uchun 21 dona funksional element va 

2

D

ni 

realizatsiya qilish uchun 4 dona funksional element sarf bo‘ladi; 

d) bir taktli funksional elementlardan yasalgan ko‘p taktli to‘g‘ri sxema orqali 

realizatsiya  qilish  talab  qilinsa,  u  holda 

1

D

ni  realizatsiya  qilish  uchun  33  dona 

funksional  element,  shu  jumladan,  12  dona  ushlab  turish  elementi  va 

2

D

ni 

realizatsiya qilish uchun 6 dona, shu jumladan, 2 dona ushlab turish elementi kerak 

bo‘ladi. 

Demak, 

1

D

  DNShni  realizatsiya  qiladigan  sxemaning  (qanday  sxema 

bo‘lishidan  qat’iy  nazar)  tannarxi 

2

D

  DNShni  realizatsiya  qiladigan  sxemaning 

tannarxidan ancha qimmat (ortiq) turadi. ■ 

1.1-misoldan  ko‘rinib  turibdiki,  mantiq  algebrasining  funksiyalarini 

minimallashtirish muammosi ko‘pchilik hollarda (jumladan, xalq xo‘jaligi uchun) 

katta amaliy ahamiyatga egadir. 

---

Bu masalani hal qilish uchun DNShning “murakkabligini” ifodalovchi 

)

(

D

L

 

soddalik indeksi

 tushunchasini kiritamiz. 

)

(

D

L

 funksional uchun quyidagi aksiomalarning bajarilishini talab qilamiz. 

I. Manfiy emasligi haqidagi aksioma. 

Har qanday DNSh uchun 

0

)

(



D

L

. 

II.  Monotonligi  haqidagi  aksioma

  (ko‘paytmaga  nisbatan).  Agar 

1

1

K

x

D

D

i

i







 bo‘lsa, u holda 

)

(

)

(

1

1

K

D

L

D

L





. 

(7) 

III. Qavariqligi haqidagi aksioma

 (qo‘shishga nisbatan). Agar 

2

1

D

D

D





 

va 

0

2

1





D

D

 bo‘lsa, u holda 

)

(

)

(

)

(

2

1

D

L

D

L

D

L





. 

(8) 

IV. Invariantlik haqidagi aksioma

 (izomorfizmga nisbatan). Agar 

1

R

 DNSh 

R

  DNShdan  o‘zgaruvchilarni  qayta  nomlash  (aynan  tenglashtirishsiz)  usuli  bilan 

hosil qilingan bo‘lsa, u holda 

).

(

)

(

1

D

L

D

L



 

Diz’yunktiv  normal  shakllar  uchun 

soddalik  indekslari

  deb  ataluvchi 

quyidagi belgilashlarni kiritamiz. 

1. 

)

(

D

L

h

 – berilgan 

D

 DNShdagi o‘zgaruvchilar harflarining soni. 

2. 

)

(

D

L

k

 – berilgan 

D

 DNShdagi elementar kon’yunksiyalar soni. 

3. 

)

(

D

L

i

 – berilgan 

D

 DNShdagi inkor (



) simvollari soni. 

)

(

D

L

h

, 

)

(

D

L

k

  va 

)

(

D

L

i

  indekslar  yuqorida  keltirilgan  aksiomalarni 

qanoatlantiradi. 

1.2-m i s o l .

  1.1-misoldagi 

1

D

 

va 

2

D

  DNShlar  berilgan  bo‘lsin.  Ravshanki, 

15

)

(

1



D

L

h

 va 

3

)

(

2



D

L

h

, ya’ni 

2

D

 DNSh o‘zgaruvchilar harflarining soni indeksiga 

nisbatan 

1

D

 DNShga qaraganda soddaroqdir. 

1

D

 

va 

2

D

 DNShlar uchun 

5

)

(

1



D

L

k

 va 

2

)

(

2



D

L

k

  bo‘lgani  uchun 

2

D

  DNSh  elementar  kon’yunksiyalar  soni  indeksiga 

nisbatan ham 

1

D

 DNShga qaraganda soddaroqdir. 

6

)

(

1



D

L

i

 va 

2

)

(

2



D

L

i

, ya’ni 

2

D

 

DNSh inkor simvollari soni indeksi uchun ham 

1

D

 DNShga nisbatan soddaroq ekan. 

■ 

Ma’lumki, 

}

,...,

,

{

2

1

n

x

x

x

  o‘zgaruvchilar  to‘plamidan 

n

3

ta  elementar 

kon’yunksiya  tuzish  mumkin  (“bo‘sh”  kon’yunksiyaga  1  konstanta  mos  qilib 

qo‘yilgan).  Bundan  o‘z  navbatida 

}

,...,

,

{

2

1

n

x

x

x

  to‘plam  elementlaridan 

n

3

2

ta 

diz’yunktiv normal shakl tuzish mumkinligi kelib chiqadi.