Vi bob matematik nazariyalar

6.5. Deduksiya teoremasi


Deduksiya teoremasi. Formulalar majmuasidan formulani keltirib chiqarish. Deduksiya teoremasining isboti.


6.5.1. Deduksiya teoremasi. Mulohazalar hisobida

deduksiya teoremasi o‘rinli edi. Ixtiyoriy birinchi tartibli nazariyada bu teorema ayrim o‘zgartirishlarsiz o‘rinli bo‘lmay qoladi. Masalan, har qanday birinchi tartibli nazariyada o‘rinlidir, ammo har doim ham formula isbotlanuvchi bo‘lavermaydi. Haqiqatan ham, hech bo‘lmaganda to‘plamning ikki elementini qamragan soha berilgan holni qarab bunga ishonish mumkin.

– predikatlar hisobi va formula ko‘rinishda bo‘lsin. formula faqatgina element egallagan xususiyatga ega deb interpretasiya beramiz. U holda formula elementi bo‘lgan to‘plamda bajariluvchi bo‘ladi, ammo shu bilan birga o‘zida formula to‘plamda bajariluvchi formula emas.
Mulohazalar hisobidagi deduksiya teoremasining shartlarini biroz kuchsizlantirganimizdagina u birinchi tartibli nazariyada o‘rinli bo‘ladi. Buning uchun birinchi tartibli nazariyada formulalar majmuasidan formulalarni keltirib chiqarish qoidasini aniqlab olaylik. Shu maqsadda, avvalo, bir yordamchi tasdiqni isbot qilamiz.
formulalar majmuasi va bu majmuadan keltirib chiqarilgan formulalar ketma-ketligini ko‘raylik. Bu keltirib chiqarishda formula formula bilan quyidagi ikki holda bog‘liq bo‘ladi deb aytamiz:
1) formula formulaning o‘zidir va u keltirilib chiqarilgan formulalar tarkibiga formulalar majmuasida mavjud bo‘lgan formula sifatida kiritilgan;
2) formula keltirilib chiqarilgan formulalardagi o‘zidan oldin turgan formulalardan xulosa qoidasi va kvantorni bog‘lash yo‘li bilan hosil qilingan. O‘zidan oldin turgan formulalarning hech bo‘lmaganda birortasi formulaga bog‘liq. Masalan, formulalar majmuasidan
, , , ,
formulalarni keltirib chiqarish mumkin. Bu formulalarning har biri formulaga bog‘liq.
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, . ■