|
. Predikatlar algebrasi uchun yechilish muammosining umumiy
holda ijobiy hal qilinmaslig
XX asrning 40 – yillarida algoritm tushunchasiga aniq ta’rif berilganidan so`ng echilish muammosini hal qilish imkoni hosil bo‘ld 1936 yilda amerikalik matematik A.CHyorch predikatlar algebrasi uchun echilish muammosi umumiy holda ijobiy hal qilinmasligini isbot qilgan.
Echilish muammosi chekli sohalar uchun ijobiy hal qilinishi ravshan. Ha=iqatdan, agar ℑ (x1, . . . , xn) formula ℳ to`plamning elementlarini x1, . . . , xn o‘zgaruvchi predmetlar o`rniga qo‘yib chiqib, ℑ formulaning qiymatlarini tekshirib chiqamiz. Bu jarayon chekli qadamda yakunlanad Kvantor amallarini esa kon’yunksiya, diz’yunksiya amallari bilan almashtirish mumkin.
6.1 - misol. "x $u ( R ( x, u, z ) Ú Q ( x )) formula
ℳ = { a, b } to`plamda bajariluvchi bo‘lish bo‘lmasligini aniqash uchun avval formula ko‘rinishini asosiy tengkuchliliklar yordamida o‘zgartiramiz :"x $u ( R ( x, u, z ) Ú Q ( x )) º "x ( P ( x, a, z ) Ú Q ( x ) Ú
Ú R ( x, b, z )) º ( P ( a, a, z ) Ú Q ( a ) Ú P ( a, b, z )) Ù
Ú ( P ( b, a, z ) Ú Q ( b ) Ú P ( b, b, z )).
Hosil bo‘lgan formulada z o`rniga a va b qiymatlarni ketma-ket qo‘yib berilgan formulaning bajariluvchi bo‘lish- bo‘lmasligini aniqash mumkin.
6.2 - ta’rif. Agar predikatlar algebrasining formulasida erkli o‘zgaruvchilar qatnashmasa, bunday formula yopiq formula deyilad
6.3 - misol. "x "u $z ( P ( x, y ) Ú R ( x, z )) – formula yopi= formuladir.
6.4 - ta’rif. Agar predikatlar algebrasining
ℑ ( x1, . . . , xn ) formulasida x1, . . . ,xn – erkli predmet o‘zgaruvchilar qatnashgan bo‘lsa, u holda
" x1 " x2. . . " xn ℑ ( x1, . . . ,xn ) – formula ℑ ( x1, . . . ,xn )
formulaning umumiylik (kvantori orqali) yopi\i,
$ x1 $ x2 . . .$ xn ℑ ( x1, . . . ,xn ) esa berilgan formulaning mavjudlik (kvantori orqali) yopi\i, ikkala $ ," kvantorlar yordamida hosil qilingan yopiq formula - berilgan formulaning aralash yopig‘i deyilad
6.5 - misol. $x R ( x, u, z ) formula berilgan bo‘lsin. U holda "u "z $x R ( x, u, z ) berilgan formulaning umumiylik yopi\i, $u $z $x R ( x, u, z ) – mavjudlik yopi\i,
"u $z $x R ( x, u, z ) – aralash yopig‘i bo‘lad
6.6 – teorema. Predikatlar algebrasining yopiq, normal formasida faqat n ta mavjudlik kvantori qatnashib, umumiylik kvantorlari qatnashmagan bo‘lsin. Agar bu formula ixtiyoriy bir elementli to`plamda rost qiymat qabul qilsa, u holda u umumqiymatli formuladir.
Isbot. Teorema shartiga asosan olingan formula quyidagi ko‘rinishda bo‘lsin :
ℬ = $x1. . . $xn ℑ ( U1, . . . ,Up ; P1, . . . , Pq ; . . .
Q1, . . . , Qt ) ( 1 ).
ℬ formulada Y1,Y2, . . . , Yp – o‘zgaruvchi mulohazalar ;
P1,P2, . . . , Pq – bir o‘rinli predikatlar simvollari va h.k.
Q1, Q2, . . . , Qt - m – o‘rinli predikatlar simvollari;
ℑ - teorema shartiga ko`ra kvantorsiz formuladir.
Teorema shartiga ko`ra ℬ formula ixtiyoriy bir elementli ℳ = { a } to`plamda aynan rost. YA’ni
ℑ ( U1, . . . ,Ur ; R1( a ) , . . . , Rq ( a ) ; Q1( a, . . . , a ), . . .
Qt( a, . . . , a ) ) = 1.
Faraz qilaylik ( 1 ) formula umumqiymatli formula bo‘lmasin. U holda shunday ℳ1 soha, U10, . . . , Ur0 – mulohazalar,
R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 - ℳ1 sohada aniqangan
predikatlar mavjud bo‘lib, ( 1 ) formula « yolg‘on»
qiymat qabul qilsin. YA’ni :
$x1. . . $xn ( ℑ ( U10, . . . , Ur0; R10, . . . , Rq0; . . .
Q10 , . . . , Qt0 )) = 0 ( 3 ).
U holda ù ( $x1. . . $xn ( ℑ ( U10, . . . , Ur0; R10, . . . , Rq0; . . . ;
Q10, . . . , Qt0 ))) = "x1. . . "xn ( ù ( ℑ ( U10, . . . , Ur0;
R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ))) = 1 .
Demak, ù ( ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ;
Q10, . . . , Qt0 )) – formula o‘zgaruvchi predikatlarning ℳ1
to‘plamdagi barcha qiymatuchun aynan rost bo‘lad
Xususan, ixtiyoriy ℳ1 = { x0 } – bir elementli to`plam uchun
ℑ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ) = 0 .
Bu esa teorema shartiga zid.
6.7 – teorema. Predikatlar algebrasining yopiq, keltirilgan normal formulasida faqat n ta umumiylik kvantori qatnashib, mavjudlik kvantorlari qatnashmasin. Agar bu formula elementlari soni n tadan ko‘p bo‘lmagan har qanday to`plamda aynan rost formula bo‘lsa, u holda u umumqiymatli formuladir.
Isbot. Teorema shartini qanoatlantiradigan
ℬ = "x1 . . . "xn ( ℑ ( U1, . . . , Ur ; R1, . . . , Rq ; . . . ;
Q1, . . . , Qt )) ( 1 )
formula berilgan bo‘lsin. Bu erda :
U1, . . . , Ur - o‘zgaruvchi mulohazalar ;
R1, . . . , Rq – bir o‘rinli predikatlar ; . . . va h.k.
Q1, . . . , Qt – m – o‘rinli predikatlardir.
ℬ formula umumqiymatli emas deb faraz qilaylik.
U holda:
shunday elementlari soni n dan ko‘p bo‘lgan ℳ to`plam ; U10, . . . ,Ur0 – mulohazalar ;
ℳ to`plamda aniqangan R10, . . . , Rq0 - bir o‘rinli predikatlar ; . . .
Q10, . . . , Qt0 – m o‘rinli predikatlar mavjud bo‘lib ,
"x1 . . . "xn ( ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ;
Q10, . . . , Qt0 )) ( 2 )
formula yolg‘on qiymat qabul qilad U holda
$x1 . . . $xn ( ù ( ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ;
Q10, . . . , Qt0 ))) = 1.
Bundan esa ù ( ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ;
Q10, . . . , Qt0 )) = 1
yoki ℑ ( U10, . . . , Ur0 ; R10, . . . , Rq0 ; . . . ; Q10, . . . , Qt0 ) = 0
ekanligi kelib chiqad Demak, ℳ to‘plamning elementlari soni n tadan ko`p bo‘lmagan ℳ1 qism to`plami mavjud bo‘lib, ℳ1 to`plamda ( 1 ) formula « yolg‘on » qiymat qabul qilad Hosil bo‘lgan natija teorema shartiga zid.
Predikatlar algebrasi uchun echilish muammosi bilan chuqurroq tanishmoqchi bo‘lgan qo‘uvchilarga P.S.Novikovning
« Elemento` matematicheskoy logiki » kitobini tavsiya etamiz.
Do'stlaringiz bilan baham: |
