Pdf-xchange 0 Examples

Манфий эмаслиги хақидаги аксиома.. Ҳар қандай ДНШ учун 
L(D)≥0. 
II. 
Монотонлиги хақидаги аксиома. ( кўпайтмага нисбатан ) Агар 
D=D
1
v
i
x

1
K
1
бўлса, у ҳолда L(D)≥L(D
1
vK
1
) ( 7 ). 
III Қавариқлиги хақида аксиома. (қўшишга нисбатан) Агар D=D
1 
v 
D
2
ва D
1 
Λ D
2

0 бўлса, L(D)≥L(D
1
)+L(D
2
) ( 8 ). 
IY. Инвариантлик ҳақидаги аксиома. (изоморфизмга нисбатан) 
Агар R
1
ДНШ
R ДНШ дан ўзгарувчиларни қайта номлаш (айнан 
тенглаштир-ишсиз) усули билан ҳосил қилинган бўлса, у ҳолда L(D
1
)=L(D) 
Дизъюнктив нормал шакллар учун мавжуд бўлган соддалик 
индеrсларини келтирайлик. 
1. L
Б
(D) – берилган D дизъюнктив нормал шаклдаги ўзгарувчилар 
ҳарфларининг сони. Масалан бизнинг мисолимиздаги D
1 
ва D
2
лар учун

---

76 
L
Б
(D
1
) =15 ва L
Б
(D
2
)=3, яъни бу индексга нисбатан D
1 
ДНШ D
2
ДНШ га 
қараганда соддароқдир. 
2. L
К
(D) – берилган D дизъюнктив нормал шаклдаги элементар 
конъюнкциялар сони. D
1
ва D
2
учун L
K
(D
1
) =5 ва L
K
(D
2
)=2, яъни D
2 
бу 
индексга нисбатан ҳам D
1 
га нисбатан соддароқ экан.
3. L
0
(D) – берилган D дизъюнктив нормал шаклдаги инкор 
белгиларининг сони. D
1 
ва D
2
лар учун L
0
(D
1
) =6 ва L
0
(D
2
)=2, демак, D
2
бу 
индекс учун ҳам D
1
га нисбатан оддароқ экан. 
L
Б
(D), L
К
(D), L
0
(D) индекслар юқорида келтирилган аксиомаларни 
қаноатлантиради. 
Маълумки, { x
1
, x
2
,… , x
n
} ўзгарувчилар тўпламидан 3
n
та элементар 
конъюнкция тузиш мумкин. ( “ бўш ” конъюнкцияга 1 константа мос қилиб 
қўйилган. ) Бундан ўз навбатида { x
1
, x
2
,… , x
n
} тўплам элементларидан 2
n
3
та ДНШ тузиш мумкинлиги келиб чиқади. 
3 таъриф. Агар f{ x
1
, x
2
,… , x
n
}функцияни реализация қилувчи ДНШ 
L(D) индексга нисбатан минимал бўлса, у ҳолда бундай ДНШ, L
K 
индексга 
нисбатан минимал бўлган ДНШ эса энг қисқа дизъюнктив нормал шакл 
деб аталади. 
Бизнинг асосий вазифамиз математик мантиқнинг ихтиёрий 
f{ x
1
, x
2
,… , x
n
 } функци-яси учун L индексга нисбатан минимал дизъюнктив 
нормал шаклни қандай усуллар ёрдами билан топишдан иборат бўлади. Бу 
муаммо 
математик 
мантиқ 
функцияларини 
минималлаштириш 
муаммолари деб аталади. Бу масала ечимининг тривиал алгоритми 
мавжудлигини кўрсатамиз: 
1. {x
1
,x
2
,…,x
n
} ўзгарувчилар тўпламида ҳамма 2
n
3
та D
1
,D
2
,∙∙∙, D
n
3
2
дизъюнктив нормал шаклларни маълум тартибда тузамиз.
2.Кейин бу ДНШ лардан f{x
1
, x
2
,…, x
n
} функцияни реализация 
қиладиган ДНШ ларни ажратиб оламиз. 
3. Ажратиб олинган ДНШ лар соддалик индексларининг ( L
Б
, L
К,
L
0
) 
миқдорларини ҳисоблаб чиқамиз. 
4. Хисоблаб чиқилган индекслар миқдорларини бир-бирига 
таққослаш йўли билан L га нисбатан минимал бўлган ДНШ ни топамиз. 
Келтирилган алгоритмни амалий реализация қилиш учун ҳам жуда 
кўп мехнат талаб этилади, чунки камида 2
n
3
та кичик амални бажаришга 
тўғри келади. Масалан, n=3 бўлганда f{ x
1
, x
2
,… , x
n
 } функцияни реализация 
қиладиган L индексга нисбатан минимал ДНШ ларни топиш учун камида
2
3
3
=2
27
=134217728 та амални бажаришга тўғри келади. Шунинг учун n≥3 
дан бошлаб бу алгоритмдан фойдаланиш мантиққа тўғри келмайди.

---

77