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

1.2. Misollar.

1 - m i s o l .

N 

f 



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

to‘plamga mos 

f

2 

(

x

1

, 

x

2 

,

x

3 

)

2

funksiyaning MKNShni

1

2

n

n

1

2

n

1

2







(



1

,



2

,..,



n

)

f

(

x

,

x

,...,

x

)





(

x



x



...



x

)

f

(



1

,



2

,..,



n

)



0

(1)

formuladan foydalanib yozamiz:

---

f

2

(

x

1

,

x

2

,

x

3

)



(

x

1



x

2



x

3

)(

x

1



x

2



x

3

)

.

Algoritmning 2- va 3- qadamlarini bajaramiz:

(

x

1 



x

2 



x

3 

)(

x

1 



x

2 



x

3 

) 



x

1

x

1 



x

1

x

2 



x

1

x

3 



x

1

x

2 



x

2 

x

2





x

2 

x

3 



x

1

x

3 



x

2 

x

3 



x

3 

x

3





x

1

x

2 



x

1

x

3 



x

1

x

2 



x

2 

x

3 



x

1

x

3 



x

2 

x

3

.

Qisqartirilgan DNSh quyidagi ko‘rinishda bo‘ladi:

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 

. ■

(2)

2 - m i s o l .

Quyidagi funksiya berilgan bo‘lsin:

f

1

(

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

.

Bu funksiyaga

1

f

N 



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

to‘plam mos keladi. Funksiyaning MKNSh ko‘rinishi

f

1

(

x

1

,

x

2

,

x

3

)



(

x

1



x

2



x

3

)(

x

1



x

2



x

3

)

.

Algoritmning 2- va 3- qadamlarini bajaramiz:

(

x

1 



x

2 



x

3 

)(

x

1 



x

2 



x

3 

) 



x

1

x

1 



x

1

x

2 



x

1

x

3 



x

1

x

2





x

2

x

2



x

2

x

3



x

1

x

3



x

2

x

3



x

3

x

3 





x

1 



x

1

x

2 



x

1

x

3 



x

1

x

2 



x

2 



x

2 

x

3 



x

1

x

3 



x

2 

x

3





x

1 



x

1

x

3 



x

2 



x

2 

x

3 



x

1

x

3 



x

2 

x

3





x

1 



x

2 



x

1

x

3 



x

2 

x

3 



x

1 



x

2

.

Demak, funksiyaning qisqartirilgan DNSh quyidagicha bo‘ladi:

D

s 



f

1 





x

1 



x

2 

. ■

(3)

2. Tupikli diz’yunktiv normal shakllarni geometrik asosda yasash usullari

---

2.1. Geometrik ma’nodagi tupikli diz’yunktiv normal shakllar.

Geometrik

ma’nodagi tupikli diz’yunktiv normal shakl tushunchasini o‘rganish uchun misolga

murojaat qilamiz.

1 - m i s o l . 

Ushbu bobning 4- paragrafidagi misolda (5) formula bilan

1

2

6

2

1

2

3

k

k

k

berilgan  

f  

(

x 

, 

x  

, 

x  

)  

funksiyaning  

N

,

N 

,...,

N

maksimal intervallardan iborat 

N

f

2

qoplama

6

2

1

2

3

4

5

k

k

N 

f  



N



N



N

k  



N

k  



N

k



N

k

(1)

ekanligini yuqorida ko‘rsatgan edik. Bu yerda

N

f  



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

,

2

1

k

2

k

N



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

N  



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

,

,

N

k 



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

,

3

N

k 



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

,

4

N

k 



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

,

5

N

k   



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

.

(2)

6

2

1

2

3

4

5

6

Quyidagi  savolga  javob  topaylik.

N

f

to‘plamning

N

k 

,

N

k 

,

N

k 

,

N

k 

,

N

k

,

N

k

maksimal intervallardan iborat bo‘lgan qoplamadan ayrim maksimal intervallarni  

chetlashtirganimizda, qolgan qismi yana

N

f

ning qobig‘i bo‘ladimi yoki yo‘qmi?

2

(1) va (2) munosabatlardan quyidagilar kelib chiqadi:

1

4

6

2

2

3

5

6

2

k

k

k

k

f

k

k

k

N

f      



N   



N   



N   



N

,

N



N 



N 



N

,

5

6

2

1

2

k

k

k

k

N

f  



N 



N  



N



N

2

3

5

2

k

k

k

f

,

N



N 



N  



N

,

N

f      



N

k   



N

k   



N

k



N

k 

.

(3)

2

4

2

3

6

N

f

to‘plamning  (3)  da ko‘rsatilgan  qoplamalaridan  boshqa  qoplamalari mavjud

2

emas. Bu qobiqlar (1) keltirilgan qobiqdan ayrim maksimal intervallarni

---

chetlashtirish natijasida hosil qilingan. Shunday qilib, qo‘yilgan savolning birinchi  

qismiga ijobiy javob berdik.

(3)  da  keltirilgan   

N

f

to‘plamning istalgan qoplamadan ixtiyoriy birorta

2

maksimal intervalni chetlashtirganimizda, qolgan maksimal intervallar

N

f

2

to‘plamning qoplamasi bo‘la olmaydi. Bunday qoplamalar