17-Ma’ruza. Deduksiya teoremasi. Mos keltirib chiqarish haqida lemma. To’liqlik haqida Gyodel teoremasi

17-Ma’ruza. Deduksiya teoremasi. Mos keltirib chiqarish haqida lemma. To’liqlik haqida Gyodel teoremasi.


4.1. Isbotlash tushunchasi
4.1.1. Formulani keltirib chiqarish qoidasi. chekli formulalar majmuasi (to‘plami) berilgan bo‘lsin. Bu formulalar majmuasidan formulani keltirib chiqarish tushunchasini o‘rganamiz.
1-ta’rif. 1) Har qanday formulalar majmuasi dan keltirib chiqariladigan formuladir.
2) Har qanday isbotlanuvchi formula dan keltirib chiqariladi.
3) va lar formulalar majmuasidan keltirib chiqarilgan formulalar bo‘lsa, u holda formula ham dan keltirib chiqariladi.
Biror formula formulalar majmuasidan keltirib chiqariladigan bo‘lsa, uni simvolik ravishda shaklda yozamiz.
Agar bo‘sh to‘plam yoki elementlari faqat isbotlanuvchi formulalardan iborat bo‘lsa, u holda dan keltirib chiqariladigan formulalar sinfi isbotlanuvchi
formulalar sinfi bilan mos keladi. Agar formulalar majmuasi ning hech bo‘lmaganda bitta elementi isbotlanmaydigan formuladan iborat bo‘lsa, u holda dan keltirib chiqariladigan formulalar sinfi isbotlanuvchi formulalar sinfiga nisbatan kengroq bo‘ladi.
Misol. formula formulalar majmuasidan keltirib chiqarilishini ko‘rsatamiz. Haqiqatdan ham, va bo‘lgani uchun formulani keltirib chiqarish qoidasiga asosan quyidagilar o‘rinli:
, (1)
. (2)
II₃ va I₁ aksiomalarga nisbatan va o‘rniga qo‘yishlarni bajaramiz. Natijada isbotlanuvchi formulalar hosil bo‘ladi. Ular formulani keltirib chiqarish qoidasiga asosan dan keltirib chiqariladi, ya’ni
, (3)
(4)
kabi bo‘ladi. isbotlanuvchi formula bo‘lgani uchun
. (5)
(5) va (3) formulalardan xulosa qoidasiga asosan
(6)
hosil bo‘ladi. Xuddi shu kabi (2) va (4) formulalardan
(7)
munosabatga kelamiz. (7) va (6) formulalardan xulosa qoidasiga asosan
(8)
kelib chiqadi. U holda (1) va (8) formulalardan
(9)
hosil bo‘ladi, ya’ni formula formulalar majmuasidan kelib chiqishini ko‘rsatdik.
formulalar majmuasidan birorta ixtiyoriy formulani keltirib chiqarishda
murakkab xulosa qoidasidan ham foydalansa bo‘ladi.
Bu holda (9) munosabatga (5), (7), (1) va (3) mulohazalar yordamida kelish mumkin.