3) tushuntirish qismi: bu yerda teoremada gap yuritilayotgan obyektlar to‘plamini ifodalash
Ravshanki, predikatlar mantiqi va mulohazalar algebrasidagi asosiy teng kuchliliklardan
)
(
)
(
)
(
)
(
))
(
)
(
(
z
R
y
Q
y
x
xP
z
R
y
yQ
x
xP
. ■
28.
Predikatlar mantiqi formulasining normal shakli.
Predikatlar mantiqining deyarli normal shakldagi
formulalari orasida
normal shakldagi
formulalar
muhim rol o‘ynaydi. Bu formulalarda kvantorli amallar yo butunlay qatnashmaydi, yoki
ular mulohazalar algebrasining hamma amallaridan keyin bajariladi, ya’ni normal shakldagi formula
quyidagi ko‘rinishda bo‘ladi:
)
,...,
,
(
)
(
.....
)
)(
(
2
1
2
1
m
n
x
x
x
A
x
x
x
,
m
n
,
bunda
)
(
i
x
simvoli o‘rnida
i
x
yoki
i
x
kvantorlardan biri yoziladi deb tushuniladi va
A
formula
ifodasida kvantorlar bo‘lmaydi.
1- t e o r e m a .
Predikatlar mantiqining har qanday formulasini normal shaklga keltirish
mumkin.
I s b o t i .
Formula deyarli normal shaklga
keltirilgan deb hisoblaymiz va uni normal shaklga
keltirish mumkinligini ko‘rsatamiz.
Agar bu formula elementar formula bo‘lsa, u holda uning ifodasida kvantorlar bo‘lmaydi va,
demak, u normal shakl ko‘rinishida bo‘ladi.
Endi faraz qilamizki, teorema ko‘pi bilan
k
amalni qamragan formula uchun to‘g‘ri bo‘lsin va
uni shu faraz asosida
1
k
amalni qamragan formula uchun isbot qilamiz.
A
formula
1
k
amalni o‘z ichiga olgan formula va uning ko‘rinishi
)
(
x
xL
shaklda bo‘lsin,
bu yerda
x
kvantorlarning birini ifodalaydi.
)
(
x
L
formula
k
amalni o‘z ichiga olganligi tufayli uni normal shaklga keltirilgan deb
hisoblaymiz. U holda
)
(
x
xL
formula ta’rifiga asosan normal shaklda bo‘ladi.
A
formula
L
ko‘rinishda bo‘lsin, bunda
L
formula normal shaklga keltirilgan va
k
amalni
o‘z ichiga olgan deb hisoblanadi. U holda
)
(
)
(
x
A
x
x
xA
va
)
(
)
(
x
A
x
x
xA
teng kuchliliklardan foydalanib, inkor amalini predikatlar ustiga tushiramiz. Natijada
A
formulani
normal shaklga keltirgan bo‘lamiz.
Endi
A
formula
2
1
L
L
ko‘rinishda bo‘lsin. Bu yerda
1
L
va
2
L
normal shaklga keltirilgan
formulalar deb qaraladi.
2
L
formulada bog‘langan predmet o‘zgaruvchilarni shunday qayta nomlaymizki,
1
L
va
2
L
formulalardagi hamma bog‘langan predmet o‘zgaruvchilar har xil bo‘lsin. U holda
1
L
va
2
L
formulalarni quyidagi ko‘rinishda yozish mumkin:
)
,...,
,
(
)
(
...
)
(
)
(
2
1
1
2
1
1
n
m
x
x
x
x
x
x
L
,
n
m
,
)
,...,
,
(
)
(
...
)
(
)
(
2
1
2
2
1
2
q
p
y
y
y
y
y
y
L
,
q
p
.
)]
(
[
)
(
x
B
C
x
x
xB
C
va
)
(
)
(
x
A
x
x
xA
teng kuchliliklardan foydalanib,
2
L
formulani
)
(
...,
,
)
(
),
(
2
1
m
x
x
x
kvantor amallari ostiga kiritamiz, ya’ni
A
formulani ushbu ko‘rinishga
keltiramiz:
)
,..,
,
(
(
)
(
...
)
(
)
(
2
1
1
2
1
n
m
x
x
x
x
x
x
A
))
,...,
,
(
)
(
...
)
(
)
(
2
1
2
2
1
q
p
y
y
y
y
y
y
.
So‘ngra
)
,...,
,
(
2
1
1
n
x
x
x
formulani
)
(
,...,
)
(
),
(
2
1
p
y
y
y
kvantor amallari ostiga kiritamiz. Natijada
A
formulaning normal shaklini hosil qilamiz:
)
(
...
)
(
)
(
)
(
...
)
(
)
(
2
1
2
1
p
m
y
y
y
x
x
x
A
))
,...,
,
(
)
,...,
,
(
(
2
1
2
2
1
1
q
n
y
y
y
x
x
x
.
2
1
L
L
ko‘rinishdagi
A
formulani normal shaklga keltirishning isboti xuddi yuqorida kabi
bajariladi. ■
Agar formulani normal shaklga keltirish jarayonida
)
(
)
(
x
xB
x
xA
yoki
)
(
)
(
x
xB
x
xA
ko‘rinishdagi ifodalarni ko‘rishga to‘g‘ri kelsa, u holda
)]
(
)
(
[
)
(
)
(
x
B
x
A
x
x
xB
x
xA
,
)]
(
)
(
[
)
(
)
(
x
B
x
A
x
x
xB
x
xA
teng kuchliliklardan foydalanish kerak bo‘ladi.
2- m i s o l .
)
,
(
)
,
(
y
x
yQ
x
y
x
yP
x
A
formulani normal shaklga keltirish talab etilsin.
A
formulada teng kuchli almashtirishlarni o‘tkazib, uni normal shaklga keltiramiz:
)
)
,
(
)
,
(
(
)
,
(
)
,
(
z
x
Q
z
y
x
yP
x
y
x
Q
y
x
y
x
yP
x
A
)
)
,
(
)
,
(
(
)
)
,
(
)
,
(
(
z
x
Q
y
x
P
z
y
x
z
x
Q
z
y
x
P
y
x
. ■
Do'stlaringiz bilan baham: 
