L nazariya uchun gyodelning toliqlik

L NAZARIYA UCHUN GYODELNING TOLIQLIK
HAQIDA TEOREMASI.

Quyidagi lemma har bir tavtologiyaning teorema bo‘lishligini isbotlashda qo‘llaniladi.

1-lemma. Faraz qilaylik formula lar esa formula tarkibiga kiruvchi propozitsional xarflar bo‘lsin va bundan tashqari lar uchun rostlik (chin) qiymatlarining qandaydir taqsimoti berilgan bo‘lsin. orqali agar rost qiymat qabul qilsa ni, agar yolg‘on qiymat qabul qilsa 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 3.1-teorema (e) punktga asosan ├ , hosil bo‘ladi. formula esa dan iboratdir.
2-teorema. nazariyaning har qanday teoremasi tavtologiya bo‘ladi.