Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

2. Diz’yunktiv normal shaklni soddalashtirish va tupikli DNSh

2. 
   1 . Tupikli DNSh. Mantiq algebrasining DNShdagi ixtiyoriy D formulasi
   

i
D  D¹  K , D  D¹  x^i K¹ , (1)

bo‘lsin, bu yerda kon’yunksiyasi,
D¹ – biror DNSh, K – berilgan D formulaning biror elementar

x

i
^i – shu K elementar kon’yunksiyaning birorta ( i indeksli)

ko‘paytuvchisi,
K¹ – K ning qolgan ko‘paytuvchilari, ya’ni
^{K } x^i K ¹ . DNShni

i
soddalashtirishning ikki xil yo‘lini (tipini) ko‘rib o‘taylik.

1. Elementar kon’yunksiyani chetlashtirish operatsiyasi. D DNShdan D¹

DNShga o‘tish uchun K elementar kon’yunksiyani chetlashtirish kerak. Bunday
o‘zgartirish D  D¹ bo‘lganda va faqat shundagina mumkin.

2. 
   Ko‘paytuvchini chetlashtirish operatsiyasi. D DNShdan D¹  K ¹
   

x
DNShga o‘tish operatsiyasi. Buni bajarish uchun K elementar kon’yunksiya

ifodasidan
^i ko‘paytuvchini chetlashtirish kerak. Bu almashtirish
D  D¹  K¹

i
bo‘lganda aniqlangan.
2.1 - t a ’ r i f . I va II almashtirishlar yo‘llari bilan soddalashtirish mumkin bo‘lmagan D DNSh (I va II almashtirishlarga nisbatan) tupikli DNSh (TDNSh) deb ataladi.

1. - m i s o l .

DNShdir. ■



D  x₂ x₃  x₁
DNSh I va II almashtirishlarga nisbatan tupikli

(1) va monotonlik aksiomasiga asosan
L(D¹ )  L(D) va
L(D¹  K¹)  L(D)

bo‘ladi. Shuning uchun TDNShlar orasida har doim minimal diz’yunktiv normal shakllar mavjud bo‘ladi.
2.2. Diz’yunktiv normal shaklni soddalashtirish. Endi yuqorida keltirilgan

ikkita almashtirish asosida berilgan
algoritmini keltiramiz.
f₁ (x₁ , x₂ , x₃ )

DNShni soddalashtirish

1. 
   f₁ (x₁ , x₂ , x₃ ) funksiyani ifodalovchi biror DNShni dastlabki DNSh sifatida
   

olamiz. Masalan, shunday DNSh sifatida uning mukammal diz’yunktiv normal shaklini olamiz (chunki chinlik jadvali asosida uni formula orqali osongina yozish mumkin).

2. 
   Dastlabki diz’yunktiv normal shaklda qo‘shiluvchilarni va har bir qo‘shiluvchidagi ko‘paytuvchilarni tartibga solamiz. Bu tartiblash bilan DNSh ko‘rinishi beriladi.
   
3. 
   Chapdan o‘ngga qarab DNSh ko‘rinishi ko‘rilib o‘tiladi. Navbatdagi K_i (
   

i  1,2,..., n ) elementar kon’yunksiyaga nisbatan K_i elementar kon’yunksiyani
chetlashtirish operatsiyasi qo‘llaniladi, agar bu mumkin bo‘lmasa, u vaqtda chapdan

o‘ngga qarab
K  x^1 x^2 ...x^r elementar kon’yunksiyalarning x^v
(v  1,2,..., r)

i i₁ i₂ i_r i_v
ko‘paytuvchi hadlari ko‘rilib chiqiladi va ularga nisbatan mumkin bo‘lgunga qadar

x

i_v
^v ko‘paytuvchini chetlashtirish operatsiyasi qo‘llaniladi. Shundan so‘ng keyingi
elementar kon’yunksiyaga o‘tiladi.
Oxirgi elementar kon’yuknsiyani ishlab chiqqandan keyin, hosil bo‘lgan DNShni yana qaytadan chapdan o‘ngga qarab ko‘rib chiqiladi va elementar kon’yunksiyani chetlashtirish operatsiyasi sinab ko‘riladi. Natijada izlangan diz’yunktiv normal shaklga ega bo‘lamiz. ■

1.