DiM 2203 дискретті математика

Анықтама 1. x
1
, x
2
, …, x
n
 – пәндік айнымалылардың символдары болсын. 
Пәндік айнымалылардың (x
1
, x
2
, …, x
n
) топтары пәндік аймақ деп аталатын   
жиыныны  тиісті  болсын. 
  пәндік  аймағында  анықталған  n-орынды 
предикат деп,   -ның тұжырымдар жиынына бейнелеуін айтады.  
Мысалдарды  қарастырар  алдын  n-орынды  предикаттарға  квазианықтама 
берейік: 
Анықтама.  «n    айнымалыға  тәуелді  және  келесі  қасиетке  ие  болған 
баяндамалы  байланысты  сөйлемі:  айнымалылардың  орнына  анық  мәндер 
қойылғанда ақиқат немесе жалған болсын». 
Мысал  1.  D(x
1
,  x
2
)  =  «x
1
  натурал  саны  x
2 
натурал  санына  бөлінеді 
(қалдықсыз)»  -  N N  жиынында  анықталған  екі  орынды  предикат.  Түсінікті, 
D(4, 2)=1, D(3, 5)=0. 
Мысал 2. Q(x) = «х
2
<-1, x R» - R нақты сандар жиынында анықталған бір 
орынды  предикат.  Q(-1)=0,  Q(
3
)=0.  Q(x)  –  тепе-тең  жалған  екендігі 
түсінікті, яғни Q(x)  0. 
Мысал  3.  R(x, y, z)= «x
2
+  y
2
z;  x,  y,  z R»  -  R
3 
жиынында анықталған үш 
орынды предикат. R(1, 1, -2)=0, R(1, 1, 2)=1. 
Мысал  4.  S(x,  y)  =  «sin2ху>-3;  x,  y R»  -  екі  орынды  тепе-тең  ақиқат 
предикат. 
Р(x
1
,  x
2
,  …,  x
n
)  - 
  аймағында  анықталған  n-орынды  предикат  болсын. 
Онымен келесі түрде анықталған екі жиынды байланыстырамыз:  
I
P
={(  x
1
,  x
2
,  …,  x
n 
)  
  |  Р(x
1
,  x
2
,  …,  x
n
)=1}  –  Р  предикаттың  ақиқаттық 
жиыны, 
L
P
={(  x
1
,  x
2
,  …,  x
n)
 
 
|  Р(x
1
,  x
2
,  …,  x
n
)=0}  –  Р  предикаттың  жалғандық 
жиыны. 
Анықтама  2.  Р  –  -да  анықталған  предикат  болсын.  Егер  I
P
=   (L
P
= ) 
болса,  онда  Р  тепе-тең  ақиқат,  егер  L
P
=   (I
P
= )  болса,  онда  Р  тепе-тең 
жалған предикат деп аталады.  
Егер  I
P 
 
  және  L
P 
 
    болса,  онда  Р  орындалатын  предикат  деп 
айтамыз. 
R
3 
кеңістікте  3  мысалдағы            R(x,  y,  z)  предикаттың    I
P   
және  L
P
 
жиындарын көрсетейік (1 сурет).                                                           
                                                                 z                        I
P
 
 
 
 
1 сурет 
                               
                                                                                        у 
                                             х                                                                      
9.1. Предикаттарға логикалық амалдарды қолдану 
 

Анықтама  3.  Р  –  -да  анықталған  предикат  болсын.  Р  предикаттың 
терістеуі дегеніміз 
Р
Р
  белгіленетін  және  -да  келесі  түрде  анықталған 
предикат: 
 
