Ma’ruza 12: nazariya uchun gyodelning toliqlik haqida teoremasi reja

Ma’ruza 12: NAZARIYA UCHUN GYODELNING TOLIQLIK HAQIDA TEOREMASI


Reja:

1. 
   Mos keltirib chiqarish haqida lemma.
   
2. 
   Gyodelning to‘liqlik haqidagi teoremasi .
   
3. 
   Gyodel teoremasining natijalari.
   

Mos keltirib chiqarish haqida lemma.

Quyidagi lemma har bir tavtologiyaning teorema bo‘lishligini isbotlashda qo‘llaniladi. (43-bet)

1-lemma.Farazqilaylik formula laresa formulatarkibigakiruvchipropozitsionalxarflarbo‘lsinvabundantashqari laruchunrostlik (chin) qiymatlariningqandaydirtaqsimotiberilganbo‘lsin. orqaliagar rostqiymatqabulqilsa ni, agar yolg‘onqiymatqabulqilsa belgilaymiz. Xudi shunday orqali agar shu taqsimotda formula rost qiymat qabul qilsa ni, agar formula yolg‘on qiymat qabul qilsa ni belgilaylik. U holda
├ .
Agar, masalan formula ko‘rinishda bo‘lsa, u holda

rostlik jadvalining har bir satri uchun 1-lemma ularga mos kelgan keltirib chiqarishni bildiradi.
Xususan, uchinchi satr uchun
├ ,
to‘rtinchi satr uchun esa
├
tasdiqlar mos keladi.
Isbot. Isbotni formulaning tarkibiga kiruvchi primitiv bog‘lovchilar soni bo‘yicha olib boriladi (tabiiyki, formula soddalashtirishlarsiz yozilgan deb faraz qilamiz).
Agar bo‘lsa, u holda formula propozitsional xarf ko‘rinishda bo‘ladi va lemmaning tasdig‘i ├ va ├ ko‘rinishda bo‘ladi.
Endi esa, faraz qilaylik lemma barcha lar uchun o‘rinli bo‘lsin.
1a-hol. formula ko‘rinishda bo‘lsin. ning tarkibiga kiruvchi primitiv bog‘lovchilar soni dan kichikdir.
Rostlik qiymatlarining berilgan taqsimotida rost qiymat qabul qilsin. U holda yolg‘on qiymat qabul qiladi. Shunday qilib, formula ko‘rinishda, formula esa ko‘rinishda bo‘ladi. Induksiya faraziga bilan ├ ga ega bo‘lamiz.
1-teoremaning (b) punktiga va MP qoidasiga asosan ├ . kelib chiqadi. Ammo esa ni bildiradi.
1b-hol. G rost qiymat qabul qilsin. U holda formula , bo‘lib esa bilan ustma-ust tushadi. Induksiya faraziga asosan ├ hosil bo‘ladi. formula esa dan iborat bo‘lgani uchun bu hol ham isbotlandi.
2-hol. formula ko‘rinishda bo‘lsin. U holda . va lar tarkibiga kiruvchi primitiv bog‘lovchilar soni dagi bog‘lovchilar sonidan kichik.
Shuning uchun induksiya farazga asosan
├
va
├ .
larga ega bo‘lamiz.
2a-hol. rost qiymat qabul qilsin. U holda formula va formula ko‘rinishga ega bo‘ladi. Shunday qilib, ├ ga

va 1-teorema (c) punktga asosan

├
hosil bo‘ladi. formula bo‘lgani uchun, bu hol ham isbotlandi.
2b-hol. H rost qiymat qabul qilsin. U holda formula ham rost qiymat qabul qiladi va formula va formula ko‘rinishga ega bo‘ladi.
├
dan va aksiomadan
├
ni hosil qilamiz. esa dan iboratdir.
2s-hol. rost va yolg‘on qiymat qabul qilsin. U holda formula yolg‘on qiymat qabul qiladi va u ko‘rinishda bo‘ladi, esa va formula ko‘rinishda bo‘ladi.
├
va ├ larga ega bo‘lamiz.
Bu erda 1-teorema (e) punktga asosan ├ , hosil bo‘ladi. formula esa dan iboratdir.