Ma’ruza: Formulalarni minimallashtirish usullari. Reja: Qisqartirilgan diz’yunktiv normal shaklni yasash algoritmi

keltirilmaydigan qoplamalari 

deb ataladi.

N

f

to‘plamning

2

Shunday qilib,

2

3

5

6

1

4

6

k

k

k

k

k

k

k

1

2

5

6

k

k

k

k

1)  

N  

,

N  

,

N 

,

N 

; 2) 

N 

,

N 

,

N 

; 3) 

N 

,

N 

,

N 

,

N

;

4) 

N

k 

,

N

k 

,

N

k 

; 5) 

N

k 

,

N

k 

,

N

k

,

N

k

2

3

5

2

3

4

6

(4)

qobiqlar

N

f

to‘plamning keltirilmaydigan qoplamalari bo‘ladi. ■

2

k

k

k

1

2

m

1 - t a ’ r i f . Agar 

N 

,

N 

,...,

N

maksimal intervallardan iborat qobiq uning

tarkibidan  istalgan  maksimal  intervalni   

(

N

k

,

j



1,2,...,

m

)

chetlashtirganimizda,

j

qolgan qismi

N

f

ning qobig‘i bo‘la olmasa, u holda bu qobiq

keltirilmaydigan qoplami deb ataladi.

N

f

to‘plamning

2

2 - t a ’r i f . 

N

f

to‘plamning keltirilmaydigan qobig‘iga mos bo‘lgan DNSh

tupikli diz’yunktiv normal shakl deb ataladi (geometrik ma’noda).

2 - m i s o l . 

1- misoldagi 

N

f

to‘plamning (4) da ifodalangan

2

keltirilmaydigan qobiqlariga mos

D

1  



x

1

x

2  



x

1

x

3 



x

2

x

3

,

D

2 



x

2 

x

2 



x

1

x

2 



x

1

x

3

,

D

3 



x

1

x

2 



x

2 

x

3 



x

1

x

2 



x

2 

x

3 

, 

D

4 



x

1

x

2 



x

1

x

3 



x

1

x

2 



x

1

x

3 

, (5)

D

5 



x

2 

x

3 



x

1 

x

3 



x

2 

x

3 



x

1

x

3

DNShlar 

f 

2

funksiyaning tupikli diz’yunktiv normal shakllari bo‘ladi. ■

---

T e o r e m a . I va II almashtirishlarga nisbatan tupikli DNSh tushunchasi

bilan geometrik ma’nodagi tupikli DNSh tushunchasi ekvivalentdir.

2.2. MDNSh asosida minimal DNSh yasash jarayonining sxemasi.

Yuqorida ta’riflangan qisqartirilgan, tupikli va minimal DNShlar quyidagi

munosabatda bo‘ladi.

Tupikli DNSh qisqartirilgan DNShdan ayrim kon’yunksiyalarni chetlashtirish

yo‘li bilan hosil qilinadi.

L

h 

ga nisbatan minimal DNSh tupikli bo‘ladi.

Tupikli DNShlar orasida 

L

h 

ga nisbatan minimal DNShlar mavjud bo‘ladi.

3 - m i s o l .

Ushbu bobning 4- paragrafidagi misolda (5) formula bilan

berilgan

f

2 

(

x

1

, 

x

2 

, 

x

3 

) 



x

1 

x

2 

x

3 



x

1 

x

2 

x

3





x

1 

x

2 

x

3 



x

1

x

2 

x

3 



x

1

x

2 

x

3 



x

1

x

2

x

3

funksiyaning 

D

s 

( 

f

2 

) 

qisqartirilgan DNShni topdik (6- paragrafdagi (1) ga qarang):

D

s 

( 

f

2 

) 



x

1

x

2 



x

1

x

3 



x

1 

x

2 



x

2 

x

3 



x

1 

x

3 



x

2 

x

3

.

Undan keyin (5) da ifodalangan tupikli DNShlarni hosil qildik. U yerdan

ko‘rinib turibdiki,

L

h

(

D

1

)



L

h

(

D

2

)



6

va

L

h

(

D

3

)



L

h

