Pdf-xchange 0 Examples

энг қисқа дизъюнктив нормал шакл
 
деб аталади
. 
Бизнинг асосий вазифамиз математик мантиқнинг ихтиёрий 

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