O’zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi nukus innovatsion instituti

Lemma. formulalar majmuasidan keltirib chiqarilgan formulalar ketma-ketligidagi formula formulaga bog‘liq bo‘lmasa, u holda .
Isboti. Lemmaning isbotini matematik induksiya metodi bilan o‘tkazamiz.
Baza. hol uchun lemma to‘g‘ridir. Haqiqatdan ham, agar formulalar majmuasidan formula keltirilib chiqarilgan bo‘lsa va u formulaga bog‘liq bo‘lmasa, u holda yo , yoki formula isbotlanuvchi formula bo‘ladi. Ikkala holda ham .
Induksion o‘tish. Endi lemmanning xulosasi uzunlikdagi keltirib chiqarish formulalari uchun to‘g‘ri deb faraz qilamiz va uning uzunlikdagi keltirib chiqarish formulalari uchun to‘g‘riligini isbot qilamiz. Agar yoki isbotlanuvchi formula bo‘lsa, u holda .
Agar formula o‘zidan oldin turgan bitta yoki ikkita formulalardan keltirib chiqarilgan bo‘lsa, u holda formula formulaga bog‘liq bo‘lmaydi, chunki induktiv farazimizga asosan keltirib chiqarish formulalari takibidagi dan oldin turgan hamma formulalar ga bog‘liq emas. Demak, .
Deduksiya teoremasi. va formulalar majmuasidan keltirib chiqarilgan formula mavjud bo‘lsin. formulaga bog‘liq bo‘lib keltirib chiqarilgan formulalarga kvantor bilan bog‘lash qoidasini qanday qo‘llashimizdan qat’iy nazar formulaga kiruvchi erkin o‘zgaruvchilarning birortasi kvantor bilan bog‘lanmasin. U holda .
Isboti. formulalar formulalar majmuasidan keltirib chiqarilgan teoremaning shartlarini qanoatlantiruvchi formulalar bo‘lsin. Isbotni matematik induksiya metodi bilan olib boramiz.
Baza. hol uchun teorema to‘g‘ridir. Haqiqatdan ham, agar formula majmuaning keltirib chiqarish formulasi bo‘lsa, u holda
a) yo ,
b) yo – isbotlanuvchi formula,
d) yoki formula formulaning o‘zidir.
a) va b) hollarda va formula isbotlanuvchi formula bo‘lgani uchun xulosa qoidasiga asosan natijaga ega bo‘lamiz.
d) holda formula formulaga aylanadi, ya’ni isbotlanuvchi formula bo‘ladi. Shuning uchun bo‘ladi, bu esa formulani dan keltirib chiqarish mumkinligini anglatadi.
Induksion o‘tish. Endi uzunlikdagi keltirib chiqarish formulalari uchun teorema to‘g‘ri bo‘lsin va uni uzunlikdagi keltirib chiqarish formulalari uchun isbot qilamiz. formulalar formulalar majmuasining keltirib chiqarish formulalari bo‘lsa, faqatgina quyidagi hollar yuz berishi mumkin:
a) ,
b) – isbotlanuvchi formula,
d) formula formulaning o‘zidir,
e) formulasi keltirib chiqarish formulalari tarkibidagi o‘zidan oldin keladigan va ( ) formulalardan xulosa qoidasiga asosan hosil qilinadi,
f) formula keltirib chiqarish formulalari tarkibidagi ( ) formuladan kvantorni bog‘lash qoidasiga asosan olinadi.
a), b), d) hollar uchun teorema isboti hol uchun berilgan isbot bilan bir xildir.
To‘rtinchi e) holni ko‘raylik. Bu yerda formula ikkita va ( ) formulalardan keltirib chiqarilganligi tufayli formula ko‘rinishga ega bo‘ladi va
, (1)
(2)
tasdiqlar to‘g‘ri bo‘ladi.
formula bilan ifodalanuvchi ikkinchi aksiomadan foydalanib, qo‘yidagini hosil qilamiz
. (3)
Murakkab xulosa qoidasidan foydalanib, (3), (2) va (1) formulalardan

formulani keltirib chiqaramiz.
Oxirgi beshinchi f) holni ko‘ramiz. formulalar majmuasidan keltirilib chiqarilgan formulalar orasida ( ) shundayki, formula bo‘lsin.
Farazimizga ko‘ra yo formula formulaga bog‘liq emas, yoki o‘zgaruvchi formulaning erkin o‘zgaruvchisi bo‘lmaydi.
Agar formula formulaga bog‘liq bo‘lmasa, u holda lemmaga asosan . Bu formulaga kvantorni bog‘lash qoidasini qo‘llab formulani hosil qilamiz, ya’ni . Shundan so‘ng formula bilan ifodalanuvchi birinchi aksiomadan foydalanib, formulani keltirib chiqaramiz. Demak, .
Agar o‘zgaruvchi formulaning erkin o‘zgaruvchisi bo‘lmasa, u holda formula bilan ifodalanuvchi beshinchi aksiomadan foydalanamiz. bo‘lgani uchun kvantorni bog‘lash qoidasidan foydalanib formulani hosil qilamiz. Bu formuladan xulosa qoidasiga asosan formulani keltirib chiqaramiz. Bundan o‘z navbatida formula kelib chikadi.
Shunday qilib, deduksiya teoremasi beshala hol uchun ham to‘g‘ridir.