(

D

4

)



L

h

(

D

5

)



8

.

Demak,

D

1



x

1

x

2



x

1

x

3



x

2

x

3

va

D

2



x

2

x

3



x

1

x

2



x

1

x

3

tupikli DNShlar

f

2

(

x

1

,

x

2

,

x

3

)

funksiyaning minimal diz’yunktiv normal shakllari

bo‘ladi. Ravshanki, bu DNShlar o‘z navbatida

f

2

(

x

1

,

x

2

,

x

3

)

ning eng qisqa DNShlari

ham bo‘ladi.

---

MDNSh asosida minimal DNSh yasash jarayonining sxemasi 1- shaklda

ifodalangan.

3. Tupikli diz’yunktiv normal shakllarni yasash algoritmi

3.1. Tupikli diz’yunktiv normal shakllarni yasash algoritmi. 

Hamma  

tupikli DNShlarni topishning geometrik g‘oyalarga asoslangan algoritmini

keltiramiz. 

N

to‘plamning hamma maksimal intervallar sistemasi

N 

0 

, 

N 

0 

,...,

N 

0

f

k

1

k

2

k

m

bo‘lsin. 

N

f  



{

P

1

, 

P

2 

,..., 

P



} 

va 

P

0 



N 

f 

ixtiyoriy nuqta hamda 

f 

funksiya aynan 1ga  teng 

bo‘lmagan funksiya bo‘lsin. 1- jadvalni tuzamiz,











0

0

1,  agar 

P



N

bo'lsa ( 

j 



0,1,....,



),



0, agar 

P



N

bo'lsa (

i 



1,....,

m

),

i

k

i

j

k

j

ij

bu yerda 1- jadvalning

P

0

ga mos 1- ustuni 0lardan iborat bo‘ladi, chunki

P

0 



N 

f 

. Qolgan har bir ustunida hech bo‘lmaganda bitta 1 mavjud bo‘ladi. Demak,  

birinchi ustun qolgan hamma ustunlardan farq qiladi.

Har bir  

j  

( 

0 



j 





) uchun hamma satrlar raqamlari (nomerlari) to‘plami 

E

j

ni topamiz, bu yerda 

P

j   

ustunda 1 mavjud bo‘ladi. Faraz qilaylik, 

E

j   



{

e

j

1

,

e

j 

2

,...,

e

j



(

j

)

}

1- shakl

Mukammal

Qisqartirilgan

Tupikli

Tupikli

Tupikli

Tupikli

Tupikli

Minimal

DNShlar

---

bo‘lsin. U holda





(

e

j

1



e

j

2



...



e

j



( 

j

)

)

j



1

ifodani tuzamiz va



turdagi

almashtirishni bajaramiz. Bu almashtirish vaqtida 

e

simvolni

buliy qiymatli deb hisoblaymiz.

1-jadval

P

0

P

1

…

P

j

…

P

N

0

k

1



10



11

…



1

j

…



1



… … … … … … …

N

0

k

i



i

0



i

1

…



ij

…



i



… … … … … … …

N

0

k

m



m

0



m

1

…



mj

…



m



Hosil qilingan ifodani

AB



A



A

,

A 



A



A

teng kuchli formulalardan foydalanib soddalashtiramiz. Buning natijasida

 

ifodaning qismi bo‘lgan

 

1

ifodani hosil qilamiz. Ravshanki,

 

1

ifodadagi har bir

qo‘shiluvchi had keltirilmaydigan qobiqni ifodalaydi.

3. 2 .

M i s o l .

Chinlik jadvali 2- jadvaldagidek berilgan

f

(

x

1

,

x

2

,

x

3

)

funksiyani ko‘ramiz.

2- jadval

x

1

x

2

x

3

f

(

x

1

,

x

2

,

x

3

)

x

1

x

2

x

3

f

(

x

1

,

x

2

,

x

3

)

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

Bu funksiya uchun

N

f  



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

to‘plam 6 ta uchdan iborat. Ularni I, II, III, IV, V va VI sonlar bilan belgilaymiz.  

Maksimal intervallari qirralardan iborat, ularni 1, 2, 3, 4, 5 va 6 sonlar bilan

