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

4.2. Keltirib chiqarishning asosiy qoidalari
va mulohazalar hisobining ikkita formulalar majmuasi bo‘lsin. Bu majmualarning yig‘indisini (birlashmasini) deb belgilaymiz, ya’ni
.
majmua bitta formuladan iborat bo‘lganda ham birlashmani ko‘rinishda yozamiz.
Endi keltirib chiqarishning asosiy qoidalarini o‘rganamiz.
4.2.1. I qoida. .
Isboti. Bu qoida bevosita formulalar majmuasidan keltirib chiqarish qoidasi asosida hosil bo‘ladi.
4.2.2. II qoida. .
Isboti. Bu qoidaning shartiga asosan formulalar majmuasidan formula keltirib chiqariladi. Shuning uchun dan oxirgi formulasi bo‘lgan
keltirib chiqarish mavjud: . (1)
Xuddi shu kabi formulalar majmuasidan formulani keltirib chiqarish mumkinligidan dan keyingi formulasi bo‘lgan keltirib chiqarish mavjud:
. (2)
(1) keltirib chiqarishda formula ishtirok etmagan holda, u faqat formulalar majmuasidan keltirib chiqarilgan ketma-ketlikda bo‘ladi. Demak, dan formula keltirib chiqariladi.
Agar (1) keltirib chiqarishda birorta formula bo‘lsa (masalan, formula ), u holda va formulalar orasiga (2)ni qo‘yamiz. Natijada quyidagi faqat dan keltirib chiqarishni olamiz:
.
Shunday qilib, dan formula keltirib chiqariladi. ■
4.2.3. III qoida. .
Isboti. bo‘lganligi uchun I qoidaga asosan . Qoidaning shartiga binoan , u holda I qoidaga ko‘ra . II qoidadan foydalanib ni topamiz.
4.2.4. IV qoida. .
Isboti. formula formulalar majmuasidan keltirib chiqariladigan bo‘lgani sababli ning shunday keltirib chiqarishi mavjudki, uning oxirida formula turadi:
. (3)
Endi formulalar majmuasiga formulani qo‘shib, formulalar majmuasini hosil qilamiz. (3) keltirib chiqarishga formulani qo‘shib, ushbu keltirib chiqarishga ega bo‘lamiz:
. (4)
O‘z navbatida bu formulalar majmuasining keltirib chiqarishi bo‘ladi. (4)ning oxiriga formulani yozish mumkin, chunki u xulosa qoidasiga asosan va
formulalardan hosil qilinadi.
Demak, oxirgi formulasi bo‘lgan formulalar majmuasining

keltirib chiqarishiga ega bo‘lamiz. Bu yerdan ekanligi kelib chiqadi. ■