Predikat tushunchasi. Predikatlar ustida mantiqiy amallar

2 - teorema (Post teoremasi). M to ‘plamning о‘zi va to‘IdiruvchisiC M effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina Mto ‘plam rekursivdir.
I s b o t i .a) M to‘plam va uning C M to'ldiruvchisi effektiv rekursivsanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to‘plamlamingelementlarini sanab chiqa oladigan A va Вalgoritmlar mavjud bo'ladi. Uholda M va C M to'plamlaming elementlarini sanab chiqish paytidalarning ro'yxatida x element uchraydi. Demak, shunday С algoritmyuzaga keladiki, u orqali Jt element M to'plamga qarashlimi yokiqarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, Mrekursiv to‘plam bo'ladi.
b) M rekursiv to‘plam bo'lsin. U holda, 1- ta’rifga asosan, x buto'plamning elementimi yoki elementi emasmi degan muammoni halqiluvchi algoritm mavjud bo‘ladi. Bu algoritmdan foydalanib, M va C Mto‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib,M va C M to‘plamlar elementlarini sanab chiquvchi ikkita A va Вalgoritmni hosil qilamiz. Demak, M va C M to‘plamlar effektiv rekursivsanaluvchi to‘plamlar bo'ladi.
3- t e o r e m a .Rekursiv bo ‘Imagan effektiv rekursiv sanaluvchinatural sonlar to 'plami mavjud.
I s b o t i . Effektiv rekursiv sanaluvchi ixtiyoriy U natural sonlarto‘plami berilgan bo'lsin. U to'plamning rekursiv emasligini isbotlashuchun, Post teoremasiga (2- teorema) ko'ra, uning C U to'ldiruvchisieffektiv rekursiv sanaluvchi emasligini isbotlash yetarli.
- hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo isin. Demak, harqanday (m,n)uchun to‘plamni tiklash mumkin.Endi U to‘plamning hamma elementlarini sanab chiqadigan Aalgoritmni kiritaylik. Bu algoritm (m , n) raqamli qadamda nihisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda Aalgoritm uni U to‘plamga kiritadi, ya’ni .
Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdanC U to‘plam hech boimaganda bitta element bilan farq qiladi, chunkiC U shunday n elementlardan iboratki, . Shuning uchun hamC U rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosanU rekursiv to‘plam boim aydi.
I z о h . Isbot qilingan bu teorema aslida Gyodelning formal arifme-tika
toiiqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan.
************