raqamlaymiz (1- shakl). 3- jadvalni tuzamiz.

Bu yerdan 

E

I 



{1,6} 

, 

E

II 



{1,2} 

, 

E

III 



{2,3} 

, 

E

IV 



{3,4}

, 

E

V 



{4,5}

, 

E

VI 



{5,6}

. U

  

(1



6)(1



2)(2



3)(3



4)(4



5)(5



6)



holda



(1



2



6)



(3



2



4)



(5



4



6)



3- jadval

0

I

II III IV V VI

1

0

1

1

0

0

0

0

2

0

0

1

1

0

0

0

3

0

0

0

1

0

0

0

4

0

0

0

0

1

1

0

5

0

0

0

0

1

1

1

6

0

1

0

0

0

0

1

---

1- shakl

Natijada 5 ta keltirilmaydigan qobiqqa va ularga mos kelgan 5ta tupikli DNShga ega

bo‘lamiz:

D

1  



x

1

x

2  



x

2 

x

3  



x

1

x

3

,

D

2  



x

1

x

3 



x

2 

x

3 



x

1 

x

3 



x

2

x

3 

,

D

3  



x

1

x

2  



x

1

x

3 



x

1

x

2 



x

1

x

3 

, 

D

4



x

1

x

2 



x

2 

x

3 



x

1

x

2 



x

2 

x

3

,

D

5  



x

1

x

3 



x

1

x

2 



x

2 

x

3

Bulardan  

D

1 

va

D

5 

minimal DNSh bo‘ladi.■

Yuqorida o‘rganilgan algoritm ko‘p argumentli funksiyalar uchun ko‘p  

mehnat talab qiladi va amalda deyarli ishlatilmaydi.

4. Ayrim yagona tarzda hosil qilinadigan diz’yunktiv normal shakllar

1

6

VI



(1



3



2



3



6



1



2



4



2



4



6)



(5



4



6)





1



3



5



2



3



5



6



1



2



4



5



2



4



5



6





1



3



4



6



2



3



4



6



1



2



4



6



2



4



6





1



3



5



2



3



5



6



1



2



4



5



1



3



4



6



2



4



6

.  

III

3

IV

2

I

4

I

V

5

---

4.1. MDNShdan minimal DNShni hosil qilish jarayoni.

Mukammal

diz’yunktiv normal shakldan minimal diz’yunktiv normal shaklni hosil qilish

jarayonining sxemasini ushbu bobning 8- paragrafidagi 1- shaklda keltirgan edik.

Avval

qisqartirilgan

DNSh

olinadi. Keyin

yagona tarzdagi

jarayon

tarmoqlanishga o‘tadi, ya’ni hamma tupikli DNShlarni yasash jarayoniga o‘tiladi.

Oxiri tupikli DNShlardan minimal DNShlar ajratib olinadi. Bu jarayonning eng og‘ir

qismi tupikli DNShlarni yasash qismidir (tarmoqlanish qismi). Uni ikki holatda

soddalashtirish mumkin.

1.

Tupikli

DNShlar

yasash

jarayonida

qatnashmaydigan

qisqartirilgan

DNShning ayrim hadlarini oldindan chetlashtirish kerak.

Natijada qisqartirilgan DNShning qolgan hadlarini birma-

bir ko‘rish kamayadi.

2.

Qisqartirilgan DNShning ayrim hadlarini shunday

chetlashtirish kerakki, qolgan qismidan hech bo‘lmaganda

bitta minimal DNSh yasash mumkin bo‘lsin. Ushbu qadam

yagona tarzda amalga oshishi maqsadga muvofiq keladi.

Ushbu paragrafda shunday yagona tarzda tupikli

DNShni hosil qilishning ikkita algoritmini keltiramiz.

4.2. Kvayn

1 

diz’yunktiv normal shakli. 

N

k

interval

N

f

to‘plamning maksimal intervali bo‘lsin.

1 -

t a ’r i f .

Agar

N

f

to‘plamning shunday



nuqtasi mavjud bo‘lsaki,





N

k  

va 



