Кез келген ҚҚФ ДҚФ-қа түрлендірудің алгоритмі

дизъюнкциясы  (конъюнкциясы).  Осындай  формула  берілген  формуланың 
дизъюнктивті ( конъюнктивті).  қалыпты түрі деп аталады. 
Жетілдірілген дизюнктивті қалыпты форма (ЖДҚФ) 
Анықтама. Айталық, А формуласы <
k
i
i
i
x
x
x
,...,
,
2
1
>  айнымалыларынан 
тәуелді  болсын.  Егер  төмендегі  шарттар  орындалса  А  формуласы  берілген 
айнымалылар  тізімінде  жетілдірілген  дизъюнктивті  қалыпты  формада 
делінеді. 
А-  дизъюнктивті  қалыпты  формада  (элементар  конъюнктер 
дизъюнкциясы)  
А-  ның  әрбір  дизъюнктивті  мүшесі  к-мүшелі  конъюнкция  және  бұл 
конъюнкцияның  әрбір 
l
-  орында  (
k
l
1
)  не 
k
l
x
  айнымалысы  не  оның 
терістеуі орналасады. А- ның барлық дизъюнктивті мушелері өзара әртүрлі. 
Мысалы, 
3
2
1
,
,
x
x
x
-айнымалылар тізімінде 
(
)
(
)
(
)
(
,
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
-дизъюнктивті қалыпты 
формалар. 
Жетілдірілген конъюнктивті  қалыпты форма (ЖКҚФ). 
Анықтама.    Айталық,  А  формуласы    <
k
i
i
i
x
x
x
,...,
,
2
1
>    айнымалыдан 
тәуелді болсын. Егер төмендегі шарттар орналаса А- берілген айнымалылар 
тізімінде жетілдірілген конъюнктивті қалыпты формада делінеді. 
А-конъюнктивті қалыпты формада  
А-ң  әрбір  мұшесі  к  мүшелі  дизъюнкция  және  бұл  дизъюнкцияның 
l
- 
ші  орнында  (
k
l
1
)  не   
k
l
x
  айнымалысының  не  өзі,  не  оның  терістеуі 
тұрса. 
А- ның барлық  конъюнктивті мүшелері өзара әр түрлі. 
Мысалдар. 
)
(
)
(
)
(
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
- ЖДҚФ 
)
(
)
(
)
(
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
- ЖДҚФ  емес. 
Берілген      формулаға  эквивалентті  ЖДҚФ,  ЖКҚФ  табу  есептерін 
шешу үшін, алдымен 
)
,...,
,
(
2
1
n
х
x
x
f
 буль функциясы үшін Шеннон жіктеуін 
қарастырамыз. 
Шеннон жіктелулері. 
Кез келген Буль функциясы Шеннон  жіктелуі түрінде өрнектеледі. 
)
(
)
(
1
1
,...
1
)
...
(
2
1
1
)
,...
,
(
1
1
нµмірлері
лар
ќ±рама
болатын
f
i
n
i
ќ±рамалары
лыќ
бар
болатын
f
n
i
n
n
x
x
x
x
f
    
Мысалы, 
)
,
,
(
3
2
1
x
x
x
f
  000,  010,  011  құрамаларында  1-ге  тең  болсын.  Олай 
болса, 
)
,
,
(
3
2
1
x
x
x
f
  жіктелуі:   
)
,
,
(
3
2
1
x
x
x
f
=
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
;  Осыған    ұқсас 
0-ге тең емес 
)
,...,
,
(
2
1
n
x
x
x
f
 функциялары төмендегідей болып жіктеледі: 

)
(
)
(
0
0
1
1
,...
0
)
...
(
2
1
1
1
)
,...
,
(
н м м
лар
р р
болатын
f
i
n
n
i
n
i
р р р
лы
бар
болатын
f
n
x
x
x
x
f
 
Бұл формулалардан төмендегі теореманы келтіруге болады. 
Теорема.    Кез  келген  Буль  функциясын    өрнектейтін      формула 
табылады Егер 
0
f
 
болса  оны ЖДҚФ түрінде өрнектейтін  жалғыз ғана формула бар. 
)
,...
,
(
2
1
1
1
)
...
(
1
n
f
K
n
 
Егер 
1
f
 болса оны ЖКҚФ түрінде өрнектейтін жалғыз ғана формула 
бар. 
)
,...
,
(
2
1
0
1
)
...
(
1
n
f
K
n
 
Мысалы,  ақиқаттық  кестемен  берілген 
)
,
,
(
z
y
x
f
  функциясының  ЖДҚФ, 
ЖКҚФ  табу керек. Функцияның толықтығы туралы теорема бойынша 
 
xyz
z
y
x
z
y
x
z
y
x
1
-ЖДҚФ; 
z
y
x
yz
x
z
y
x
z
y
x
2
-ЖКҚФ 
Сонымен ЖДҚФ, ЖКҚФ - белгілері.  
Дизъюнкцияның  (конъюнкцияның  )  мүшелері  әр  түрлі  конъюнктердің 
(дизъюнктердің) 
мүшелері 
әр 
түрлі 
бір 
де 
бірі 
конъюнкте 
(дизъюнкте)айнымалының әрі өзі ,әрі оның терістеуі бірге болмайды.  
Әрбір  конъюнктің  (дизъюнктің  )  құрамында формулаға  енетін  барлық 
айнымалылар болуы керек, яғни х
1
х
2
... х
3
  мұндағы х
і
 не 
i
x
 өзі , не  
i
х
. 
Мысалы, 
y
x
z
y
x
-өрнегі 
)
(
x
z
y
x
 
формуласының 
– 
дизъюнктивті  қалыпты  формаларының  бірі.  Бұл  ЖДҚФ-ң  алдыңғы  үш 
талабын қанағаттандырады, ал төртіншісін қанағаттандырмайды. Сондықтан 
оған түрлендірулер жүргіземіз  (
z
z
  көбейтміз).  
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
z
y
x
z
y
x
y
x
z
y
x
))
(
(
 
Кез  келген  F  (х
1
,х
2
...х
n
)  формуласын  ЖДҚФ    (ЖКҚФ  )  түріне  келтіру 
үшін мына ережені қолдануға болады. 
F  (х
1
,х
2
...х
n
  )    формуласын  қандайда  бір  дизъюнктивті  (конъюнктивті) 
қалыпты формаға түрлендіру.  
Егер  конъюнктке  қандай  да  бір  айнымалы    өзінің  терістеуімен  бірге 
кірсе оны ДҚФ- тан жою керек. (х   
х
 0) 
Егер конъюнктке бір литер х  бірнеше рет кірсе, олардың біреуін ғана 
қалдырып калғандарын  қысқарту керек.   (х   х  х) 
Егер конъюнктердің біріне (
k
k
x
x
x
...
2
1
2
1
  )  y  айнымалыc    кірмей  тұрса, 
онда  бүл  конъюнктті  оған  эквивалентті 
k
k
x
x
x
...
2
1
2
1
)
(
y
y
  формуламен 
алмастырамыз да, дистрибутивті заңды (x  (y z)) = xy   xz қолданып ДҚФ 

түріне  келтіреміз.  Егер  толық  емес  конъюнкт  бірнешеу  болса  олардың 
әрқайысысы үшін сәйкес 
)
(
y
y
 формуласын қосамыз. 
Алынған  ДҚФ-да  бірдей  бірнеше  конъюнктер  болса  олардың  (  х х) 
біреуін ғана қалдырамыз. Нәтижесінде ЖДҚФ шығады. 
Мысалы, 
YZY
X
X
X
 ДҚФ –ны ЖДҚФ-қа түрлендіру керек. 
YZY
X
X
X
))
(
)
(
(
X
X
YZ
Y
Y
X
[дистрибутивтік 
заңымен 
ашамыз]
YZ
X
XYZ
Y
X
XY
)
(
)
(
Z
Z
Y
X
Z
Z
XY
YZ
X
XYZ
YZ
X
XYZ
Z
Y
X
Z
Y
X
Z
XY
XYZ
Z
Y
X
Z
Y
X
YZ
X
Z
XY
XYZ
 
КҚФ-ны  ЖКҚФ  түрлендірудің  алгоритмі  де  осындай.  Мысал  арқылы 
көрейік. 
Z
Y
X
XY
XYZ
 формуланы ЖКҚФ ға келтіру керек  болсын. 
1.Формуланы  қандайда  бір  конъюнктивті  қалыпты  формаға    (КҚФ) 
келтіреміз. 
Z
Y
X
XY
XYZ
Z
Y
X
XY
Z
Y
X
 
Z
Y
X
Y
X
Z
Y
X
X
Y
X
Z
Y
X
;
Z
Y
X
Y
Y
X
 
2).  Бірдейлерін  жоямыз.  Айнымалының  терістеуімен  бірге  қатысып 
тұрған конъюнкция мүшесі,3 қайталанып тұрған конъюнкция мүшесі 1 мен 4. 
Y
X
Z
Y
X
ТОЛЫҚТЫРАМЫЗ
Z
Z
Y
X
Z
Y
X
 
Z
Y
X
Z
Y
X
Z
Y
X
жойылады
муше
тивтi
конъюнк
бiрдей
Z
Y
X
Z
Y
X
-Бұл ЖДҚФ 
Негізгі әдебиет:  2[180-185]; 3[172-193]. 
Қосымша әдебиет:: 7[50-80]  
Бақылау сұрақтары: 
1. 
Буль функцияларының негізгі қасиеттерін атаңыз.  
2. 
Логикалық  функцияларды  жіктеу  туралы  Шеннон 
теоремасы қандай? 
3. 
Буль 
алгебрасындағы 
негізгі 
эквиваленттік 
түрлендірулерді атаңыз.  
4. 
Функцияның ЖДҚФ,ЖКҚФ қалай табуға болады ? 
5. 
Қандай логикалық функцияда ЖДҚФ болмайды? 
 
Ақиқат кесте бойынша берілген. Буль функциясына формула құру 
әдісі. Буль функцияларының  түйіндестік принципі.  
Пікірлер  логикасының  әрбір  формуласына  ақиқат  кесте  құруға 
болатынын  білеміз.  Керісінше  қалай?.  Керісінше  де  яғни  ақиқат  кесте 
бойынша формула құруға болатынын көреміз.  
 
2. Осы құрамаларға сәйкес конъюнкция жазамыз. Егер х
і 
аргументінің 
құрамадағы  мәні  1-ге  тең  болса  ол  конъюнкцияға  өзгеріссіз  енеді,  ал  х
і
=0, 
болса конъюнкцияға оның терістеуі алынады. 

3.  Алынған  барлық  конъюнкциялардың    дизъюнкциясы  іздеген 
формула болады және ол құрылған функцияның  ЖДҚФ-ы болады. 
Мысалы, f (x1 ,x2,x3 )=
1
V
(3,4,6), f (x1 ,x2,x3 )=
V
1
(0,2,5,7) 
3,4,6-құрамалардың нөмірлері
  
0,2,5,7- құрамалардың нөмірлері
 
 
 
Ақиқаттық кесте бойынша ЖКҚФ құрудың алгоритмі.  
Алгоритмді  f  (x1  ,x2,x3  )  =
V
0
(0,3,7)  функциясына  ЖКҚФ  құруға 
қолданайық. 
1.  Кестеден  функцияны  0-ге  айналдыратын  аргументтерге  сәйкес 
құрамалар алынады(асты сызылады). 
2. Осы құрамаларға сәйкес дизъюнкция  жазамыз. Егер  х
і  
аргументінің 
құрамадағы  мәні  0-ге  тең  болса  ол  конъюнкцияға  өзгеріссіз  енеді,  ал  х
і
=1, 
болса конъюнкцияға оның терістеуі алынады. 
3. Алынған барлық дизъюнкциялар конъюнкциямен жалғастырылады. 
3
2
1
3
2
1
3
2
1
(
x
x
x
x
x
x
x
x
x
F
 
 
Анықтама.  Егер  f
*
(x
1
,x
2
,…,x
n
)=
)
,...
(
1
n
x
x
f
 
онда  f*(x
1
,x
2
,…,x
n
) 
функциясы  f(x
1
,x
2
,…,x
n
)  функциясына  түйіндес  функция  деп  аталады. 
f(x
1
,x
2
,…,x
n
)  функциясына  түйіндес  функцияны  анықтау  үшін,  барлық 
айнымалылар  және  функцияның  өзін  оның  қарама-қарсы  мәндеріне 
ауыстыру керек. 
Мысал. 
Үш 
айнымалыдан 
тәуелді 
)
&
)
((
)
~
(
)
,
,
(
2
3
1
2
1
3
2
1
x
x
x
x
x
x
x
x
f
 
функциясын  буль  формуласы  яғни 
ЖДҚФ-түрінде өрнектеу керек. 

 
Іздеп отырған ЖДҚФ 
)
,
,
(
3
2
1
x
x
x
f
= 
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
х
х
х
х
х
х
х
х
х
х
х
х
х
х
х
 
Түйіндестік  принципі:  Егер  f  функциясын  өрнектейтін  F 
формуласындағы  барлық  операция  белгілерін  түйіндес  функцияның 
операция  белгілеріне  алмастырғаннан  алынған  F*  формуласы  берілген  f 
функциясының түйіндес функциясын өрнектейтін болады. 
Тек 
, 
,  а,  ж  символдарымен  ғана  байланысқан  формулаларды 
қарастырамыз.  ,  , а, ж  символдары бір біріне түйіндес деп аталады.  
Мысалдар: ақиқат–формуласының түйіндесі - жалған;  
 
Егер  f
1
,  f
2
  функциялары  тең  болса,  онда  оларға  сәйкес  түйіндес 
формулалар  да  тең  болады. 
2
1
f
f
  онда 
*
2
*
1
f
f
.  Түйіндестік  принцип 
дизъюнкция,  конъюнкция,  терістеу  арқылы  байланысқан  формулалармен 
берілген  функциялардың  түйіндестерін  табу  үшін  ыңғайлы.  Бұл  жағдайда 
берілген  формулада  конъюнкция  дизъюнкцияға,  дизюнкция    конъюнкцияға 
ауысады. Сөйтіп ДҚФ–КҚФ, КҚФ-ДҚФ, ЖДҚФ–ЖКҚФ немесе керісінше. 
Мысалы: (
)
(
)
(
)
(
)
*
z
y
x
z
x
y
x
z
y
x
xz
xy
 
Егер    формуласы  -ге  эквивалент  болса:
  онда  оларға  сәйкес 
түйіндес формулалар да эквивалентті болады ,яғни  *
 
* болады. 
Егер f*
 
(x
1
,x
2
,…,x
n
)=f(x
1
,x
2
,…,x
n
) онда f(x
1
,x
2
,…,x
n
) функциясы өзіне-өзі 
түйіндес  функция  деп  аталады.  Мысалы,    xy xz yz  функциясы  өзіне  өзі 
түйіндес  функцияны  кескіндейді.  Оған  (б
1
,б
2
,б
3
)  және  (1-б
1
,  1-б
2
  ,  1-б
3
) 
жиынтықтарының  қарама-қарсы  мәндерінде  функция  да  қарама-қарсы  мән 
қабылдайтындығына көз жеткізуге болады. Ол үшін ақиқаттық кесте құрып: 
 
екендігін көреміз. 
Мысал:  Түйідестік  принципіне  сүйене  отыра,  буль  алгебрасындағы 
түйідестік  принципінің  дұрыстығын  дәлелдеу  керек.  Буль  алгебрасында 
)
,
;&,
(
2
P
 үш амал бар:
}
,
{&,
;   
Буль алгебрасының әр бір амалына түйіндес амалдарды анықтайық. 
а) Айталық, 
y
x
y
x
f
)
,
(
 болсын. 

Олай болса 
y
x
y
x
f
y
x
f
)
,
(
)
,
(
*
y
x
; 
б) Айталық, 
)
,
(
y
x
f
y
x
;Олай болса 
y
x
y
x
f
y
x
f
)
,
(
)
,
(
*
y
x
; 
в) Айталық, 
)
(x
f
x
; Олай болса 
x
x
x
f
x
f
)
(
)
(
*
; 
Сонымен  конъюнкция  дизъюнкцияға,  дизъюнкция  конъюнкцияға 
түйіндес, ал терістеу өзіне өзі түйіндес. 
Негізгі әдебиет: 1[49-54]; 2[192-197]. 
Қосымша әдебиет: 7[50-80] . 
Бақылау сұрақтары: 
1.  Қандай  функциялар  бір-біріне  түйіндес  деп  аталады?  Мысал 
келтіріңіз. 
2. Ақикаттық кесте бойынша формула құру ережелері 
 
8-дәріс. Буль функцияларының толық жүйелері. Пост теоремасы  
 
Буль  функцияларының  толық  жүйелері.  Кез  келген  логикалық 
функция  өрнектелетін  логикалық  операциялардың  жиынтықтары  болады. 
Мұндай  операциялар    жиыны  функционалды  толық  жүйелер  немесе  базис 
деп аталады. Функционапды толық жүйелерге немесе базистерге мысалдар. 
{ ,  ,  }; { ,  }; { , }; { }; { }; { , ,1}; {
, }; { , , }; { ,  ,  }; т.б  
Бұлардың  ішінде  көбірек  зерттелгені  { ,  ,  }-базис;  Бұлар  буль 
формулалары деп аталады. 
Анықтама.  Логикалық  функциялар  жиыны  Р
2
-негізгі  жиыны,  ал 
операциялары-дизъюнкция,  конъюнкция,  терістеу  болатын  {Р
2
; 
, 
,  } 
алгебрасы логикалық функциялардың бульдік алгебрасы деп аталады. 
1-Теорема.  Кез  келген  логикалық  функция  буль  формуласы  түрінде 
кескінделеді  яғни  дизъюнкция,  конъюнкция,  терістеудің  суперпозициясы. 
Бұдан  буль  формулаларының    жүйесі 
{ ,  ,  };  функциональды  толық 
жүйе. Бұл кесте түрінде берілген кез келген функцияны буль алгебрасының 
формуласы түрінде кескіндеуге болатындығын көрсетеді. 
2-Теорема. 
Егер  функционалды  толық 
*  жүйенің  барлық 
функциялары    -жүйенің  формулалары  арқылы  өрнектелетін  болса,онда  -
жүйе де функционалды толық жүйе болады. 
Кез келген жүйенің толықтығы туралы сұраққа Пост теоремасы жауап 
береді: 
Пост кластарының анықтамасы. 
Р
0
–класы.  Бұл  0-ді  сақтайтын  буль  функциялары  класы,  яғни 
f(0,0,…,0)=0 болатын функциялар.    Р
0
  f   f (0,0,…,0) = 0}. 