n
def
n
x
x
x
P
x
x
x
;
;
;
;
;
;
Р
2
1
2
1


 
P және Q –  -да анықталған предикаттар болсын. 
P және Q предикаттардың дизъюнкциясы (конъюнкциясы, импликациясы, 
эквиваленциясы)  дегеніміз  былай  белгіленетін 
Q
P
,  (
Q
P
  (
Q
P
,
Q
P &
, 
PQ), 
Q
P
, 
Q
P ~
) және 
-да келесі түрде анықталатын предикат: 
n
n
def
n
x
x
Q
x
x
P
x
x
Q
P
,
,
,
,
,
,
1
1
1



 
(
n
n
def
n
x
x
Q
x
x
P
x
x
Q
P
,
,
,
,
,
,
1
1
1



) 
(
n
n
def
n
x
x
Q
x
x
P
x
x
Q
P
,
,
,
,
,
,
1
1
1



) 
(
n
n
def
n
x
x
Q
x
x
P
x
x
Q
P
,
,
~
,
,
,
,
~
1
1
1



) 
 
Анықтама  4.  Егер 
  аймағына  тиісті  кез  келген  (  x
1
,  x
2
,  …,  x
n 
)  пәндік 
айнымалылардың топтары үшін Р( x
1
, x
2
, …, x
n 
)   Q( x
1
, x
2
, …, x
n 
) болса, онда 
P және Q предикаттар 
 аймағында анықталған пара-пар предикаттар деп 
аталады (P Q). 
 
Теорема 1.   аймағында анықталған n – орынды предикаттардың жиыны 
предикаттардың  бульдік  алгебрасық  құрайды,  яғни  олар  үшін  бульдік 
алгебраның келесі 19 негізгі тепе-теңдіктер орынды: 
 
0. 
Р
Р
 
1. 
P
Q
Q
P
 
2. 
P
Q
Q
P
 
3. 
R
Q
P
R
Q
P
 
4. 
R
Q
P
R
Q
P
 
5. 
R
P
Q
P
R
Q
P
 
6. 
R
P
Q
P
R
Q
P
 
7. 
Q
P
Q
P
 
8. 
Q
P
Q
P
 
9. 
Р
Р
Р
 
 
10. 
Р
Р
Р
 
11. 
1
1
Р
 
12. 
0
0
Р
 
13. 
Р
Р 0
 
14. 
Р
Р 1
 
15. 
P
Q
P
P
 
16. 
P
Q
P
P
 
17. 
1
P
P
 
18. 
0
P
P
 
 
Мұнда  1  –  -дағы  тепе-тең  ақиқат  предикаттың,  ал  0  –  тепе-тең  жалған 
предикаттың белгілері.  
Бұл теореманың дұрыстығы айқын. Өйткені предикаттарға қолданылатын 
амалдар  тұжырымдарға  қолданылатын  амалдар  көмегімен  енгізілген,  ал 
тұжырымдар бульдік алгебраны құрайды.  

9.2. Кванторлық амалдар 
 
Предикаттарды тұжырымдарға түрлендіретін амалдарды қарастырайық. М 
жиынында  анықталған  Р(х)  предикат  берілсін.  Егер  “а”  –  М  жиынының 
қандай  да  бір  элементі  болса,  онда  Р(х)  предикатта  х  орнына  а  ны  қою 
берілген    предикатты  Р(а)  тұжырымға  айналдырады.  Мұндай  предикатты 
бірлік деп атайды. Мысалы, Р(x): “х – жұп сан” – предикат, ал Р(6) – ақиқат 
тұжырым, Р(3) – жалған тұжырым. 
Жоғарыда айтылғанды n – орынды предикаттарға жалпылау мүмкін: егер 
барлық х
i
, i=
n
,
1
, пәндік айнымалылардың орнына олардың мәндері қойылса, 
онда тұжырым алынады.  
Квантификация  амалдарын  қарастырамыз.  Бұл  амалдардар  да 
предикаттарды тұжырымдарға айналдырады.  
 
Жалпылау кванторы 
 
Р(х)  – 
  жиынында  анықталған  предикат  болсын.  Бұл  предикатқа 