nuqta 

N 

f 

ning boshqa maksimal intervallarining elementi bo‘lmasa, u  

holda 

N

k  

maksimal interval 

N 

f 

ning asosiy qismi deb ataladi.

1 

Kvayn Uillard Van O‘rman (Quine Willard Van Orman, 1908-2000) – AQSh faylasufi va mantiqchisi.

1- jadval

x

1

x

2

x

3

f

(

x

1

,

x

2

,

x

3

)

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

---

1 - m i s o l .

1- jadvalda berilgan 

f

(

x

1

,

x

2

,

x

3

)

funksiyani ko‘raylik. 1- shaklda

N 

f 

to‘plam va uning 

N

1 

, 

N

2 

, 

N

3 

maksimal intervallari (qirralari) aks ettirilgan. Bu  

yerda  

N

1  



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

,  

N

2  



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

va 

N

3



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

. 

(0,0,0)

nuqta faqat

N

1  

interval bilan, 

(1,1,1)  

nuqta esa faqat 

N

3  

interval bilan qoplanganligi ko‘rinib

turibdi. Demak, 

N

1 

va 

N 

3 

maksimal intervallar

bo‘ladi.

N 

f 

to‘plamning asosiy qismlari

2 -

t a ’r i f .

N

f

to‘plamning hamma asosiy qismlaridan (yoqlaridan)

tuzilgan to‘plam yadro deb ataladi.

1- misolda keltirilgan

{

N

1

,

N

3

}

to‘plam yadro bo‘lishi ravshan. Yadro har bir

keltirilmaydigan qobiqqa kiradi. Bu yerdan yadro bilan qoplanadigan yoq (qirra)

hech bir keltirilmaydigan qobiqqa kirmasligi kelib chiqadi.

3 - t a ’ r i f . Yadro bilan qoplangan maksimal yoqlarga (qirralarga) mos

keladigan hamma oddiy implikantlarni mukammal DNShdan (qisqartirilgan

DNShdan) chetlashtirish natijasida hosil qilinadigan DNSh Kvayn diz’yunktiv

normal shakli deb ataladi va

D

kv

deb belgilanadi.

U.Kvayn isbot qilgan (1959 y.) quyidagi teoremani keltiramiz.

1- shakl

1 - t e o r e m a . Har bir aynan 0ga teng bo‘lmagan

f

(

x

1

,...,

x

n

)

funksiyaning

yagona Kvayn diz’yunktiv normal shakli mavjud.

2

- m i s o l .

1- jadvalda berilgan

f

(

x

1

,

x

2

,

x

3

)

funksiyaning qisqartirilgan  

DNSh quyidagicha bo‘ladi:

D

s 



x

1 

x

2 



x

2 

x

3 



x

1

x

2

.

---

{

N

1

,

N

3

}

yadro

N

2

yoqni (qirrani) qoplaydi.

N

2

ga

x

2

x

3

oddiy implikant mos

keladi. Ta’rifga asosan, bu oddiy implikantni qisqartirilgan DNSh ifodasidan

chetlashtirsak, Kvayn DNSh kelib chiqadi:

D

kv



x

1

x

2



x

1

x

3

.

Demak, qisqartirilgan DNShdan ayrim oddiy implikantlarni chetlashtirish

yo‘li bilan yagona tarzda aniqlangan Kvayn DNShga o‘tish mumkin. Kvayn DNSh

o‘sha funksiyani realizasiya qiladi va bu funksiyaning hamma tupikli DNShlarini

o‘z ichiga olgan bo‘ladi.

4 -

birorta  

kiruvchi

majmuasi

t a ’r i f . Hech bo‘lmaganda

keltirilmaydigan

qobiqqa  

yoqlar

shunday

maksimal

bilan

qoplangan

N

f

to‘plamga mos keluvchi diz’yunktiv

normal shakl



T

turdagi DNSh deb

ataladi va u

D



T

bilan belgilanadi.

f 

(

x

1 

,..., 

x

n 

) 

funksiyaning hamma

tupikli  

(mantiqiy

soddalashtirish

natijasida

DNShlari

diz’yunksiyasi  

yig‘indisi)

