Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез



Pdf көрінісі
бет42/131
Дата24.03.2022
өлшемі1,67 Mb.
#28682
1   ...   38   39   40   41   42   43   44   45   ...   131
Байланысты:
1-том, 113-240

УДК 378(075.8):51 
 
ЛОГИКАЛЫҚ АЛГЕБРА ФУНКЦИЯЛАРЫН ТІЗБЕКТІ ЕСЕПТЕУ АРҚЫЛЫ 
АЛЫНҒАН МИНИМАЛ ФОРМУЛАЛАР СИНТЕЗІ. 
 
Жантлеуов Нұржан Бахытұлы, Математика мамандығының 
 2 курс магистранты. 
Шымкент Университеті 
 
Бұл  жұмыста    формалды  класстағы  көп  мәнді  логикалық  алгебраның  функцияларын 
минимизациялаудың    д.қ.ф-лар  класында  қиындықтар  тұғызатын  логикалық  функциялардың 
жалпылама  қасиеттері  жойылмайтын  минимизациялаудың  дискриптивтік  және  метрикалық 
аспектілерін қарастырамыз[1-3]. 
Д.қ.ф.  бульдік  формулалардың  арнайы  түрі  болып  табылады,  атап  айтқанда    бұл  – 
дизьюнкция  (  «немесе») 

  болып,  онда  әрбір  мүшесі  коньюнкция(«және») 
лардан  құралған  сол  немесе  басқа  түрлі  айнымалылардың 
,  j=
1,   терістеуімен    немесе 
оныңсыз қабылданады.  
  Айталық  
= { ,
, …
, … } - бастапқы айнымалылар алфавиті берілген болсын. 
Логикалық  алгебрасында немесе бульдік функцияларда осы алфавитте анықталған 
( ,
, … ,
)

, ≠  функцияны  қарастырамыз . 
    Белгілеу енгіземіз: 


~ 151 ~ 
 
=
̅, егер  = 0
, егер  = 1
 . 
  Мұнда 
= 1 болатынын тек  =    жағдайдағана дұрыс екенін кґру қиын емес. 
Логикалық алгебра функциялары 
 кубтағы n – ґлшемді бірлік тґбелер жиынында 
анықталған. Әрбір f функцияға  барлық ά

 тґбелер үшін  f(ά)=1 болған 

 ішкі 
жиындарды сәйкес қоямыз.  
1-анықтама. 
к

  ішкі  куб    r  -  рангілі  интервал  деп  аталады,  егер  ол  r-рангілі  К 
э.к.ға сәйкес келетін болса. 
Бұл r-рангілі  интервал 
2
  нүктелерден   құралады,  ал  d=n-r  шамасы 
к
  интервалдың 
ґлшемі деп аталады (dim 
к
). 
Мұнда  f  функцияның  кез  келген 

⋁ … ⋁
  д.қ.ф.сы  үшін 
= ⋃
  қатынас 
орындалады,  сондықтан  f  функцияның  әрбір  д.қ.ф.сы 
  жиынның  қапталуына  сондай 
,
, … ,
  интервалдармен   
⊆ 
  (j=
1,
)  шарт  бойынша  байланыста  болады. 
Бұндай интервалдар f функциясы үшін жарамды деп аталады. 
2-анықтама. 
к
  интервалы  f  функциясы  үшін  максимал  деп  айтылады,  егер 
к

 
болып  
к

`

 қатынаста болатын  
`
интервалы табылмаса. 
Логикалық алгебраның к-мәнді функцияларынформулалар арқылы кескіндеу 
Әрбірі  ґзімен    ґлшемді 
− мәнді  кубты  сипаттайтын{
}, ≥ 3  жиынтықтар  үйірін  
қарастырамыз, мұнда 
= (
,
, … ,
) ∈
, егер 

= {0,1, … , − 1}, = 1, . 
Әрбір    ґлшемді 
− мәнді  кубтың 
  құрамында 
2
− 1  түрлі 
1 ≤ ≤ 2
− 1  
ішкі  жиындар  болсын. 
дан  алынған  әрбір   
  жиынтыққа 
( , 
)  ретінде    оң  сан  сәйкес 
қоямыз және оны 
дегы 
 дің қуаты деп атауға келісеміз. 
Ал,
,
, … ,
  жиынтықтың қуаты ретінде   
= ∑
(
,
) санды айтамыз. 
Дербес жағдайларда кез келген 
 жиынтығы үшін қуаттар ретінде тґмендегілер сәйкес 
келеді:  
,
= 1, 
,
=
( −/ /) ∏
/ /
/ /

⋅ … ⋅
/
/
/
/
 
бұл жерде 
/ /− ге кіретін ґзара әр түрлі    –координаталар тґбелерінің саны; 
 -    -
координатасы  -ға тең болған 
−ге енетін тґбелер саны.  
  жиынтықта 
  айнымалыға  байланысты
 ( ,
, … ,
)функцияны  қарастырамыз, 
мүнда 
(
,
, … ,
) ∈


