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 
индексга 
нисбатан минимал бўлган ДНШ эса