предикат тепе-тең ақиқат болғанда ғана ақиқат болатын 
)
(x
xP
 тұжырымын 
сәйкестікке қоямыз. 
)
(x
xP
 тұжырымы былай оқылады:  “Кез келген х үшін 
Р(х)  ақиқат  ”. 
)
(x
xP
  тұжырымы  Р(х)  предикатқа  х  айнымалы  бойынша 
жалпылау кванторын ілу көмегімен алынған деп айтады.  
  символын  жалпылау  кванторы  деп  атайды.  Р(х)  предикатқа  х 
айнымалы  бос  болып,  ал 
)
(x
xP
  тұжырымға  –  х  жалпылау  кванторымен 
байланған болып енеді деп айтады.  
 
Бар болу кванторы 
 
P(x)  –   
  жиынында  анықталған  предикат  болсын.  Бұл  предикатқа 
предикат тепе-тең жалған болғанда ғана жалған болатын 
)
(x
xP
 тұжырымын 
сәйкестікке  қоямыз. 
)
(x
xP
  тұжырымы  былай  оқылады:“  P(x)  ақиқат 
болатын  х  табылады”. 
  символын  бар  болу  (табылу)  кванторы  деп 
аиаймыз. 
)
(x
xP
 тұжырымы Р(х) предикатқа х айнымалы бойынша бар болу 
кванторын  ілу  көмегімен  алынған  деп  айтады.  х  айнымалы  бұл  квантормен 
байланған болады.  
Кванторлық  амалдарды  көп орынды  предикаттарға да  қолдануға  болады. 
Мысалы,    жиынында  екі  орынды  P(x,y)  предикаты  берілсін.  Предикаттың 
айнымалыларына кванторларды іліп, мынадай тұжырымдарды алуға болады: 
)
,
(
),
,
(
),
,
(
),
,
(
 
),
,
(
 
),
,
(
 
),
,
(
  
),
,
(
y
x
xP
y
y
x
уP
х
y
x
xP
y
y
x
уP
х
y
x
xP
y
y
x
уP
x
y
x
хP
у
y
x
уP
х
 
 
9.3.  Предикаттар логикасының формуласының ұғымы 
 

Предикаттар логикасында келесі символдарды пайдаланамыз: 
1.  p,  q,  r,  …  символдары  –    1–  ақиқат  немесе  0  –  жалған  екі 
мәнді қабылдайтын айнымалы тұжырымдар; 
2.   x,  y,  z,  …  –  кейбір  М  жиынына  тиісті  мәндерді 
қабылдайтын пәндік айнымалылар;  
x
0
, y
0
, z
0
 – пәндік тұрақтылар, яғни пәндік айнымалылардың мәндері. 
3.  P(·), Q(·), F(·), … - бір орынды предикаттық айнымалылар; 
Q(·,·,…,·), R(·,·, …,·) – n-орынды предикаттық айнымалыла;р 
P
0
(·), Q
0
(·,·, …,·) – тұрақты предикаттардың символдары. 
4.  Логикалық амалдардың символдары: 
.
,
,
,
     
5.  Кванторлық амалдардың символдары: 
.
, x
x
 
6.  Көмекші  символдар: жақшалар, үтірлер. 
 
 
10-дәріс.  Предикаттар  логикасының  формулалары.  Пренексті 
қалыпты формалар. 
1.  Кез келген тұжырым (қарапайым) формула болады.  
2.  Егер F(·,·, …,·) – n-орынды предикатты айнымалы немесе тұрақты 
предикат,  ал  x
1
,  x
2
,…,  x
n 
–  пәндік  айнымалылар  немесе  пәндік 
тұрақтылар  болса,  онда  F(x
1
,  x
2
,…,  x
n
)  –    формула.  Мұндай  формула 
қарапайым  деп  аталады,  бұл    формулада  пәндік  айнымалылар  бос, 
кванторлармен байланбаған болады.  
3.  Егер  А  және  В  –  формулалар  (бұл  формулаларға  айнымалылар 
бір түрде кіреді – бос немесе байланған), онда 
B
A
B
A
B
A
,
,
 сөздер 
–  формулалар.  
4.  Егер А – формула болса, онда 
A
 да – формула, А формуладан 
A
 
формулаға өтуде пәндік айнымалылардың ену түрі өзгермейді.  
5.  Егер  А(х)  –  формула  (бұл  формулаға  х  пәндік  айнымалы  бос 
болып енеді), онда 
)
(x
xA
 және 
)
(x
xA
 сөздер де формулалар.  
6.  1  –  5  бөлімдерде  айтылған  сөздерден  басқа  сөздер  формула 
болмайды.  
Мысалы, егер Р(х) және Q(x,y) – бір орынды және екі орынды 
предикаттар, ал q, r – айнымалы тұжырымдар болса, онда келесі сөздер 
(өрнектер) формулалар болады: 
r
q
y
x
Q
y
x
xQ
x
xP
y
x
Q
x
P
x
P
q
)
)
,
(
(
),
,
(
)
(
),
,
(
)
(
),
(
,
0
. 
Мысалы, 
)
(
)
,
(
x
P
y
x
xQ
  сөзі  формула  емес.  Мұнда  үшінші  бөлімнің 
шарты бұзылған: 
)
,
(
y
x
xQ
 формулаға х айнымалы байланған болып, ал  Р(х) 
формулаға бос болып енеді.  
Предикаттар 
логикасы 
формуласы 
анықтамасынан 
тұжырымдар 
алгебрасының  әрбір  формуласы  предикаттар  логикасының  формуласы 
болатыны түсінікті.  
 
Предикаттар логикасының формуласының мәні 

 
Формуланың 
логикалық 
мәні 
жайлы 
бұл 
формулаға 
кіретін 
предикаттардың  М  анықталу  аймағы  берілгенде  ғана  айтуға  болады. 
Формуланың  логикалық  мәні үш  түрлі  айнымалылардың мәндеріне  тәуелді: 
1)  формулаға  енетін  айнымалы  тұжырымдардың  мәндеріне,  2)  М  жиынына 
тиісті 
бос 
пәндік 
айнымалылардың 
мәндеріне, 
3) 
предикатты 
айнымалылардың мәндеріне.  
Осы  үш  түрлі  айнымалылардың  анық  мәндерінде  предикаттар 
логикасының формуласы  ақиқат немесе  жалған  мән қабылдайтын  тұжырым 
болады.  
Мысал ретінде келесі формуланы қарастырамыз:  
))
,
(
)
,
(
(
z
y
P
y
x
P
z
y
,                                                (1) 
Бұл формулада екі орынды Р(x, y) предикаты M M  жиынында анықталған, 
мұнда  M={0,1,2,…,n,…}, яғни M M=N N. 
В  формулу  (1)  формулаға  кіретін  P(x,y)  айнымалы  предикаттың үш  x,y,z  
пәндік  айнымалыларынан  екеуі  –  у  және  z  кванторлармен  байланған,  ал 
үшіншісі х – бос.  
P(x,y) предикаттың мәнін бекітеміз: P
0
(x,y)= «xмәні 
M
x
5
0
  болсын.  Онда  у-тің  x
0
=5  мәнінен  кіші  мәндерінде  P
0
(x
0
,y)  
предикаты  “жалған”  мәнін,  ал  импликация 
)
,
(
)
,
(
z
y
P
y
x
P
  барлық 
M
z
 
үшін “ақиқат” мәнін қабылдайды, яғни 
))
,
(
)
,
(
(
0
0
z
y
P
y
x
P
z
y
 тұжырымы 
ақиқат.  
10.1. Предикаттар логикасының формулаларының тепе-теңдігі 
 
Анықтама  1.  Егер  предикаттар  логикасының  А  және  В  формулалары  М 
аймаққа тиісті айнымалыларының барлық мәндерінде бірдей логикалық мән 
қабылдаса, онда бұл формулалар М аймақта тепе-тең деп айтады. 
Анықтама 2. Егер предикаттар логикасының А және В формулалары кез 
келген аймақта тепе-тең болса, онда бұл формулалар тепе-тең деп аталады. 
Түсінікті,  егер  тұжырымдар  алгебрасының  тепе-теңдіктеріне  айнымалы 
тұжырымдардың  орындарына  предикаттар  логикасының  формулалары 
қойылса, олар дұрыс болады. Бірақ, олардан басқа, предикаттар логикасының 
өзінің тепе-теңдіктері орынды болады. Олардың негізгілерін қарастырайық.  
А(х)  және  В(х)  –  айнымалы  предикаттар,  ал  С  –  айнымалы  тұжырым 
болсын  (немесе  х  ке  тәуелді  емес  формула).  Онда  келесі  тепе-теңдіктер 
орынды:  
1. 
).
(
)
(
x
A
x
x
xA
              
2. 
).
(
)
(
x
A
x
x
xA
 
3. 
).
(
)
(
x
A
x
x
xA
 
4. 
).
(
)
(
x
A
x
x
xA
 
5. 
)]
(
)
(
[
)
(
)
(
x
B
x
A
x
x
xB
x
xA
 

6. 
)]
(
[
)
(
x
B
C
x
x
xB
C
. 
7. 
)]
(
[
)
(
x
B
C
x
x
xB
C
 
8. 
)]
(
[
)
(
x
B
C
x
x
xB
C
 
9. 
.
)
(
]
)
(
[
C
x
xB
C
x
B
x
 
10. 
).
(
)
(
)]
(
)
(
[
x
xB
x
xA
x
B
x
A
x
 
11. 
).
(
)]
(
[
x
xB
C
x
B
C
x
 
     12. 
).
(
)]
(
[
x
xB
C
x
B
C
x
 
13. 
)].
(
)
(
[
)
(
)
(
y
B
x
A
y
x
y
yB
x
xA
 
14. 
).
(
)]
(
[
x
xB
C
x
B
C
x
 
15. 
.
)
(
]
)
(
[
C
x
xB
C
x
B
x
 
 
10.2.  Пренекстік нормал форма 
 
Анықтама.  Егер  предикаттар  логикасының  формуласы  терістеу, 
конъюнкция, дизъюнкция және кванторлық операциялар көмегімен құрылған 
болса  және  терістеу  амалы    тек  қарапайым  формулаларға  қатысты  болса, 
онда бұл формула нормал формаға ие деп айтады.  
Тұжырымдар  алгебрасының  және  предикаттар  логикасының  тепе-
теңдіктерін  пайдаланып,  предикаттар  логикасының  кез  келген  формуласын 
нормал формаға келтіру мүмкін.  
Мысал 1. 
)
(
))
(
)
(
(
z
R
y
yQ
x
xP
 
формуланы нормал формаға келтірейік.  
Тепе-тең түрлендірулерді пайдаланып, келесіні аламыз:  
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
))
(
)
(
(
z
R
y
Q
y
x
xP
z
R
y
yQ
x
xP
z
R
y
yQ
x
xP
z
R
y
yQ
x
xP
. 
Предикаттар 
логикасы 
формулаларының 
арасында 
пренекстік 
(префикстік)  нормал  форма  деп  аталатын  формулаларды  бөліктейді.  Бұл 
формада  кванторлық  амалдар  жоқ  болады  немесе  олар  логика  алгебрасы 
барлық  амалдарынан  кейін  қолданылады,  яғни  предикаттар  логикасы 
формуласының ПНФ келесі түрде болады:  
m
n
x
x
x
A
х
х
х
m
n
),
,...,
,
(
)
)...(
)(
(
2
1
2
1
, 
мұнда 
i
х  символы –
i
x
 немесе 
i
x
, ал А формуласында кванторлар жоқ.  
Теорема.  Предикаттар  логикасының  кез  келген  формуласын  пренекстік 
нормал формаға келтіру мүмкін.  
 
 

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

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