, = 1, .  Осындай  функцияларды    к-мәнді    логикалық 
функциялар деп атаймыз. 
  арқылы 
  айнымалыға  байланысты 
− мәнді  барлық  логикалық  функциялар 
жиынын(құрамында бос жиында болуы мүмкін) белгілейміз. Мұнда  
/
/=
екені белгілі. 
к-мәнді  логиканың  әрбір 
( ,
, … ,
)  функциясына 
,
, … ,

)
ретіндегі 
тґмендегідей  болған  кґбімен  (
к − 1)  жиын  (құрамында  бос  жиында  болуы  мүмкін)  сәйкес 
келеді :  


~ 152 ~ 
 
( ,
, … ,
) =







1, егер    ∈
,
2, егер    ∈
,
… … … … … … ,
(к − 1), егер    ∈

)
,
0, егер    ∈
/
 

= ∅,  ≠ . 
 
 арқылы 
,
, … ,

)
 жиынтығының бірігуін белгілейміз. 
Оларда тґмендегідей қатынас ґте айқын:  
( ) = max
{ ( ), ( ), … ,
( )} ,        (2.1) 
бұл жерде  ( ) =
, егер  ∈
0, егер    ∉ 
 
 
Логикалық алгебра функцияларын тізбекті есептеу арқылы алынған минимал 
формулалар синтезі. 
 
Айталық 
( = 1, )  э.к.ры  ядролық  болған 
/ ⋁
    д.қ.ф.ға  кіретін  
белгілі бір сандағы э.к.лары бар д.қ.ф. болсын. 
 
/ ⋁
  д.қ.ф.да э.к.лардың  рангісін ґсу ретімен орналастырамыз: 

≤ ⋯ ≤

 
(
− )–ґлшемді 
  кубты  қарастырамыз,  мұнда   
= ( ,
, … ,

координаталы әрбір набор(жиналым)    д.қ.ф.ға  келесі түрде сәйкес келеді: яғни    д.қ.ф.ға 
 енеді, егер 
= 1болса, және    д.қ.ф.ға енбейді, егер 
= 0, ( = 1,
− ) болса. 
 
 кубтың барлық    ά  наборларын    деңгейлі деп атаймыз, егер  | |
= ,
=
0,
−   болса  (мұнда  бірлік  координаттар  саны 
−ге  тең).  Барлық  наборларды 
антилексикографиялық ретімен орнатамыз. 
(
− _)  –  ґлшемді 
  кубтың  наборлар  жиынында   
( ,
, … ,
)    және 
`
( ,
, … ,
)функцияларын  тґмендегідей    түрде  енгіземіз:  ( ,
, … ,
) = ,  егер 
осы  D  д.қ.ф.ның  (
,
, … ,
)    наборлары  және 
, ( = 1, )    ядролық  э.к.  үшін 
тґмендегідей сәйкестік орындалса 

= , 
`
( ,
, … ,
) =

+

Кґрініп тұрғандай, 
≤ ( ) ≤
,

`
( ) ≤ (
− )
+

 ( ,
, … ,
)  және 
`
( ,
, … ,
)–монотонды функциялар. 
Егер 
( ,
, … ,
) =
  болса,  онда  D  д.қ.ф.ның  (
,
, … ,
)    наборына 
сәйкес келетін және ядролық коньюнкциялардың жиынтығы   функциясын іске асырады. 


~ 153 ~ 
 
 
Егер 

  наборы  үшін  ( )
=
  орындалса  және  кез  келген 
`
наборы 
үшін  сондай  | |
=
`
+ 1,
,
`
= 1   (
,
  - 
және    наборлар  координаттарының 
ґзара  әртүрлі  сандары), 
`

  шарт  орындалады  және  осы  наборға  сәйкес  келетін 
  
д.қ.ф. ядролық коньюнкциялар жиынтығынан тұйықты д.қ.ф. үшін   функциясы қалыптасады. 
 функцияның  тұйықты д.қ.ф.сын анықтайтын барлық наборлар жиынтығы
  функциясының 
 мәні тґменгі шекарасын кґрсетеді, ал оған д.қ.ф. ядролық коньюнкциялар жиынтығымен 
барлық тұйықты  д.қ.ф.   функциялар жиынтығы сәйкес келеді. 
 
Тґмендегі функцияны қарастыру 
`
( ) =
2

+
2
 
және  оны  есептеу  үшін  кґп  мґлшерде  жұмыс  қажет  емес,  ал 
( )  функциясының 
мәндерін  есептеу  үшін  тиісті  д.қ.ф.ға  кіретін  сәйкес  интервалдардың    нүктелер  жиынтығын 
қарастыру қажет және осы жиынтықта ґзара әр түрлі болған нүктелер есептеледі. 
 
Егер 
`
( ) <
  болса,  онда  ( )
<
,  сондықтан  алдымен   
`
( )  мәнін   
жиынтығы үшін, содан кейін қажет болған жағдайда осы  ( ) функциясының мәнін есептеу 
ұсынылады. 
 


Достарыңызбен бөлісу:
1   ...   38   39   40   41   42   43   44   45   ...   131




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет