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

23 
функция қисап бола алады. Бұл мағынада барлық математикалық логиканың 
функциялары қисап бола алады. 
Үш және одан да көп логикалық функциялар ақиқаттық кестесімен, 
немесе айнымалылары және унарлы, бинарлы қисапты формулалармен 
беріледі. 
Жалпы 
жағдайда 
формула 
қарапайым 
функциялардың 
суперпозициясы ретінде логикалық функцияны сипаттайды.
Анықтама.
 
Егер 
1
1
1
1
( ,...,
)
( ( ,... ),...,
( ,...,
))
n
n
m
n
f x
x
g h x
x
h x
x

болса, онда 
)
,...,
(
1
n
x
x
f
функцисы
)
,...,
(
1
m
y
y
g
 
және
 
)
,...,
(
),...,
,...,
(
1
1
1
n
m
n
x
x
h
x
x
h
функцияларының 
суперпозицияы дейді. 
Мысалы 2.1.5
- 
3
2
1
3
2
1
)
,
,
(
y
y
y
y
y
y
g



және 
2
1
1
x
x
h

, 
3
2
2
x
x
h

,
1
4
3
x
x
h

функциялардың суперпозицияы 

1
4
3

2
2
1
4
3
2
1
)
,
,
,
(
x
x
x
x
x
x
x
x
x
x
f



.
 
 
 
 
2.2 Дәріс 5. Эквивалентті формулалар. Алгебра логикасының негізгі 
эквивалентті қарым-қатынастары 
Дәріс мазмұны: формулалардың эквиваленттілігі; негізгі эквивалентті 
заңдар мен ережелер; қосалқылық; Пост класы және базистер.
Дәріс мақсаты: формулалардың эквиваленттілігі және негізгі эквивалентті 
қарым-қатынастары, базис ұғымымен таныстыру. 
 
Бір функция әртүрлі формулалармен беріле алады. Бұл жағдайда 
формулалардың эквиваленттігі ұғымы пайда болады.

Анықтама.

 
Егер 
)
,...,
(
1
n
x
x

және 
)
,...,
(
1
n
x
x

формулалары бір ғана 
функцияны өрнектесе, онда олар эквивалентті делінеді (белгіленуі 


~
, 






,
). 
Мысалы 2.2.1
- 
y
x



және 
x
y



формулаларының ақиқаттық 
кестесін құрамыз. 
2.2.1 кесте 
Бұл формулалардың мәндерінің бағаны бірдей 
болғандықтан, олар эквивалентті
(
) ~ (
)
x
y
y
x


. 
Бұл мысалда формулаларының эквиваленттігін тексеру үшін ақиқаттық 
кестесін құрып, айнымалылар мәндерінің жиынтығын салыстыру әдісі 
қолданылды.
Формулаларының эквиваленттігін тексерудің басқа әдісі оларды 
эквивалентті түрлендірулер. Ол үшін эквивалентті қарым-қатынастар (заңдар) 
және ережелер. 
Түрлендірулерді келесі екі ережеге сүйеніп қолдану керек: 
x 
y 
y
x


0 
0 
1 
1 
1 
1 
0 
1 
0 
1 
1 
1 
1 
0 
1 
0 
0 
0 
1 
1 
0 
0 
1 
1 

24 
а) орнына қою ережесі: егер берілген эквивалентті қарым-қатынаста 
х 
айнымалысының 
барлық 
енулерін 
бірмезгілде 

формуласымен 
айырбастаймыз, сонда жаңа эквивалентті қарым-қатынас аламыз; 
б) айырбастау ережесі: егер 
f
функциясын сипаттайтын қандай да бір 

формуласы 

ішкі формуладан тұрса, онда 

-ді 
1

-мен айырбастағанда 
(
1



) 
f
функциясы өзгермейді. 
Негізгі эквивалентті қарым-қатынастарды атап өтейік.
2.2.2 кесте 
1 Коммутативтік 
x
y
y
x



x
y
y
x