Р
1
–класы.  1-ді  сақтайтын  функциялар  класы,  яғни  f  (1,1,…,1)  =1 
болатын функциялар.  Р
1
  f   f (1,1,…,1) = 1} 
S-өзіне-өзі  түйіндес  функциялар  класы.  S={f    f-өзіне-өзі  түйіндес 
функция} 

М–монотонды  функциялар  класы.  Кез-келген  (
1
,  ...,
n
)  және  (
1
, 
2
,...,
n
)  нөлдер  мен  бірлер  жиынтығында   
1
1
,...,
n
n
  шарттың 
орындалуынан 
f(
1
,…,
n
) f(
1
,…,
n
)  орындалса  f(х
1
,х
2
,…,х
п
)  функциясы  монотонды 
деп аталады. М {f   f–монотонды функциялар}. 
5. L-сызықты функциялар класы. 
Егер 
буль 
сақинасында 
<{0,1}, 
, 
> 
f-функциясы 
f(х
1
,х
2
,…,х
п
)=c
0
c
1
x
1
c
2
x
2
… c
n
x
n
  түрінде  өрнектелетін  болса,  мұндағы 
с
1
,с
2
,...,с
n
{0,1}  онда  Буль  функция  сызықты  деп  аталады.  c
0
с
1
с
2
,...,с
n
 
