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

1-teorema. nazariyaning har qanday teoremasi tavtologiya bo‘ladi.
Isbot. nazariyaning har bir aksiomasi tavtologiya bo‘lishini osongina tekshirib ko‘rish mumkin. Ravshanki, MP qoidasini tavtologiyalarga qo‘llash natijasida hosila bo‘lgan formulalar ham tavtologiya bo‘ladi. Demak, nazariyaning har qanday teoremasi tavtologiya bo‘lar ekan.
2-teorema. (Gyodelning to‘liqlik haqidagi teoremasi). (44-bet)
Agar formula nazariyada tavtologiya bo‘lsa, u holda u nazariyaning teoremasi bo‘ladi.
Isbot (Kalmar). Faraz qilaylik, formula tavtologiya va lar tarkibiga kiruvchi propozitsional xarflar bo‘lsin. xarflarning har bir chinlik taqsimoti uchun 4.1-lemma. ga asosan
├ .
ga ega bo‘lamiz, chunki tavtologiya bo‘lgani uchun formula dan iboratdir. Shuning uchun, rost qiymat qabul qilsa


, ├ ga,


yolg‘on qiymat qabul qilganda esa


├ ga

ega bo‘lamiz. Bularga deduksiya teoremasini qo‘llab,

, ├ .
, .
larni hosil qilamiz.
1-teorema (h) punktga asosan
├ .
ni hosil qilamiz.
Xuddi shu jarayonni takrorlab, ni ham yo‘qotish mumkin. Umuman qadamda keyin esa biz ├ ga ega bo‘lamiz.
1-natija.Agar ifoda belgilarni o‘z ichiga olsa va nazariyaning qandaydir formulasining soddalashtirilgani ( ) ta’riflarga qarang) bo‘lsa, u holda formula tavtologiya bo‘lishi uchun formula nazariyaning teoremasi bo‘lishi zarur va etarlidir. (44-bet)
2-natija. sistema zidsiz sistemadir, ya’ni da bir vaqtda ham, ham teorema bo‘ladigan formula mavjud emas. (44-bet)
Isbot. 1-teoremaga asosan nazariyaning har qanday teoremasi tavtologiya bo‘ladi. Tavtologiyaning inkori esa tavtologiya bo‘la olmaydi. Shuning uchun xech bir formula uchun va formulalar bir vaqtda nazariyaning teoremalari bo‘la olmaydi.
nazariyaning zidsizligidan unda teorema bo‘lmaydigan formulaning mavjudligi kelib chiqadi (masalan, ixtiyoriy teoremaning inkori).
Ikkinchi tomondan esa, ning zidsizligini nazariyada teorema bo‘lmaydigan formulalarning mavjudligidan keltirib chiqarish mumkin edi. Haqiqatan ham, 1-teorema (c) punktga asosan
├
ga ega bo‘lamiz va demak agar nazariya ziddiyatli nazariya bo‘lganda edi, ya’ni qandaydir formula va o‘zining inkori chiqariladigan bo‘lganda edi, u holda ├ va qoidasiga asosan dagi har qanday formula keltirib chiqariladigan bo‘lar edi.
Barcha formulalari teorema bo‘lmaydigan nazariyani absolyut zidsiz nazariya ham deyiladi. Demak, biz qarayotgan nazariya absolyut zidsiz nazariya ekan.
Biz bu erda keltirgan aksiomalar sistemasi E.Mendelson kitobida kiritilgan aksiomalar sistemasidan uchinchi aksiomasi bilan farq qiladi.
E.Mendelson kitobida isbotlangan lemmalar va biz isbotini keltirgan faktlar shuni ko‘rsatadiki, bu ikkala taklif qilingan aksiomalar sistemasi ekvivalent ekan (ya’ni teoremalar to‘plami ustma-ust tushadi).
Asosiy darsliklar va o’quv qo’llanmalar

1. Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012. (71-74 betlar)

1. 
   Mendelson E. Vvedenie v matematicheskuyu logiku. M. «Nauka». 1984
   
2. 
   Lavrov I.A., Maksimova L.L. Zadachi po teorii mnojestv, matematicheskoy logike i teorii algoritmov. M. «Nauka» 1995