Bundan keyin
h
L
indeksga nisbatan minimal bo‘lgan DNShni
minimal
diz’yunktiv shakl
deb ataymiz.
1.3-m i s o l .
1.1-misoldagi
1
D
va
2
D
DNShlarni tahlil qilamiz.
2
D
DNSh
minimal DNShdir, chunki ushbu DNSh orqali ifodalangan
)
,
,
(
3
2
1
x
x
x
f
funksiyaning
3
2
1
,
,
x
x
x
argumentlari muhim (soxta emas) argumentlardir. Shuning uchun uni
uchtadan kam harf bilan ifodalash mumkin emas.
2
D
DNSh eng qisqa DNShdir, chunki ushbu DNSh bilan ifodalangan
)
,
,
(
3
2
1
x
x
x
f
funksiya har qanday elementar kon’yunksiyadan farq qiladi.
2
D
DNSh
i
L
indeksga nisbatan ham minimal DNShdir, chunki ushbu DNSh
bilan ifodalangan
)
,
,
(
3
2
1
x
x
x
f
funksiya
2
x
va
3
x
o‘zgaruvchilari bo‘yicha o‘suvchi
funksiya emas va demak, uni ikkita inkordan kam inkor qatnashgan DNSh
ko‘rinishida ifodalash mumkin. ■
Shunday qilib, asosiy muammo matematik mantiqning ixtiyoriy
)
,...,
,
(
2
1
n
x
x
x
f
funksiyasi uchun
L
indeksga nisbatan minimal diz’yunktiv normal shaklni
topishdan
iboratdir.
Bu
muammo
matematik
mantiq
funksiyalarini
minimallashtirish muammosi
deb ataladi.
1.2. Matematik mantiq funksiyalarini minimallashtirish muammosini hal
qilish
algoritmining mavjudligi.
Bu bo’limda matematik mantiq funksiyalarini
minimallashtirish muammosini hal qilish usullari bilan shug‘ullanamiz. Avvalo bu
masala yechimining trivial algoritmi mavjudligini ta’kidlaymiz. Bu algoritm
birma-
bir ko‘zdan kechirish algoritmi
deb yuritiladi va quyidagi 4 bandda ifodalangan
jarayonlarni bajarishni taqazo qiladi.
1.
}
,...,
,
{
2
1
n
x
x
x
o‘zgaruvchilar to‘plamida barcha
n
3
2
ta
n
D
D
D
3
2
2
1
,...,
,
diz’yunktiv normal shakllarni ma’lum tartibda tuzamiz.
2. Bu DNSh lardan
)
,...,
,
(
2
1
n
x
x
x
f
funksiyani realizatsiya qiladigan DNShlarni
ajratib olamiz.
3. Ajratib olingan DNShlar soddalik indekslarining (
h
L
,
k
L
,
i
L
) miqdorlarini
hisoblaymiz.
4.
h
L
,
k
L
,
i
L
indekslar miqdorlarini bir-biri bilan taqqoslash yo‘li bilan
L
ga
nisbatan minimal bo‘lgan DNShni topamiz. ■
Keltirilgan algoritmni amaliy realizatsiya qilish uchun juda ham ko‘p mehnat
talab etiladi, chunki kamida
n
3
2
ta sodda amalni (operasiyani) bajarishga to‘g‘ri
keladi. Masalan,
3
n
bo‘lganda,
)
,
,
(
3
2
1
x
x
x
f
funksiyani realizatsiya qiladigan
L
indeksga nisbatan minimal diz’yunktiv normal shakllarni topish uchun kamida
728
217
134
2
2
3
3
3
n
ta amalni bajarishga to‘g‘ri keladi. Shuning uchun
3
n
dan
boshlab bu algoritmdan foydalanish (hattoki tez hisoblah imkoniyatiga ega bo‘lgan
hozilrgi zamon hisoblash mashinalarini ishlatganda ham) mantiqqa to‘g‘ri kelmaydi.
Bu algoritmdan faqatgina
1
n
va
2
n
bo‘lgan hollar uchun foydalanish mumkin.
Demak, umuman olganda, birma-bir ko‘zdan kechirish algoritmi minimal
diz’yunktiv normal shaklni topish masalasida amaliy yordam bermaydigan
algoritmdir. Shuning uchun mantiq algebrasi funksiyasini minimallashtirishning
boshqa usullarini izlashga to‘g‘ri keladi.
2. Diz’yunktiv normal shaklni soddalashtirish va tupikli DNSh
2 . 1 . Tupikli DNSh.
Mantiq algebrasining DNShdagi ixtiyoriy
D
formulasi
uchun
K
D
D
1
,
1
1
K
x
D
D
i
i
,
(1)
bo‘lsin, bu yerda
1
D
– biror DNSh,
K
– berilgan
D
formulaning biror elementar
kon’yunksiyasi,
i
i
x
– shu
K
elementar kon’yunksiyaning birorta (
i
indeksli)
ko‘paytuvchisi,
1
K
–
K
ning qolgan ko‘paytuvchilari, ya’ni
K
1
K
x
i
i
. DNShni
soddalashtirishning ikki xil yo‘lini (tipini) ko‘rib o‘taylik.
I.
Elementar kon’yunksiyani chetlashtirish operatsiyasi.
D
DNShdan
1
D
DNShga o‘tish uchun
K
elementar kon’yunksiyani chetlashtirish kerak. Bunday
o‘zgartirish
1
D
D
bo‘lganda va faqat shundagina mumkin.
II. Ko‘paytuvchini chetlashtirish operatsiyasi.
D
DNShdan
1
1
K
D
DNShga o‘tish operatsiyasi. Buni bajarish uchun
K
elementar kon’yunksiya
ifodasidan
i
i
x
ko‘paytuvchini chetlashtirish kerak. Bu almashtirish
1
1
K
D
D
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.
2.1 - m i s o l .
1
3
2
x
x
x
D
DNSh I va II almashtirishlarga nisbatan tupikli
DNShdir. ■
(1) va monotonlik aksiomasiga asosan
)
(
)
(
1
D
L
D
L
va
)
(
)
(
1
1
D
L
K
D
L
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
)
,
,
(
3
2
1
1
x
x
x
f
DNShni soddalashtirish
algoritmini
keltiramiz.
1.
)
,
,
(
3
2
1
1
x
x
x
f
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
i
K
(
n
i
,...,
2
,
1
) elementar kon’yunksiyaga nisbatan
i
K
elementar kon’yunksiyani
chetlashtirish operatsiyasi qo‘llaniladi, agar bu mumkin bo‘lmasa, u vaqtda chapdan
o‘ngga qarab
r
r
i
i
i
i
x
x
x
K
...
2
2
1
1
elementar kon’yunksiyalarning
v
v
i
x
)
,...,
2
,
1
(
r
v
ko‘paytuvchi hadlari ko‘rilib chiqiladi va ularga nisbatan mumkin bo‘lgunga qadar
v
v
i
x
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. ■
Do'stlaringiz bilan baham: 
