Maksimal interval va oddiy implikant tushunchalari

9.5.2. Qisqartirilgan DNSh tushunchasi.
3- ta’rif. funksiyani hamma oddiy implikantlarining diz’yunksiyasi (3) qisqartirilgan DNSh deb ataladi.
Demak,
(4)
funksiyaning qisqartirilgan DNShi bo‘ladi. qisqartirilgan DNSh funksiya orqali bir qiymati aniqlanadi va funksiyani realizasiya qiladi.
3- misol. Ushbu bobning 4- paragrafidagi (2) formulada berilgan uchun maksimal intervallardan iborat
(5)
Qobiqqa va o‘sha yerdagi (5) formulada berilgan funksiya uchun
(6)
qobiqqa ega bo‘lamiz. Bu yerda , , , , , , , . Bu qobiqlarga
,

qisqartirilgan DNShlar mos keladi. ■
9.6. Qisqartirilgan diz’yunktiv normal shaklni yasash algoritmi


Funksiya. Qisqartirilgan DNSh. Algoritm.


9.6.1. Qisqartirilgan DNSh yasash algoritmi. Ixtiyoriy funksiyaning qisqartirilgan diz’yunktiv normal shaklini yasash uchun quyidagi operasiyalarni bajaramiz:
1) funksiyaning istalgan kon’yunktiv normal shaklini olamiz, masalan, mukammal KNSh;
2) qavslarni ochib chiqamiz, ya’ni

turdagi almashtirishni o‘tkazamiz;
3) hosil qilingan ifodadan 0 ga teng hadlarni chetlashtiramiz va
,
formulalardan foydalanib uni soddalashtiramiz. Natijada, qisqartirilgan DNShga kelamiz. ■
9.6.2. 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)