Графтар теориясының элементтері

27 
Кестеде Пост класына тиісті буль функциялар (тиісті – (+); тиісті емес – 
(-)) мысалдары көрсетілген. 
2.2.7 кесте 
Функция 
0
P
1
P
L
M
S
Теріске 
шығару 
- 
- 
+ 
- 
+ 
Конъюнкция 
+ 
+ 
- 
+ 
- 
Дизъюнкция 
+ 
+ 
- 
+ 
- 
Импликация 
- 
+ 
- 
- 
- 
Бір логикалық функция әртүрлі логикалық қисаптар енген жиынтық 
арқылы берілуі мүмкін. Мысалы, 
2
1
2
1
2
1
|
x
x
x
x
x
x




. Кез келген логикалық 
функцияларды өрнектей алатын логикалық қисаптар (функциялар) жиынтығы 
бар. 
Анықтама.
 
Егер кез келген логикалық функция 

-дағы функциялардың 
суперпозициясы болса, онда 

логикалық функциялар жүйесі толық жүйе 
немесе базис деп аталады.
Кез келген жүйенің толықтығын келесі теоремадан білуге болады. 
Пост теоремасы. Буль функцияларының жүйесі толық болуы үшін осы 
жүйеде 0-ды сақтамайтын ең болмағанда бір функция, 1-ді сақтамайтын ең 
болмағанда бір функция, ең болмағанда өзқосалқы бір функция, ең болмағанда 
сызықты бір функция, ең болмағанда монотонды бір функция болуы қажетті 
және жеткілікті. 
Буль функцияларының жүйесі толықтығын анықтау үшін осы 
функциялардың Пост классына тиістілік кестесін қолдануға болады. Мысалы, 
 




,
1
жүйесінде теріске шығару константаны сақтамайды және
монотонды емес, ал конъюнкция сызықты емес және өзқосалқы емес (кесте 
2.2.7), онда бұл жүйе толық. Мысалы, функционалды толық жүйелер: 
},
,
,
{



}
,
,
{
},
,
,
{
},
,
{
},
1
,
,
{
},
{
},
{
},
,
{
},
,
{















және т.б. Айнымалылар, 
жақшалардан басқа конъюнкция, дизъюнкция және теріске шығару 
қисаптарынын тұратын формулалар буль формулалары делінеді. 

Теорема.
 

Кез келген буль функциясы
 
буль формуласы түрінде жазыла 
алады (яғни конъюнкция, дизъюнкция және теріске шығарудың 
суперпозициясы түрінде).
Бұдан 
}
,
,
{



жүйесінің функционалды толықтығы шығады. Қандай да 
бір қисаптар жиынтығының функционалды толықтығын дәлелдеу үшін
қисапты конъюнкция, дизъюнкция және теріске шығару арқылы өрнектеуге 
болатындығын көрсету керек. Жүйенің толықтығын дәлелдейтін жалпы 
тұжырымдар да бар.

 
Теорема.
 
Егер 


функционалды толық жүйенің барлық функциялары 

-
ның формулалары түрінде көрсете алса, онда, 

да функционалды толық жүйе.

28 

Мысалы 2.2.6
-
 
 




,
1
және 
 




,
2
жүйелерін, 
0

=
}
,
,
{



базисін 
қарастырамыз. 
1

, 
2

жүйелерінің базис болатындығын дәлелдеу керек. 
Расында, 
0

-да бар, бірақ әрбір жүйеде жетіспей тұрған қисаптарды қалған 
екеуі арқылы өрнектеуге болады: 
1

-де «

» жетпей тұр:
1
2
1
2
x
x
x
x

 
2

үшін жетпей тұр «

»:
1
2
1
2
x
x
x
x

 
(

) .
1

, 
2

жүйесіндегі

f
)
(
4
3
2
2
1
x
x
x
x
x


формуласы келесі түрде жазылады: 

f
=[
1

]
4
3
2
2
1
x
x
x
x
x





, 

f
[
2

]
4
3
2
2
1
x
x
x
x
x





. 
Сонымен, функционалды толық жүйелер мағынасында 
0

жүйесін 
шамадан тыс деп есептеуге болады, себебі одан дизъюнкция немесе 
конъюнкцияны алып тастасақ та толықтықтың қасиетін сақтайды. Бірақ
1

, 
2

жүелерін (

) формулаларымен толықтықтандыру үшін формулада шамадан тыс 
теріске шығаруға әкеліп соқтырады.
 
2.3 
Дәріс 6. Дизъюнктивті және конъюнктивті қалыпты
формалар (ДҚФ, КҚФ) 
 
Дәріс мазмұны: ДҚФ және КҚФ; МДҚФ және МКҚФ. 
Дәріс мақсаты: 
}
,
,
{



базисін таңдау себептері; ДҚФ пен КҚФ-ке 
келтіру; МДҚФ пен МКҚФ-ке келтіру. 
 
0

=
}
,
,
{



базисі зерттелген және жиі қолданылады, басқа базистер осы 
базиске келтіріледі. Осы базиске келтірудің әртүрлі әдістерін қарастырайық. 

Анықтама.

 
Элементар конъюнкция (дизъюнкция) деп айнымалылардың 
конъюнкциясы (дизъюнкциясы) немесе олардың терістеуі айтылады.

Мысалы 2.3.1
–
а) 
z
y
x


