Pdf-xchange 0 Examples

Мантиқий функцияларни минималлаштириш Элементар 
∪ ранги. 
Мулоҳазалар 
алгебрасининг 
функцияларини 
 
минималлаштириш 
муаммолари. Минимал ДНШ. Энг қисқа ДНШ. Тривиал алгоритм. “ Бирма 
– бир кўздан кечириш.” Алгоритми. 
1 - таъриф. Ушбу К=x
1
1

i
∙x
2
2

i
∙∙∙x
r
r
i

(



да i


i

) (1) ифода 
элементар коньюнкция деб аталади, r сон элементар коньюнкциянинг 
ранги дейилади. Константа I ни ранги 0 га тенг бўлган элементар 
коньюнкция деб биламиз. 
2- таъриф. Ушбу D=
s
i 1


K
i
( i 

j да K
i

K
j
) (2) Ифода дизъюнктив 
нормал шакл (ДНШ) деб аталади, бу ерда К
i
- ранги i га тенг бўлган 
элементар конъюнкция.
Маълумки, D “
∩” нормал шакл мантиқ алгебрасининг маълум бир
f(x
1
, x
2
,… , x
n
)
функциясини реализация қилади.
Мантиқ алгебрасининг ҳар 
қандай
f( x
1
, x
2
,… , x
n 
) ( f≠0) функциясини ДНШ кўринишига келтириш 
мумкинлигини, яъни D=f(x
1
,x
2
,… , x
n
) (3) эканлигини олдин кўрилган. 
Бундай ДНШ сифатида f функциянинг мукаммал дизъюнктив нормал 
шаклини ( МДНI) олиш мумкин, яъни
D= V ∙ x
1
1

∙x
2
2

∙…∙x
n
n

(
1

∙ 
2

∙∙∙ 
n

) (4) f (
1

∙ 
2

∙∙∙ 
n

)=1 
1-мисол f( x
1
, x
2
,… , x
n 
)
функция қуйидаги чинлик жадвали билан 
берилган бўлсин: 
х
1 
х
2 
х
3 
f( x
1
, x
2
, x
3 
) 
х
1 
х
2 
х
3 
f( x
1
, x
2
, x
3 
) 
0 
0 
0 
1 
1 
0 
0 
1 
0 
0 
1 
0 
1 
0 
1 
1 
0 
1 
0 
0 
1 
1 
0 
1 
0 
1 
1 
0 
1 
1 
1 
1 

---

75 
У ҳолда бу функцияни қуйидаги МДНШ кўринишида ифодалаш 
мумкин: D
i
=
3
2
1
x
x
x
v x
1
2
x
3
x
v x
1
2
x
x
3 
v x
1
x
2
3
x
vx
1
x
2 
x
3
(5) 
Иккинчи тарафдан, шу функциянинг ўзини
D
2
= 
2
x
3
x
v x
1
(6) 
ДНШ кўринишида ҳам ифодалаш мумкин. 
Ушбу масала кўрсатяптики, мантиқ алгебрасининг битта 
функциясини бир нечта ДНШ кўринишида ифодалаш мумкин.
Агарда D
1 
билан D
2 
кўринишлардаги функцияни:
а) контактли схема орқали реализация қилсак, у ҳолда D
1 
ни 
реализация қилиш учун 5 та контакт ва D
2 
ни реализация қилиш учун 3 та 
контакт талаб этилади; 
б) ноль тактли функционал элементлардан ясалган схема орқали 
реадизация қилсак, у ҳолда D
1 
ни реализация қилиш учун 21 дона 
функционал элемент ва D
2 
ни реализация қилиш учун 4 дона функционал 
элемент сарф бўлади; 
в) бир тактли функционал элементлардан ясалган кўп тактли тўғри 
схема орқали реализация қилиш талаб этилса, у ҳолда D
1 
ни реализация 
этиш учун 33 дона функционал элемент, шу жумладан, 12 дона ушлаб туриш 
элементи ва D
2 
ни реализация қилиш учун 6 дона, шу жумладан, 2 дона 
ушлаб туриш элементи керак бўлади. 
Демак D
1 
ни реализация қиладиган схеманинг таннархи D
2
ни 
реализация қиладиган схеманинг таннархидан анча қиммат туради. 
Шунинг 
учун 
ҳам 
мантиқ 
алгебраси 
функцияларини 
минималлаштириш муаммоси халқ хўжалиги учун катта амалий аҳамиятга 
эгадир. Бу масалани ҳал этиш учун ДНШнинг “мураккаблигини” 
ифодаловчи L(D) соддалик индексини киритамиз. 
L(D) функционал учун қуйидаги аксиомаларнинг бажарилишини 
талаб қиламиз. 
I.