2 Ассоциативтік 
)
(
)
(
z
y
x
z
y
x





)
(
)
(
z
y
x
z
y
x





3 Дистрибутивтік 
)
(
)
(
)
(
z
x
y
x
z
y
x






)
(
)
(
)
(
z
x
y
x
z
y
x






4 Идемпотенттік 
x
x
x


x
x
x


5 Сіңіру заңы 
x
y
x
x



)
(
x
y
x
x



)
(
6 де Моргана заңы 
y
x
y
x



y
x
y
x



7 Екі рет терістеу заңы
x
x

8 Константалар 
қасиеті 
0
0
,
1




x
x
x
x
x
x




0
,
1
1
9 
0


x
x
- қарама-қайшылық 
заңы 
1


x
x
- жойылған үшінші заңы 
Негізгі 
эквиваленттіліктермен 
қатар 
жиі 
қолданылатын 
эквиваленттіліктер. 
2.2.3 кесте 
10 
Жапсыру заңы 
x
y
x
y
x




)
(
)
(
x
y
x
y
x




)
(
)
(
10а Тарқату заңы 
(
)
(
)
x
x
y
x
y
   
)
(
)
(
y
x
y
x
x




11 
Жалпыланған жапсыру 
)
(
)
(
)
(
)
(
)
(
z
y
z
x
y
x
z
y
z
x









12 
y
x
y
x
x




)
(
12а 
y
x
y
x
x




)
(
13 
y
x
y
x
x




)
(
13а 
y
x
y
x
x




)
(
14 
(
)
(
)
x
y
x
y
y
x
 



)
(
)
(
)
(
)
(
y
x
y
x
x
y
y
x
y
x









15 
y
x
y
x



)
(
16 
|
x y
x
y
 
17 
x
y
x
y
  
18 
(
)
(
)
x
y
x
y
x
y
y
x
   



Анықтама.
 
Егер 
)
,...,
(
1
n
x
x

формуласының 1 (0) мәнін қабылдайтындай 
айнымалылардың мәндерінің жиынтығы бар болса, онда формула орындалатын 
(жоққа шығарылатын) делінеді.
Мысалы 2.2.2
-

=
y
x

формуласы бірмезгілде орындалатын және жоққа 
шығарылатын болады, себебі (
)
1
1
1


және 
)
0
0
0
(


. 

25 

Анықтама.

 
Егер 
)
,...,
(
1
n
x
x

формуласы барлық айнымалыларының 
жиынтығында 1 (сәйкес 0) мәнін қабылдаса (яғни функция 1 (0) константа 
болса), онда формула тепе-тең ақиқат, жалпымәнді немесе тавтология (тепе-тең 
жалған немесе қарама-қайшылық) делінеді. 
Мысалы 2.2.3
-
x
x

- формуласы тепе-тең ақиқат, себебі 
x
x

=1 кез 
келген
х 
үшін; 
x
x

- формуласы тепе-тең жалған , себебі 
x
x

=0 кез келген
х 
үшін:
2.2.4 кесте 
х
x
x
x

x
x

0 
1 
1 
0 
1 
0 
1 
0 
Айта кетелік, формула қандай да бір логикалық тұжырым немесе 
пайымдауды білдіреді. Егер тұжырымды сипаттаушы формула тепе-тең ақиқат 
болса, онда бұл пайымдау логикалық дұрыс болады. 


Қосалқылық. 

Анықтама.

 
Егер
)
,...,
(
)
,...,
(
1
1
n
n
x
x
f
x
x
f


орындалса, онда 
)
,...,
(
1
n
x
x
f

функциясы 
)
,...,
(
1
n
x
x
f
функциясына қосалқы делінеді. Өзіне өзі қосалқы
функция, яғни 
f
f


, өзқосалқы делінеді. 
Егер 
g
f


, онда 
f
g


, яғни қосалқылық қатынасы симметриялы. 
Мысалы 2.2.4
- Дизъюнкция конъюнкцияға, конъюнкция – дизъюнкцияға, 
1 константасы – 0 константасына, 0 константасы – 1 константасына қосалқы. 
Теріске шығару өзқосалқы. Расында, мысалы, 
f
=
y
x

үшін 
y
x
y
x
y
x
f







;
f
x
f
x
x



 
, яғни 
f
f


. 
Қосалқы функцияны ақиқат кестесі көмегімен алуға болады. Ол үшін 
f
функцияның ақиқат кестесінде барлық мәндерді қарама-қарсыға айырбастау 
керек.
Мысалы 2.2.5
- 
( , , )
f x y z
xy
xz
yz



функциясы үшін қосалқы функцияны 
екі әдіспен аламыз: 
I әдіс. 
)
(
)
(
)
(
z
y
z
x
y
x
z
y
z
x
y
x
f










yz
xz
xy



, яғни 
f
f


. 
II әдіс. 
f
үшін ақиқат кестесін құрамыз (кесте 2.2.5). Содан соң ондағы 
мәндерді қарама-қарсыға айырбастап

f
үшін кесте аламыз (кесте 2.2.6). 
Кестеден функцияның өзқосалқылығы көрінеді 
f
f


. Айта кетелік, 

f
функцияның кәдімгі кестесін алу үшін, соңғы кестедегі барлық бағандарды 
«төңкеру керек», мұндағы айнымалылардың мәні лексикографиктік ретте 
жазылған.

26 
2.2.5 кесте 2.2.6 кесте 
Қосалқылық принципі:
 
егер
f
функциясын сипаттайтын
F
формуласында функцияның барлық таңбаларын қосалқы функцияның 
таңбасына ауыстырсақ, онда алынған 

F
формула 

f
функциясын сипаттайды,

f
функциясы
 
f
функциясына қосалқы. Буль алгебрасында қосалқылық 
принципі нақтырақ: Егер 
f
функциясын сипаттайтын
F
формуласында, 
барлық конъюнкцияны дизъюнкцияға, дизъюнкциияны конъюнкцияға, 1-ді 0-
ге, 0-ді 1-ге айырбастасақ, онда қосалқы 

f
функциясын сипаттайтын 

F
формуласын аламыз.

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

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