коэфициенттері төмендегідей анықталады. 
с
0
=f(0,0,…,0),  c
0
c
1
=f(1,0,…,0),  c
0
c
2
=f(0,1,…,0),...,c
0
c
n
=f(0,0,…,1) 
яғни с
0 
=f(0,0,…,0),  c
1
=c
0
f(1,…,0),…,с
n
=c
0
f(0,0,…,1) 
Сонымен 
f–функциясының 
сызықтығын 
тексеру 
деген 
с
i
 
коэфициенттерінің  тауып,  берілген  формуланың  ақиқаттық  кестесімен 
табылған  c
0
с
1
х
1
... c
п
х
п
  формуланың  ақиқат  кестесін  салыстыру  болып 
табылады. Мысалы. x y функциясы сызықты ма ? 
Тексеру: c
0
=o o=o; c
1
=c
0
f(1,0)=0 (1 0)=1; c
2
=0(f(0,1))=0 (0 1)=1; 
Сонымен c
0
c
1
х c
2
y x y;  x v y пен  x y ақиқат кестесі бірдей емес. 
Ендеше  x  v  y–cызықты  емес.  Егер  функцияның  ЖДҚФ  тұріндегі  V–
операциясының  орнына    қойылса  онда  сызықты  функцияның  мүлтіксіз 
полиномды қалыпты түрін аламыз. (МПҚФ) (дизъюнкция белгісінің орнына 
). Бұл Жегалкин полиномы деп аталады. 
Мысалы.  F(x
1
,x
2
,x
3
)=(x
2
x
3
) (x
1
x
2
)  функциясын  2  модулі  бойынша 
қосу полиномы түрінде жазу керек.  
f(x
1
,  x
2
,  x
3
)=(
2
x
x
3
) (x
1
x
2
) (x
2
, 
x
3
, 
1) (x
1
x
2
, 
x
1
x
2
) (x
2
, 
x
3
, 
1)  
(x
1
x
2
x
1
x
2
1) (x
2
, 
x
3
, 1)
x
1
x
2
x
1
x
2
1 (x
2
, 
x
3
, 1) (x
1
x
2
x
1
x
2
1)= 
x
1
x
3
x
1
x
2
x
1
x
2
x
2
x
1
x
2
x
2
x
1
x
3
x
2
x
3
x
1
x
2
x
3
x
3
x
1
x
2
x
1
x
2
1= x
2
x
1
x
3
x
2
x
3
x
1
x
2
x
3
1 
(P
2
, 
, 
,  1)–Жегалкин  алгебрасы  деп  аталады. 
={   , ,1}  болып 
белгіленеді: 
        сигнатура деп аталады. 
