Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

Misollar.
1- misol. to‘plamga mos funksiyaning MKNShni
(1)
formuladan foydalanib yozamiz:
.
Algoritmning 2- va 3- qadamlarini bajaramiz:


.
Qisqartirilgan DNSh quyidagi ko‘rinishda bo‘ladi:
. ■ (2)
2- misol. Quyidagi funksiya berilgan bo‘lsin:
.
Bu funksiyaga

to‘plam mos keladi. Funksiyaning MKNSh ko‘rinishi
.
Algoritmning 2- va 3- qadamlarini bajaramiz:




.
Demak, funksiyaning qisqartirilgan DNSh quyidagicha bo‘ladi:
. ■ (3)

5-ilova



6-ilova

Insert texnikasi bo`yicha mavzuni o`qib chiqing va jadvalni to`ldiring. № Asosiy tushunchalar Belgi 1. Elementar kon’yunksiyaning rangi. 2. Minimal DNSh. 3. Eng qisqa DNSh. 4. Trivial algoritm 5. Tupikli DNSh. 6. Minimal DNShga keltirish. 7. Ko‘paytuvchini chetlashtirish jarayoni. 8. Joiz kon’yunksiyalar. 9. Qisqartirilgan DNSh Maksimal interval. Algoritm.

Insert jadvali qoidasi  – avval olgan bilimiga to’g’ri keladi. + – yangi ma’lumot -- – olgan bilimiga qarama-qarshi ? – tushunarsiz (aniqlanishi zarur bo’lgan ma’lumotlar)

Sinov savollari

1. 
   va DNShlar berilgan bo‘lsin. Quyidagi mulohazalarning chinligini isbotlang. Agar va ko‘rinishdagi funksiyani:
   

a) kontaktli sxema orqali realizatsiya qilsak, u holda DNShni realizatsiya qilish uchun 15ta kontakt, DNShni realizatsiya qilish uchun esa 3ta kontakt talab etiladi;
b) nol taktli funksional elementlardan yasalgan sxema orqali realizatsiya qilsak, u holda ni realizatsiya qilish uchun 21 dona funksional element va 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 etilsa, u holda ni realizatsiya qilish uchun 33 dona funksional element, shu jumladan, 12 dona ushlab turish elementi va ni realizatsiya qilish uchun 6 dona, shu jumladan, 2 dona ushlab turish elementi kerak bo‘ladi.

2. 
   Quyidagi funksiyalarni MKNShga keltirib, , , soddalik indekslarining miqdorini toping:
   

a) ; b) ;
d) ; e) .

3. 
   Quyidagi funksiyalarni soddalashtirish algoritmidan foydalanib, minimal diz’yunktiv normal shaklga keltiring:
   

a) ;
b) ;
d) .

4. 
   Diz’yunktiv normal shaklda berilgan quyidagi funksiyalarning tupikli diz’yunktiv normal shaklini toping:
   

a) ;
b) ;
d) .

5. 
   5- bandda berilgan funksiyalarning har biri uchun minimal diz’yunktiv normal shaklni toping.
   
6. 
   Matematik mantiq funksiyalarini minimallashtirish muammosining amaliy ahamiyatini tushuntirib bering. Matematik mantiq funksiyalarini minimallashtirish masalasini yechishda trivial algoritmni qo‘llash noqulayligi nimadan iboratligini tushuntiring.
   
7. 
   Quyidagi to‘plamlarga mos keladigan va funksiyalarning analitik ko‘rinishlarini yozing:
   

a) ;
b) .

8. 
   Quyidagi intervallarga mos keluvchi kon’yunksiyalarning analitik ko‘rinishlarini yozing:
   

a) , b) ,
d) _.

9. 
   Har bir intervallardan iborat to‘plamning qobig‘iga diz’yunktiv normal shaklda ifodalangan funksiya mos kelishini isbotlang.
   
10. 
    Quyida berilgan funksiyalarning joiz kon’yunksiyalarini toping:
    

a) ;
b) ;
d) ;
e) ;
f) ;
h) .

11. 
    Qisqartirilgan DNShni yasash algoritmi asosida quyidagi funksiyalarni qisqartirilgan DNSh ko‘rinishga keltiring:
    

a) ;
b) ;
d) .
Mustaqil ishlash uchun savollar

1. 
   Matematik mantiq funksiyalarini minimallashtirish muammosi deganda nimani tushunasiz?
   
2. 
   Soddalik indeksi va uning xususiyatlarini bilasizmi?
   
3. 
   Minimal va eng qisqa DNSh qanday ta’riflanadi?
   
4. 
   Trivial algoritm tushunchasini bilasizmi?
   
5. 
   Nega birma-bir ko‘zdan kechirish algoritmi qulay bo‘lsada kam qo‘llaniladi?
   
6. 
   DNShni soddalashtirishning necha xil yo‘lini bilasiz?
   
7. 
   Elementar kon’yunksiyani va ko‘paytuvchini chetlashtirish jarayonlari qanday jaroyonlar?
   
8. 
   Tupikli DNSh deganda nimani tushunasiz?
   
9. 
   Minimal DNShga keltirishda qanday muammolar bor?
   
10. 
    Interval tushunchasi nimani anglatadi?
    
11. 
    To‘plam qobig‘i nima?
    
12. 
    To‘plam qobig‘i bilan funksiya orasida qanday munosabat bor?
    
13. 
    Joiz (ruxsat etilgan) kon’yunksiyalar deganda nimani tushunasiz?
    

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