-  дәріс.  Буль  функциялары

Бірлік  жиын  тықтар      f  –  функцияның  бірлік  жиыны  деп  аталады  Осыған 
ұқсас   f = 0  болатын мәндер жиынтығы f – функцияның нольдік жиыны деп 
аталады.    f  (x
1
x
2
,…,x
n
)      функция 
суреттегідей    ақиқаттық  кестемен 
анықталады.Егер    f  буль  функциясы 
мен 
  формуласының  ақиқаттық 
кестелері бірдей болса,    формуласы  
f    функциясын  өрнектейді  деп 
айтамыз 
Егер 
)
,
,
,...,
(
)
,...,
,...,
,...,
,
(
1
1
1
1
2
1
n
n
i
i
n
i
i
x
x
x
x
g
x
x
x
x
x
f
 
 
болса  
)
,...,
,
,
,...
,
(
1
1
2
1
n
i
i
i
x
x
x
x
x
x
f
      формуласындағы 
i
x
  аргумент  маңызсыз 
(фиктивный)  деп  аталады.  Бұл  жағдайда 
).
,...,
,...,
,
(
)
...,
,
(
1
2
1
2
1
n
i
n
x
x
x
x
g
x
x
x
f
   
Шын  мәнінде 
f
- n  
айнымалыдан  тәуелді,  ал
f
g
тен  маңызсыз 
айнымалыны  шығарып  тастағаннан  алынды  дейді.    Нөлден    немесе  бірден 
тұратын құрамалардағы 0 немесе 1 мәнін қабылдайтын f(x
1
,…,x
n
) функциясы 
түрақты деп аталады. f(x
1
,x
2
,…,x
n
) 0;   f(x
1
,x
2
,…,x
n
) 1. 
Логикалық алгебраның элементар функциялары. 
Логикалық алгебрада бір немесе  2  айнымалысы бар унарлы, бинарлы 
операциялар  көп  қолданылады.Бір  айнымалысы  бар  барлық  логикалық 
функциялар жиынтығы кестеде берілген.     
3
0
,
- 0,1 тұрақтылары.Олардың 
мәндері 
x
-тен тәуелсіз. Демек 
x
-ң мәні оларға маңызсыз (фиктивная).  
;
1
)
1
(
;
0
)
0
(
3
0
 
1
)
0
(
0
)
1
(
3
0
  -
x
-мәніне  тәуелсіз
x
x)
(
1
    -
x
-ті 
қайталайды; 
1
)
1
(
0
)
0
(
1
1
,   
)
(
2
x
x
-ң  терістеуі  деп  аталады   
)
(
2
x
x
айнымалысы  бар  логикалық  функциялардың  жиынтығы  төменде 
берілген. 16 функция бар 
Мысалы, 
1
(x
1
,x
2
)=x
1
&x
2
=x
1
 
x
2
–коньюнкция деп аталады. 
7
  (x
1
,x
2
) = x
1 
v x
2
  (логикалық қосу, «немесе» операциясы) 
1. 
0
, 
15 
- константалар  
2. конъюнкция : 
1
 (x
1
,x
2
) =
а
жаѓдайлард
ќалѓан
x
х
егер
,
0
1
,
1
2
1
  
3. импликацияға кері функция: 
а
жаѓдайлард
ќалѓан
x
x
егер
x
x
,
0
0
,
1
,
1
)
,
(
2
1
2
1
2
 
4. 
1
2
1
3
)
,
(
х
x
x
 
5. 
а
жаѓдайлард
ќалѓан
x
x
егер
x
x
,
0
1
&
0
,
1
)
,
(
2
1
2
1
4
 
6. 
2
2
1
5
)
,
(
х
x
x
 
7. 2-ң модулі бойынша қосу.
)
(
,
2
1
2
1
x
x
x
x
: 
болса
т‰рлі
єр
мєндер
аќиќаттыќ
егер
болса
бірдей
мєндері
аќиќаттыќ
x
x
егер
x
x
x
x
,
1
,
,
0
)
,
(
2
1
2
1
2
1
6
 

8. Дизьюнкция:  
а
жаѓдайлард
ќалѓан
x
x
егер
х
х
x
x
,
1
0
,
0
)
,
(
2
1
2
1
2
1
7
 
9. Пирс бағыты:  
а
жаѓдайлард
ќалѓан
x
x
егер
х
х
x
x
,
0
0
&
0
,
1
)
,
(
2
1
2
1
2
1
8
 
10.Эквиваленция:
болса
т‰рлі
єр
мєндер
аќиќаттыќ
егер
болса
бірдей
мєндері
аќиќаттыќ
x
x
егер
x
x
x
x
,
0
,
,
1
~
)
,
(
2
1
2
1
2
1
9
 
11. 
2
)
,
(
2
1
10
х
x
x
 
12. 
а
жаѓдайлард
ќалѓан
x
x
егер
х
х
x
x
,
1
1
&
0
,
0
)
,
(
2
1
2
1
2
1
11
 
13. 
1
)
,
(
2
1
12
х
x
x
 
14. импликация :
)
(
2
1
x
x
 
а
жаѓдайлард
ќалѓан
x
x
егер
х
х
x
x
,
1
0
&
1
,
0
)
,
(
2
1
2
1
2
1
13
 
15. Шеффер штрихы:
2
1
| x
x
 
а
жаѓдайлард
ќалѓан
x
x
егер
x
х
x
x
,
1
1
,
0
)
,
(
2
1
2
1
2
1
14
 
16. константа: 
1
)
,
(
2
1
15
x
x
 
 
Бұл  16 функцияның ішінен  
0
, 
15 
– 0 және 1 константалары, яғни екі 
маңызсыз  айнымалы        функция.    Қалғандардың  ішінен  жиі 
қолданылатындары: 
 
 
элементар функциялар болып есептеледі.   ,   ,     ,    ,    ,    ,   ,    
Үш  және  одан  көп  айнымалысы  бар  функиялар  ақиқаттық  кесте 
арқылы  және  айнымалылардың  символдары  және  оларға  қолданылған 
унарлы,  бинарлы  операциялардың  символдарынан  тұрады.  Мысалы; 
f(x
1
,x
2
,x
3
)=(
2
1
х
х
) 
  (  x
1
x
3 
)  функция  x
1
,x
2
,x
3
  символдарынан  және  ( ), 
(
),( ),( )  операцияларынан  тұрады.Сонымен  формулалар  ақиқаттық 
кестеге қоса функцияны (берілу) өрнектеу және есептеу үшін қолданылады.  
Жалпы  жағдайда  формулалар  логикалық  функцияны  басқа  элементар 
функциялардың суперпозициясы түрінде сипаттайды. 
Суперпозициялар 
Анықтама.  Функция аргументтерінің орнына  элементар немесе басқа 
да  функцияларды    (f
1
,f
2
,…,f
k
)    қою  арқылы  алынған  жаңа  функция    (F) 
функциясы      f
1
,f
2
,…f
k 
 
 
функцияларының  суперпозициясы  деп 
аталады.Мысалы, 
терістеу, 
коньюнкция, 
дизьюнкция, 
импликация, 
эквиваленция  функциялары  арқылы  олардың  суперпозициясы  болып 
табылатын логикалық  алгебраның жаңа функцияларын жазуға болады: 

х
2
 
   x
1 
; x
1
   
2
х
; (x
1
   x
2
) 
 (
3
1
х
х
); ((x ~x
3
) х
1
)
(x
2
1
х
)  т.б 
Егер  формулада  операция  таңбасы  аргументтердің  арасында 
тұрса,ондай жазуды инфиксті жазу деп атайды. f
1
=x
3
x
1
;  f
2
=x
1
x
2
;f
3
=x
1
(f
2
); 
f
4
=(x
3
x
1
) (x
1
(x
1
x
2
)); 
Элементар  функциялардың  ақиқаттық  кестесі  арқылы  олардың 
суперпозициясы  болып  табылатын  кез  келген  функцияның  ақиқат  кестесін 
анықтауға болады. 
f(x
1
,x
2
,x
3
)  =  {[(
1
х
  ~  x
3
)      (  x
1
    x
2
)]    (  x
1
 
  x
2
)}
  x
3
    функциясын 
ақиқаттық кесте арқылы өрнектеу  керек болсын;   
Жақшаларды  қою  ретіне  логика  алгебрасында  арнаулы  келісімдер 
қабыл  данған:  Сыртқы  жақшалар  жазылмайды.  Мысалы,    (  (x у
z)) 
өрнегінің  орнына        x у
z    жазуға  болады.  Операциялардың  орындалу 
приоритеттері: 
(   ,  ,   ,  
 ,
,    ,     ,     , ); 
 
Мысалдар: 
1. x y z  өрнегі ((x y) z ) болып жазылады. 
2. x y
z
u өрнегі ( (x   y )   ( z u ) болып жазылады. 
3.  x y
z
u v w x y  өрнегі  ((x y)
(
z
(u (((v w) x) y)  болып 
жазылады 
4.  x
(
y
z)  өрнегінде  жақшаны  қалдыруға  болмайды.  Жақшасыз 
жазылса (x
y
)
z болып  кетеді. 
Логикалық  алгебра  функциясын  бульдік  функция,  екілік  функция 
(двоичная)  немесе  ауыстырып  қосқыш  (переключательная)  функция  деп 
атайды.Буль  функциялары  арқылы  қандай  да  бір  құрылғыға  берілген 
сигналдардың  қортынды    сигналға  түрленуін  белгілеуге  болады.  Мысалы, 
суретте  көрсетілгендей  қүрылғының    n  нүктеден  тоқ  қабылдау  мүмкіндігі 
бар.  Құрылғыларға  берілген  токқа  байланысты    xi=1  айнымалының  мәні 
тоқтың    i-  ші  нүктеге  берілуін  көрсетеді,    xi=0    тоқ  жоқты  көрсетеді. 
f(б1б2,...,бт)  =  1  тоқтың  шығу  нүктесін  берілуін,  f  =  0  болуы  тоқтың 
берілмеуін көрсетеді. 
1-мысал. коньюнкция  X   Y – екі тоқ беру нүктесі, бір шығу нүктесі 
бар    құрылғыны көрсетеді.  Шығу  нүктесіне  тоқ    беріледі, егер   x,y-    ке  тоқ 
берілсе.  
 

2-мысал.  Үш  адамнан  тұратын  комиссяның  дауыс  беруін  белгілеп 
отыратын  құрылғыны  қарастырайық.  Комиссия  мүшелері  резолюцияға 
(ұсынылған  шешім)  өз  кнопкасын  батырады.Егер  комиссия  мүшелерінің 
көпшілігі  резолюцияны  мақұлдаса,  онда  резолюция  (шешім)  қабылданады 
Бұл регистрация жасайтын құрылғымен белгіленіп отырылады 
 
Құрылғының  жұмысының  ақиқаттық  кестесі  суретте  көрсетілгендей 
функциямен  сипатталады;    алынған  функцияны    f(0,0,0)  =  f(001)  =  f(010)  = 
f(100) = 0  теңдіктер жүйесімен де беруге болады. 
(  0  0  0  1  0  1  1  1  )–жиынтығы  f  функциясының  мәндер  векторы  деп 
аталады. 
Қосымша әдебиет: 7[50-80] . 
Негізгі әдебиет: 1[46-49];  9[194-200]  
Қосымша әдебиет:  7[9-34]  
Бақылау сұрақтары: 
1. Қандай функциялар логикалық деп аталады? 
2. Бір айнымалыдан тәуелді барлық функцияларды атаңыз. 
3. n айнымалыдан тәуелді неше логикалық айнымалылар бар  ? 
4. Қандай айнымалылар негізгі деп аталады,қандайлары –жалған? 
5. Логка алгебрасының қандай формулалары эквивалентті деп аталады? 
 
7-Дәріс 
тақырыбы. 
Логикалық 
алгебра 
функцияларын 
аналитикалық түрде жазу. ДҚФ, КҚФ, ЖДҚФ, ЖКҚФ.  
 
Анықтама.  Егер  x  логикалық  айнымалы, 
  {0,1}  болса,  онда 
0
,
1
,
егер
x
егер
x
x
 өрнегі литер деп аталады. 
x
x  
,
 литерлері контрарлы литерлер 
деп аталады. 
Анықтама. 
Егер 
формула 
айнымалылар 
немесе 
олардың 
терістеулерінің  дизъюнкциясы  болса  (бір  мұшелі  болуы  да  мүмкін)  оны 
элементар дизъюнкция (дизъюнктер) деп атайды. 
Мысалдар. x
2
,x
3
;  x
1
x
2
x
3
, x
1
x
2
x
3
;  x y z;  x y x–дизъюнктер. 
Анықтама. 
Егер 
формула 
айнымалылар 
немесе 
олардың 
терістеулерінің  конъюнкциясы  болса  (бір  мұшелі  болуы  да  мүмкін)оны 
элементар конъюнкция (конъюнктер) деп атайды.   
х
1
, x
2
, x
1
x
2
 ,
3
x
, 
3
&
2
x
x
, 
3
2
& x
x
, x
1
x
2
x
3
;  
3
1
& x
x
&
2
4
& x
x
 
х- бір уақытта дизъюнкт те, конъюнкт те бола алады. 
Анықтама.  Конъюнктердің  дизъюнкциясы  дизъюнктивті  қалыпты 
форма  (ДҚФ    Элементар  конъюнкциялардың  дизъюнкциясы)  деп,  ал 
дизъюнктердің  конъюнкциясы  конъюнктивті  қалыпты  форма  деп  аталады 
(КҚФ-Элементар дизъюнкциялардың конъюнкциясы). 

Мысалы. ДҚФ: 
2
х
,
3
х
, 
y
x
,  
3
2
1
&
&
х
х
х
, 
y
x
yz, 
3
2
1
3
2
1
&
&
&
&
х
х
х
х
х
х
 
КҚФ: (x y
z
) (x z)y;  – ДҚФ;   
y
x
- КҚФ-те ДҚФ-те бола алады. 
1-Теорема.  Кез-келген  А  формуласы  үшін  оған  эквивалентті  қалыпты 
дизъюнктивті  формадағы    В  формуласын  (А  В)  табуға  болады.  В  А-ның 
қалыпты  дизъюнктивті  формуласы  деп  аталады.Дәлелдеусіз  (кез  келген 
формула өзінің ДҚФ,КҚФ эквивалентті ). 
Формуланы дизюнктивті қалыпты формаға келтірудің алгоритмі 
1. Формула құрамындағы барлық логикалық операцияларды 
),
(
~
)
(
 
),
(
)
(
~
)
(
  эквиваленттіліктер  және 
, ,  
операцияларының 
анықтамаларын 
пайдаланып 
дизъюнкция, 
конъюнкция, терістеу арқылы өрнектейміз. (Дизъюнктивті қалыпты формаға 
түрлендіру )  
2.  Морган  заңын  пайдаланып,  барлық  терістеулерді  айнымалыларға 
көшіріп, қос терістеулерді  
x
x
 формуласы бойынша қысқартамыз. 
Дистрибутивті 
))
(
)
((
~
))
(
(
  заңды  пайдаланып, 
форму-ланы 
барлық 
конъюнкциялар 
дизъюнкциялардан 
бұрын 
орындалатындай  түр-лендіреміз.  1-3  пункттерді  орындаудың  нәтижесінде 
формула дизъюнктивті қалыпты формаға түрлендіріледі.  
Мысалы, 
((x
y) (x
z))  формуласын  дизъюнктивті  қалыпты 
формаға  түрлендіру  керек  болсын. 
,    операцияларын    , ,       арқылы 
өрнектейміз.  
)
(
y
x
x
)
(
)
(
)
(
)
(
z
y
y
x
z
y
y
x
z
y
 
бойынша
за
вті
дистрибути
z
y
y
x
z
y
y
x
)
(
)
(
)
(
)
(
)
(
)
(
z
y
x
y
y
x
; 
Сонымен,      (( x y)   ( x z)) 
)
(
)
(
z
y
x
y
y
x
;   
2-Теорема. Кез келген А формуласы үшін оған эквивалентті және ҚҚФ 
болатын  В   формуласын табуға болады А В (дәлелдейміз) В  А- ның ҚҚФ. 
Кез келген формула өзінің ҚҚФ эквивалентті.  
Конюнктивті қалыпты формаға келтірудің алгаритмі алдыңғыға ұқсас, 
тек 3 пунктың орнына  
3
 қолданылады. 
3
. 
))
(
)
((
~
))
(
(
  дистрибутивті  заңды  пайдаланып, 
фор-муланы  барлық  дизъюнкциялар,  конъюнкцияларға  қарағанда  бұрын 
орын-далатындай түрлендіреміз.  
Мысалы. 
)
(
y
x
)
)
(
(
x
z
y
 формулада 
 болмайтындай түрлендір-
еміз:  
)
(
)
(
)
)
(
(
)
(
~
x
z
y
y
x
x
z
y
y
x
бойынша
зањ
дистр
x
z
y
y
x
.
)
)
((
)
(
 
)
)(
)(
(
z
x
y
x
y
x
-бұл формуланы одан 
әрі тағы түрлендіруге болады: 
)
(
)
)(
(
z
x
y
x
y
x
)
(
))
(
(
.
z
x
y
y
x
ќолданып
зањды
дистр
 

x
z
x
x
)
(
; 
x
-ті  ҚҚФ деуге де, ДҚФ деуге  де болады. Бұлардан басқа егер 
формуланың  ДҚФ  белгілі  болса  ҚҚФ-ке  ,  ҚҚФ  белгілі  болса  ДҚФ  көшудің 
алгоритмдері бар. Олар төмендегідей: 
ДҚФ-ті ҚҚФ-ке түрлендірудің  алгоритмі. 
Егер формуланың ДҚФ  белгілі болса ,оны  төмендегі ережемен ҚҚФ 
түрлендіруге болады. 
Айталық, ДҚФ   F=
m
к
к
к
...
2
1
      
1
m
   түрінде болсын. Мұндағы 
m
к
к
к
,
,
,
2
1

-элементар конъюнкциялар. 
1.    F-ке  қос  терістеу      F= 
m
к
к
к
...
2
1
    заңын  қолданып,  
m
к
к
к
...
2
1
-ті  ДҚФ  –ке 
'
'
'
1
2
m
к
к
к

  түрлендіру  керек.  Мұндағы 
'
'
'
1
,
,
,
2
m
к
к
к

- элементар конъюнкциялар.Сонда, 
F=
m
к
к
к
...
2
1
= 
m
к
к
к
...
2
1
  =
'
'
2
'
1
...
р
к
к
к
; 
Морган 
заңымен 
екінші 
терістеуден 
құтылып 
элементар 
конъюнкциялардың терістеулерін  элементар  дизъюнкцияларға 
р
D
D
D
,
,
,
2
1

 
түрлендіру керек. 
Сонда , F  =
'
'
2
'
1
...
р
к
к
к
=
'
'
2
'
1
...
р
к
к
к
=
.
,
,
2
1
р
D
D
D

 

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

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