Анықтама. 
Егер 
Жегалкин 
көпмүшелігінің 
құрамында 
айнымалылардың  көбейтіндісі  бар    болса,  онда  көпмүшелік  сызықты  емес 
деп аталады, жоқ болса сызықты деп аталады.  
Буль  функциясының  сызықтылығы  Жегалкин  көп  мүшелігінің 
сызықтылығымен  эквивалентті  яғни  Жегалкин  көпмүшелігі  сызықты  болса 
оған сәйкес буль функкциясы да сызықты болады. 
Мысал.  f(x
1
y)=x y 
функциясы  Пост  класстарының  қайсысына 
жататынын анықтау керек. 
f(0,0)=1; f(1,1)=0,  f(x
1
y) P
o
 және f(x
1
y) P
1
 
f(1,0) f(0,1) болғандықтан f(x, y) S; 
f(0,0) f(1,1) болғандықтан f(x, y) M; 

f(x, y) функциясы үшін Жегалкин көпмүшелігі f(x, y)=x  y=
y
x
xy
 
)
1
(
)
1
(
1
y
x
x
x
=(x 1) (y 1)сызықты  емес.  Мынадай  кесте 
құруға  болады:  Пост  теоремасы  Буль  функциялар  жүйесі  Ғ  толық  жүйе 
болады тек сонда ғана, егер әрбір P0, P,S,M,L кластары үшін Ғ жүйесінен осы 
класқа жатпайтын функция табылса. 
 
Бұл  теоремадан  жоғарыдағы 
y
x
  функция  толық  жүйе  құрады,  яғни 
Шеффер функциясы  арқылы кез келген буль функциясын алуға болады: 
х x x, x y
y
x
y
x
~
(x y)(x y) 
Буль  функциялар  жүйесі  толық  болса  базис  деп  аталады,  ал  жүйеден 
кез келген функция алынып тасталса жүйе толық емес болады. 

жүктеу/скачать 3,62 Mb.

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