2- ta’rif. to‘plamning maksimal intervaliga mos kelgan kon’yunksiya funksiyaning oddiy implikanti deb ataladi.
Agar kon’yunksiyaning hamma ko‘paytuvchilari kon’yunksiyada ham mavjud bo‘lsa, u holda deb yozish mumkin. U holda, ma’lum ma’noda, funksiyaning oddiy implikanti ifodasidan birorta ham ko‘paytuvchini chetlashtirish mumkin emas, chunki ko‘paytuvchini chetlashtirish natijasida munosabatda bo‘lgan kon’yunksiyaga ega bo‘lamiz.
Har qanday intervalni maksimal intervalgacha kengaytirish mumkin.
to‘plamning hamma maksimal intervallari
(1)
lardan iborat bo‘lsin. U holda
(2)
bo‘ladi, chunki va ning har bir nuqtasi (1) dagi maksimal intervallarning birortasining elementi bo‘ladi. (2) tenglik quyidagi munosabatga ekvivalentdir:
. (3)
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. ■
Qisqartirilgan diz’yunktiv normal shaklni yasash algoritmi
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. ■
Do'stlaringiz bilan baham: |