va

uni

D



T

diz’yunktiv normal shakl hosil bo‘ladi.

Ta’rifga

asosan,

har

bir

f 

(

x

1 

,..., 

x

n 

) 

funksiya uchun yagona

D



T

DNSh mavjud va u

f 

(

x

1 

,...,

x

n

)

funksiyani

2- shakl

realizasiya qiladi.

D



T

DNSh

qisqartirilgan DNShdan ayrim hadlarini chetlashtirish yo‘li bilan hosil qilinadi.

5 - t a ’ r i f . 





N 

f 

bo‘lsin. U holda 



nuqtani o‘z ichiga olgan hamma 

N 

f

ga nisbatan maksimal yoqlarning (qirralarning) 

П



majmuasiga 



nuqtadan

Mukammal

Qisqartirilga  

n

Tupikli

Tupikli

Tupikli

Tupikli

Tupikli

Minimal  

DNShlar

Kvayn

turdagi

---

o‘tuvchi dasta (tutash) deb ataladi.

0

6 - t a ’r i f .





N

va 





N

bo‘lsin.

0

f

k

K

f

N

shu

N

to‘plamning maksimalyoqi

0

f

K





K

f

(qirrasi). Agar  





N

\

N 

0    

va  

П 



П

bo‘lsa, u holda  



nuqta (

N

va

N

larga

nisbatan) regulyar nuqta deb ataladi.

3 - m i s o l .

1- jadvalda berilgan

f 

(

x

1 

, 

x

2 

, 

x

3 

) 

funksiya uchun (1- shaklga

(0,0,1)

qarang) 



nuqta  sifatida

nuqtani va 

N

2 



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

maksimal yoqni

olamiz.  Ravshanki,  





N

2 

.  



regulyar  nuqta  ( 

N 

2    

va  

N 

f  

ga nisbatan) ekanligini

ko‘rsatamiz.  





(0,0,0)  

bo‘lsin. U holda 

(

N

1  



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

П





{

N

1 

, 

N 

2 

}

, 

П





{

N

1

}

va 

П





П



. Demak, 



nuqta regulyar nuqta bo‘ladi.

7 - t a ’r i f . Agar

N

0 

maksimal intervalning har bir nuqtasi (

N

0   

va

N

larga

k

k

f

nisbatan) regulyar nuqta bo‘lsa, u holda

N

uchun 

N 

0 

regulyar maksimal interval

f

k

deb ataladi.

4.3. Yu.I.Juravlev

2

teoremasi.

1

2

3

2- t e o r e ma (Juravlev  teoremasi).

f 

(

x 

, 

x 

, 

x 

)

funksiyaning

k

0

oddiy

implikanti

D



T

turdagi DNShning ifodasida bo‘lmasligi uchun, unga mos bo‘lgan

k

N 

0 

regulyar maksimal interval bo‘lishi yetarli va zarurdir.

5 - m i s o l .

1- jadvalda berilgan 

f

(

x

1

,

x

2

,

x

3

)

funksiya uchun bitta

N

2 

regulyar

interval  mavjud. Uni chetlashtirsak, u  holda  

N

1  



N

3   

ga ega bo‘lamiz.  Bu  yerdan

x

1 

x

2 



x

1 

x

3 

kelib chiqadi va u 

D



T 

turdagi DNShi bo‘ladi. Bu DNSh funksiyaning  

yagona tupikli DNShi ham bo‘ladi.

2 

Juravlyov Yuriy Ivanovich (Журавлёв Юрий Иванович, 1935 yilda tug‘ilgan) – rus matematigi, informatigi.

---

3 - t e o r e m a .

f

(

x

1

,

x

2

,

x

3

)

funksiyaning



T

turdagi DNSh shu funksiyaning

Kvayn DNShdan ayrim oddiy implikantlarni chetlashtirish yo‘li bilan hosil qilinishi

mumkin.

Shunday qilib,

f

(

x

1

,

x

2

,

x

3

)

funksiyani minimallashtirish jarayonini 2-

shaklda aks ettirilgan sxema orqali ifodalash mumkin.

---