және 



x
y
x
элементар дизъюнкциялар;
б) 
1 2 3
x x x
және 



3
2
1
x
x
x
элементар конъюнкциялар;
в)

x
бір мезгілде элементар дизъюнкция және элементар конъюнкция. 

Анықтама.

 
Дизъюнктивті қалыпты форма (ДҚФ) деп элементар 
конъюнкциялардың дизъюнкциясы айтылады. Конъюнктивті қалыпты форма 
(КҚФ) деп элементар дизъюнкциялардың конъюнкциясы айтылады. 

Мысалы 2.3.2
-
а)


yz
y
x
ДҚФ,
б) 
(
)(
)(
)
x
y x
z y
x
z


  
КҚФ. 
Теорема.
 
Кез келген
 
формула ДҚФ (КҚФ)-ке келтіріледі (яғни кез келген
 
формула қандай да бір ДҚФ (КҚФ) эквивалентті). 
 
ДҚФ-ке келтіру ережелері: 
а) формуладағы барлық логикалық қисаптарды, эквиваленттілікті 
қолданып, 
}
,
,
{



арқылы өрнектеу керек: 
1) 






~
)
(
; 
}

29 
2) 
)
(
)
(
~
)
(










; 
3) 





~
|
; 
4) 






~
; 
5) 
)
(
)
(
~
~













; 
б) теріске шығаруды де Морган заңы бойыша ашу керек:












~
,
~
; 
в) дистрибутивтік заңын қолданып, формуладағы барлық конъюнкциялар 
дизъюнкциядан 
бұрын 
орындалатындай 
етіп 
түрлендіру 
керек: 
)
(
)
(
)
(













. 

Мысалы 2.3.3
-
z
y
y
x




)
(

формуласын ДҚФ-ке келтіру керек. 
Ол үшін 


,
қисаптарын 



,
,
қисаптарына айырбастаймыз, содан соң де 
Морган және екі рет терістеу заңдары бойынша:
)
(
)
(
)
(
)
(
z
y
y
x
z
y
y
x









=
)
(
)
(
z
y
y
x



= 





)
(
)
(
z
y
y
x
)
(
)
(
)
(
)
(
z
y
x
y
y
x
z
y
y
x









. 
Айта кетелік, мысалдағы соңғы формула кейбір оқулықтарда ДҚФ болып 
есептелінеді, басқа оқулықта элементар конъюнкцияяда және дизъюнкцияда 
әрбір айнымалы бір ақ рет кездесу керек. Артық айнымалылардан арылу үшін 
келесі эквиваленттілік қолданылады: 
а) 










,
(идемпотенттік заңы);
б) 
1
 
 
(жойылған үшінші заңы), 
0
 
 
(қарама-қайшылық заңы);
в) 
1
1
,
1







, 







0
,
0
0
- (константалар қасиеті).
Идемпотенттік заңын қолданып, соңғы мысалдағы ДҚФ аламыз: 
(
)
(
)
x
y
x
y
z


   
.
 
КҚФ-ке келтіру ережелері ДҚФ-ке келтіру сияқты, тек в) пункті орнына 
в

) қолданылады: 
в

) 
дистрибутивтік 
заңын 
қолданып, 
формуладағы 
барлық 
дизъюнкциялар конъюнкциядан бұрын орындалатындай етіп түрлендіру керек:: 
(
)
(
)
(
)
  
 
 






. 
Мысалы 2.3.4
-
)
)
((
)
(
x
z
y
y
x






формуласын КҚФ-ке келтіру 
керек. 
 

қисабын 
y
x
y
x



)
(
формуласын қолданып түрлендіреміз: 
(
)
((
)
)
(
)
((
)
)
x
y
y
z
x
x
y
y
z
x

 

 
 

 

[ де Морган, екі рет терістеу 
заңдары] =
)
(
)
(
)
(
)
)
((
)
(
x
z
x
y
y
x
x
z
y
y
x










- КҚФ. 
ДҚФ және КҚФ формаларын кемшілігі – оларға жалғыздық қасиеті 
орындалмаыды, бір формуланың бірнеше ДҚФ және КҚФ бар. Бұндай кемшілік 
мүлтіксіз қалыпты формаларда жоқ. 
Анықтама.
 
Мүлтіксіз дизъюнктивті қалыпты форма
 
(МДҚФ) деп 
мынадай ДҚФ айтылады:
 
әрбір элементар конъюнкцияға әрбір айнымалы бір ақ 
рет енеді және не тек өзі, не оның терісі ғана, элементар конъюнкция арасында 
бірдейлері болмау керек. 

30 

жүктеу/скачать 1,03 Mb.

Достарыңызбен бөлісу: