|
92.MAVZU. PREDIKATLAR HISOBHOSILAVIY KELTIRIB CHIQARISH QOIDALAR BA`ZI TAVTOLOGIYALAR ISBOT PREDIKATLAR HISOBINING ZIDSIZLIGI VA TO’LALIG MATEMATIK NAZARIYALAR. FORMAL ARIFMETIKA.
Predikatlar hisobining formulalari, aksiomalari
Predikatlar hisobining aksiomalari sifatida mulohazalar hisobining barcha aksiomalarini undan tashqari
quyidagi aksiomalarni qabul qilamiz :
V1. "x F ( x ) Þ F ( y );
V2. F ( y ) Þ $x F ( x ).
SHunday qilib, predikatlar hisobining aksiomalari quyidagilardan iborat :
I1. A Þ ( B Þ A ) .
2. ( A Þ ( B Þ C )) Þ (( A Þ B ) Þ ( A Þ C )).
1. A Ù B Þ A .
2. A Ù B Þ B .
3. ( A Þ B ) Þ (( A Þ C ) Þ ( A Þ B Ù C )) .
I1. A Þ A Ú B .
2. B Þ A Ú B .
I3. ( A Þ C ) Þ (( B Þ C ) Þ ( A Ú B ) Þ C )) .
IV1. ( A Þ B ) Þ ( ù B Þ ù A ) .
IV2. A Þ ù ù A .
IV3. ù ù A Þ A .
V1. "x F ( x ) Þ F ( y ) .
V2. F ( y ) Þ $x F ( x ) .
Predikatlar hisobining keltirib chiqarish qoidalari
2.1. Xulosa chiqarish qoidasi .
Agar ℑ , ℑ Þ ℬ formulalar keltirib chiqariluvchi formulalar bo‘lsa, u holda ℬ ham keltirib chiqariluvchi formuladir. Bu qoida mulohazalar hisobidagidek
ℑ , ℑ Þ ℬ
ℬ
ko‘rinishda belgilanad ( BU KASR BELGISI EMAS )
2.2. O‘zgaruvi mulohazani o‘rniga qo‘o`yish qoidasi .
Predikatlar hisobining keltirib chiqariluvchi ℑ ( A ) formulasida A o‘zgaruvchi mulohaza qatnashsin.
ℬ – predikatlar hisobining ixtiyoriy formulasi bo‘lib, ℬ ning erkin o‘zgaruvchilari ℑ dagi bog‘li= o‘zgaruvchilardan farqli harflar bilan ; ℬ ning bog‘liq o‘zgaruvchilari ℑ ning erkin o‘zgaruvchilaridan farqli harflari bilan belgilangan bo‘lsin. Undan tashqari A mulohaza birorta kvantorning ta’sir doirasida yotgan bo‘lsa, bu kvantorlar bilan bog‘langan harf ℬ formulada qatnashmasin. Bu holda A o‘zgaruvchi mulohaza ℑ formulaning =aerida qatnashgan bo‘lsa, o`sha joylarda A mulohazani ℬ formula bilan almashtirsak, hosil bo‘lgan ifoda predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad Bu qoida qisqacha
ℑ ( A )
ℑ ( ℬ ) ko‘rinishda belgilanad
2.4. O‘zgaruvchi predikatni o‘rniga qo‘yish qoidasi .
Bu almashtirish natijasida ham hosil bo‘lgan ifoda formula bo‘lishini ta’minlashimiz lozim.
Predikatlar hisobining keltirib chiqariluvchi ℑ ( F ) formulasida n o‘zgaruvchili F predikat qatnashsin.
ℬ ( t1, . . , tn ) – predikatlar hisobining n ta erkin t1 . . , tn o‘zgaruvchili formulasi bo‘lsin. ℬ ning bog‘li= o‘zgaruvchilari ℑ ning erkin o‘zgaruvchilaridan, ℬ ning erkin o‘zgaruvchilari ℑning bog‘li= o‘zgaruvchilaridan farqli harflar bilan belgilangan bo‘lsin. Undan tashqari agar F ℑ dagi birorta harfni bog‘lagan kvantorning ta’sir sohasida bo‘lsa, o‘sha harf ℬ formulada qatnashmasin. U holda agar ℑ ( F ) formulada barcha F ( x1, . . . , xn ) qatnashgan joylarda
ℬ ( t1, . . . , tn ) formulaning t1 . . , tn o‘zgaruvchilarini mos ravishda x1, . . . , xn larga almashtirib qo‘yib chiqamiz.
Natijada hosil bo‘lgan ifoda predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad
YUQoridagi shartlarning buzilishini o‘zgaruvchilarning kolliziyasi deyilad
Erkin o‘zgaruvchi predmetlarni almashtirish qoidas
Agar predikatlar hisobining keltirib chiqariluvchi ℑ formulasidagi erkin o‘zgaruvchi predmetlarni, shu o‘zgaruvchilar qaerda qatnashsa o`sha joylarning barchasida boshqa erkin o‘zgaruvchi predmetlar bilan almashtirib chiqsak, hosil bo‘lgan ifoda yana predikatlar hisobining keltirib chiqariluvi formulasi bo‘lad
2.10. Bog‘liq o‘zgaruvchi predmetni almashtirish qoidas
Predikatlar hisobining keltirib chihariluvchi ℑ formulasida bog‘li= o‘zgaruvchi predmetlarni, shu o‘zgaruvchini bog‘lagan kvantorning ta’sir sohasiga tegishli hamma joylarda ℑ dagi barcha erkin o‘zgaruvchi predikatlardan farq qiladigan boshqa bog‘liq o‘zgaruvchi predmetlar bilan almashtirsak, hosil bo‘lgan ifoda predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad
2.12. Kvantorlar bilan bog‘lash qoidalari .
Agar ℑ Þ ℬ ( x ) predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lib, x o‘zgaruvchi ℑ da qatnashmasa ℑ Þ "x ℬ ( x ) predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad
Agar ℑ ( x ) Þ ℬ predikatlar hisobining keltirib chiqariluvchi formulalari bo‘lib, x o‘zgaruvchi ℬ da qatnashmasin. $ ℑ ( x ) Þ ℬ predikatlar hisobining keltirib chiqariluvchi formulasi bo‘lad
. Predikatlar hisobida keltirib chiqariluvchi formula tushunchasi
1 – ta’rif. 1. Predikatlar hisobining har bir aksiomasi keltirib chiqariluvchi formuladir.
2. Predikatlar hisobining keltirib chiqariluvchi formulalariga 2 bayon qilingan keltirib chiqarish qoidalari ni chekli marta qo‘llash natijasida hosil qilingan formulalar ham predikatlar hisobining keltirib chiqariluvchi formulalari bo‘lad
3. Boshqacha usulda keltirib chiqariluvchi formulalar hosil qilib bo‘lmayd Predikatlar hisobining zidsizligi
Aksiomatik nazariyada birorta formula va uning inkori keltirib chiqariluvchi bo‘lsa, bunday nazariya ziddiyatli nazariya, aks holda zidsiz nazariya deyilishi ma’lum.
4.1 – teorema. Predikatlar hisobi zidsiz nazariyadir.
Bu tasdiqni isbot qilish sxemasini beramiz.
Predikatlar hisobining har bir formulasiga mulohazalar hisobining formulasini quyidagi usulda mos qo‘yamiz :
Hamma formulalarni predikatlar algebrasining bir elementli { a } to`plamda aniqangan formulasi deb faraz qilamiz. U holda har bir predikatga mulohaza mos kelad Masalan, / ( x1, . . . ,xn ) – predikatga / ( a, . . . , a ) mulohaza mos kelad "x ℑ ( x ) , $x ℑ ( x ) formulalar o`rniga ℑ ( a ) formula hosil bo‘lad Predikatlar hisobining elementar formulalari o`rniga mulohazalar algebrasining elementar formulalari, predikatlar hisobining keltirib chiqarish qoidalari mulohazalar hisobining keltirib chiqarish qoidalari ga aylanad Natijada predikatlar hisobining keltirib chqariluvchi formulalari mulohazalar algebrasining aynan rost formulalariga aylanad SHunday qilib, predikatlar hisobi ziddiyatga ega bo‘lsa, u holda mulohazalar algebrasida bitta formulaning o`zi ham aynan rost, ham aynan yolg‘on formula bo‘lib qolar ed Buning esa bo‘lishi mumkin emas.
Do'stlaringiz bilan baham: |
