DNShlar f 2 funksiyaning tupikli diz’yunktiv normal shakllari bo‘ladi.«
Teorema. I va II almashtirishlarga nisbatan tupikli DNShtushunchasi bilan geometrik m a’nodagi tupikli DNSh tushunchasi ekvivalentdir.
9.7.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’yunksiyalami chetlashtirish yo‘li bilan hosil qilinadi.Lh ga nisbatan minimal DNSh tupikli bo‘ladi.
Tupikli DNShlar orasida Lh ga nisbatan minimal DNShlar mavjud bo‘ladi.
3-misо 1. Ushbu bobmng^4-_paragrafidagi misolda (5) formulabilan berilgan ^ (x ,,x 2,x ^)= x lx2x3Vx1 x2x} v x, x,x3 v x,x2x3 v x,x2 x3 v x,x0 x3 funksiyaning Ds( f 2) qisqartirilgan DNShni topdik (6- paragrafdagi (1) gaqarang):
___ ___________ ______
Ds (f 2) = x,x2 v x,x3 v x, x2 v x2x3 v x, x3 v x2 x3 .
Undan keyin (5) da ifodalangan tupikli DNShlarni hosil qildik. U yerdan ko‘rinib turibdiki,Lh(Di) = Lh(Di) = 6 va Lh(D 3) = Lh(D A) = Lh(D 5) = S.Demak,£>, = x, x 2 v x ,x 3 v x 2x7 va D 2 =x^x3 v x ,x 2 tupikli DNShlar / 2(x ,,x 2,x 3) funksiyaning minimal diz’yunktiv normal shakllari bo‘ladi. Ravshanki, bu DNShlar o‘z navbatida / 2(x,,x2,x3)ning eng qisqa DNShlari ham bo‘ladi.MDNSh asosida minimal DNSh yasash jarayonining sxemasi 1- shaklda ifodalangan.
Xulosa
Xulosa qilib aytadigan boʻlsak agar bir hadga Ai yoki ⌐Ai formulalar juftligidan faqat bittasi kirgan bo‘lsa, A1, A2, …, An fikr o‘zgaruvchilarining kon’yunktiv yoki diz’yunktiv bir hadlari mukammal deyiladi.Agar KNSh yoki DNSh larda A1, A2, …, An o‘zgaruvchilarning takrorlanmaydigan mukammal bir hadlari kirgan bo‘lsa, A1, A2, …, An fikr o‘zgaruvchilarining KNSh yoki DNSh lari mukammal deyiladi.
Masalan: A&B\/⌐A&B\/A&⌐B – A va B fikro‘zgaruvchilarining Mukammal diz’yunktiv normal shakli (MDNSh) bo‘ladi. A\/B – esa MKNSh bo‘ladi.
Do'stlaringiz bilan baham: |
