Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

- t a ’ r i f .

N _f to‘plamning
N_k maksimal intervaliga mos kelgan K

kon’yunksiya f funksiyaning oddiy implikanti deb ataladi.
^{Agar k1 kon’yunksiyaning hamma ko‘paytuvchilari} k ^{kon’yunksiyada ham}

mavjud bo‘lsa, u holda
N_k  N_k1
deb yozish mumkin. U holda, ma’lum ma’noda, f

^funksiyaning k ^{oddiy implikanti ifodasidan birorta ham ko‘paytuvchini} chetlashtirish mumkin emas, chunki ko‘paytuvchini chetlashtirish natijasida

N_k1  N _f
munosabatda bo‘lgan
k¹ kon’yunksiyaga ega bo‘lamiz.

Har qanday mumkin.
N_k intervalni
(N_k  N _f )
maksimal intervalgacha kengaytirish

N _f to‘plamning hamma maksimal intervallari
N ₀ , N ₀ ,..., N ₀

(1)

lardan iborat bo‘lsin. U holda
k₁ k₂ k_m

k k k
N _f  N ₀ ∪ N ₀ ∪... ∪ N ₀ (2)
1 2 m

bo‘ladi, chunki
N ₀  N _f

k
i
(i  1,2,..., m)
va N _f ning har bir nuqtasi (1) dagi maksimal

intervallarning birortasining elementi bo‘ladi. (2) tenglik quyidagi munosabatga ekvivalentdir:
f  k⁰  k⁰ ...  k⁰ . (3)
1 2 m

5. 2. Qisqartirilgan DNSh tushunchasi.

2. 
   - t a ’ r i f . f funksiyani hamma oddiy implikantlarining diz’yunksiyasi (3)
   

qisqartirilgan DNSh deb ataladi.
Demak,
D ( f )  k ⁰  k ⁰ ......  k ⁰ (4)
s 1 2 m

f funksiyaning qisqartirilgan DNShi bo‘ladi.
D_s ( f )
qisqartirilgan DNSh f

funksiya orqali bir qiymati aniqlanadi va f funksiyani realizasiya qiladi.

5.3 - m i s o l . 4-bo’limdagi (2) formulada berilgan maksimal intervallardan iborat
f₁ (x₁ , x₂ , x₃ )
uchun

N _f1  N_{k 0} ∪ N_{k 0}
(5)

1 2

Qobiqqa va o‘sha yerdagi (5) formulada berilgan
f ₂ (x₁ , x₂ , x₃ )
funksiya uchun

f

k k k k k k
N  N ∪ N ∪ N ∪ N ∪ N ∪ N
2 1 2 3 4 5 6
(6)

qobiqqa ega bo‘lamiz. Bu yerda k ⁰  x , k ⁰  x
, k  x x , k  x x , k  x x

, k  x x

1 1 2
, k₅  x₁ x₂ , k₆  x₁ x₃ . Bu qobiqlarga
² 1 1 2 ²
1 3 3
2 3 4 2 3

D_s ( f₁ )  x₁  x₂ ,
D_s ( f₂ )  x₁x₂  x₁x₃  x₂ x₃  x₂ x₃  x₁ x₂  x₁ x₃
qisqartirilgan DNShlar mos keladi. ■