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

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. ■

4.2.5. V qoida. (Deduksiya teoremasi.) .
Isboti. Avval formulalar majmuasining har qanday keltirib chiqarishi uchun ning to‘g‘riligini matematik induksiya metodidan foydalanib isbot qilamiz.
Baza. hol uchun tasdiq to‘g‘ri. Haqiqatan ham, agar formula ning keltirib chiqarishi bo‘lsa, u vaqtda quyidagi uch hol bo‘lishi mumkin:
a) ,
b) isbotlanuvchi formuladir,
d) formula ning o‘zidir.
a) va b) hollar uchun dan quyidagi keltirib chiqarishni yozish mumkin: , , . Demak, .
d) hol uchun bo‘lishini isbotlash kerak.
Ravshanki, isbotlanuvchi formuladir. Shuning uchun uni har qanday majmuadan keltirib chiqarish mumkin.
Induksion o‘tish. Endi istalgan ( ) chuqurlikdagi har qanday keltirib chiqarish uchun tasdiq to‘g‘ri bo‘lsin deb hisoblab, uning chuqurlikdagi keltirib chiqarish uchun to‘g‘riligini isbot qilamiz.
lar majmuaning keltirib chiqarishi bo‘lsin, bu yerda . U vaqtda formulaga nisbatan quyidagi to‘rt hol yuz berishi mumkin:
a) ,
b) isbotlanuvchi formuladir,
d) formula ning o‘zidir,
e) formula xulosa qoidasiga asosan keltirib chiqarishdagi ikkita undan
oldin ketma-ket keladigan formulalardan hosil qilinadi.
a), b), d) hollar uchun isbot to‘liq ravishda holdagi isbotga mos keladi.
Shuning uchun e) holni ko‘ramiz. Bu holda formula va formulalardan hosil qilinib , formula ko‘rinishni oladi va quyidagi tasdiqlar o‘rinli bo‘ladi:
, (5)
. (6)
I₂ aksiomada

o‘rniga qo‘yishni bajarib, quyidagi isbotlanuvchi formulaga ega bo‘lamiz:

. (7)
(6), (5) va (7) ifodalar dan keltirib chiqariladigan formulalardir. Ularga murakkab xulosa qoidasini qo‘llab, ni hosil qilamiz.
Endi umumiy, ya’ni bo‘lgan holni ko‘raylik. U holda ning , keltirib chiqarishi mavjud bo‘ladi. Demak, yuqoridagi mulohazalarga asosan tasdiq to‘g‘ridir. ■
Deduksiya teoremasidan quyidagi muhim ahamiyatga ega bo‘lgan tasdiq kelib chiqadi.