Pdf-xchange 0 Examples

Adabiyot: 
1. Xalq so’zi gazetasi, 2016-yil 31-dekabr (№259).1-2 sahifa. 
МАНТИҚИЙ ФУНКЦИЯЛАРНИ МИНИМАЛЛАШТИРИШ 
УСУЛЛАРИ 
Назаров Ф.М.
Андижон давлат университети 
Мантиқ алгебраси функцияларини минимал схемалар орқали 
реализация қилиш муаммосини ечиш жуда катта илмий-амалий аҳамиятга 
эга бўлган долзарб муаммодир. Афсуски, аниқ схемаларнинг минимал 
схема эканлигини исботлаш айрим ҳоллардагина мумкин.
Схемаларни минималлаштириш муаммоси мантиқ алгебраси 
функция-ларини 
минималлаштириш 
муаммоси 
билан 
чамбарчас 
боғлангандир.

---

73 
Айрим ҳолларда берилган схеманинг минимал схема эканлигини 
кўрсатадиган хоссаларни топиш мумкин. Буни мисолларда кўриб чиқамиз.
Агар бирорта ўзгарувчи функциянинг сохта эмас аргументи бўлса,
у ҳолда ушбу функцияни ишлатади схемада энг камида ўша ўзгарувчига мос 
келадиган бир дона контакт мавжуд бўлиши керак. “Кўприкча” реализация 
этадиган ўтказувчанлик функцияси f(x,y,z,u,t) = xyVtuVxzuVtzu бўлади.
Бу функциянинг ҳамма x, y, z, u, t аргументлари муҳим аргументлардир. 
Схемада бу аргументларга мос келадиган контактлар бир мартадан 
қатнашган. Демак, “кўприкча” схемаси минимал схемадир. 
Шундай қилиб, агар схемадаги контактлар хар хил ўзгарувчиларга 
мос келса ва бу ўзгарувчилар ўтказквчанлик функциясининг муҳим 
аргументлари бўлса, у ҳолда схема минимал схема бўлади. Энди қуйида 
келтирилган схеманинг минимал эканлигини кўрсатайлик 
Берилган бу ихтиёрий схемада х
1 
ўзгарувчига мос бўлган контактлар 
фақат мусбат бўлсин. У ҳолда f(x
1
, x
2
,… , x
n
) ўтказувчанлик функцияси учун 
f( x
1
, x
2
,… , x
n 
)≥ f( 0, x
2
,… , x
n 
) муносабат ҳамма x
2
,… , x
n
учун бажарилади 
Худди шу каби, агар х
1 
га фаватгина манфий контактли контактлар мос 
келса, у ҳолда
f(1, x
2
,… , x
n
)≤ f( 0, x
2
,… , x
n
) муносабат ҳамма x
1
, x
2
,… , x
n 
учун 
бажарилади.
Шундай сигналлар мажмуи ( 
2

, 
3

,...,
n

) мавжуд бўлсинки, f (1,
2

, 
3

,...,
n

) < f(0,
2

, 
3

,...,
n

) бажарилсин. У ҳолда f функция х
1
аргументи 
бўйича ўсмайди. ва f функ-цияни реализация қиладиган ҳар қандай схемада 
х
1
га мос бўлган манфий контакт бор деб айтамиз. 
Худди шу каби (
2

, ...,
n

) мажмуи учун f (1, 
2

, ...,
n

) > f(0, 
2

, ...,
n

)
бажарилса, у ҳолда f функция х
1
аргументи бўйича камаймайди ва f ни 
реализация қиладиган схемада х
1
га мос мусбат контакт бор деб айтамиз. 
Агарда f функция х
1
аргументи бўйича на камаювчи ва на ўсувчи функция 
бўлса, у ҳолда f функцияни реализация қилувчи схемада х
1
аргумент бўйича 
ҳам манфий, ҳам мусбат контактлар мавжуд бўлади. Схеманинг ўтказувчан-
лик функциясининг f=x
1
x
2
..x
n
v
n
x
x
x
...
2
1
кўриниши бўлади. 
2

=
3

=...=
n

=0 да
f функция х
1
аргументи бўйича ортувчи бўлмайди ва 
2

=
3

= ...=
n

=1 да 
камаювчи бўлмайди. Кўрилаётган функция ҳамма аргуметларига нисбатан 
симметрик бўлгани учун, қолган барча аргументлари бўйича ҳам ўсувчи ва 
камаювчи функция бўлмайди. Кўрилаётган схемада ҳар бир ўзгарувчига 
мусбат ва манфий контакт тўғри келгани учун бу схема минимал схемадир.
Демак, агар схемада ҳар бир ўзгарувчига биттадан мусбат ва 
биттадан манфий контакт мос келиб, функциянинг ҳамма аргументлари 
муҳим аргумент бўлса ва бу ўзга-рувчилар бўйича функция ўсувчи ҳам, 
камаювчи ҳам бўлмаса, у ҳолда схема минимал схема бўлади. 
f=x
1
x
2
..x
n
v
n
x
x
x
...
2
1
функцияни реализация қиладиган Схемадан фарқ 
қиладиган минимал схема тузиш талаб қилинсин. Бунинг учун f функцияни 

---

74 
(x
1
v
2
x
)(x
2
v 
3
x
)( x
3
v
4
x
) ...( x
n-1
v
n
x
)( x
n
v
1
x
) кўринишидаги КНШ га 
келтирамиз ва уни реализация қиладиган схема минимал бўлади.
Демак битта функцияни ҳар хил минимал схемалар орқали реализация 
қилиш мумкин экан, яъни минимал схема ягона эмас.
“ Кўприкча ” минимал схемаси орқали бажарилган f=xy v tu v xzu v 
tzу функция учун 5 контактли схема мавжуд эмаслиги қўйилган саволга 
жавобдир. 
f(x
1
, x
2
,… , x
n
) мантиқ алгебрасининг функцияси бўдсин. L(f) орқали 
уни реализация қиладиган минимал схемадаги контактлар сонини ва L
n
(f) 
орқали схемадаги контактлар сонини белгилаймиз. У ҳолда L(f) ≤ L
n
(f) 
бўлади. max L(f)=L(n) ва max L
n
(f)=L
n
(n) лар Шеннон функциялари 
деб аталади: n аргументли f( x
1
, x
2
,… , x
n 
) функцияни схема орқали 
реализация қилиш учун зарур бўлган минимал ва максимал контактлар 
сонини топиш масаласи катта амалий аҳамиятга эга.