Vi bob matematik nazariyalar

6.8.3. Yechilish muammosi. Yechilish muammosi algoritmik muammo bo‘lib, unda berilgan to‘plam uchun shunday algoritm (uni bilan belgilaymiz) tuzish kerakki, bu algoritm ni boshqa to‘plamga nisbatan yechuvchi (hal etuvchi) bo‘lsin, ya’ni bu algoritm ning har bir elementiga tatbiq etiladi hamda lar uchun , lar uchun esa deb hisoblanadi.
Yechilish muammosiga oddiy misol sifatida mulohazalar algebrasidagi yechilish muammosini ko‘rsatish mumkin, u shunday algoritmni topishdan iboratki, bu algoritm vositasi bilan mulohazalar algebrasidagi har bir formulaning yo aynan chin, yo aynan yolg‘on, yoki bajariluvchi ekanligini aniqlash mumkin. Algoritmik muammoning muhim sinfi formal nazariyalar uchun yechilish muammosidir, ya’ni hamma isbotlanuvchi formulalar to‘plami uchun formulalar nazariyasidagi ( to‘plam) nazariyaning hamma formulalar to‘plamiga ( to‘plam) nisbatan yechilish muammosidir. Biz uni mulohazalar hisobining aksiomatik nazariyasi uchun ko‘rgan edik.
6.8.4. Predikatlar hisobining zidsizligi (maxsus aksiomalarsiz nazariya).
4- ta’rif. Maxsus aksiomalarga ega bo‘lmagan birinchi tartibli nazariya birinchi tartibli predikatlar hisobi deb ataladi.
Teorema. Ixtiyoriy birinchi tartibli predikatlar hisobi zidsizdir.
Isboti. Ixtiyoriy formuladan quyidagicha o‘zgartirishlar natijasida hosil qilinadigan ifodani bilan belgilaymiz. formuladagi hamma kvantor va termlar qavslar va vergullari bilan birgalikda tashlab yuboriladi. Masalan, formula yuqorida ko‘rsatilgan o‘zgartirishlardan keyin ko‘rinishni oladi, ya’ni ifoda ko‘rinishga, xuddi shu kabi ifoda ko‘rinishga keladi.
Ravshanki, va . Osongina ko‘rsatish mumkinki, predikatlar hisobining formulasi uchun formula mulohazalar hisobining formulasidir va qandaydir sxema vositasidai 1–5- aksiomalardan (ushbu bobning 3- paragrafga qarang) hosil qilingan har qanday aksioma uchun tavtologiya bo‘ladi. Bu 1–3- aksiomalar shundaygina ko‘zga tashlanib turibdi. aksioma uchun formula ko‘rinishda bo‘ladi, ya’ni u tavtologiyadir. aksioma uchun ifoda munosabatga aylanadi, ya’ni bu ham tavtologiyadir.
Agar mulohazalar hisobidagi xulosa qoidasini , tavtologiyalarga qo‘llasak, u holda tavtologiyaga kelamiz. Shunday qilib, agar va tavtolo-giyalar bo‘lsa, u holda ham tavtologiya bo‘ladi.
operasiyasini va formulalarga qo‘llash natijasida olingan natijalar bir xil bo‘lganligi uchun, agar tavtologiya bo‘lsa, u holda ham tavtologiya bo‘ladi.
Demak, agar predikatlar hisobida teorema bo‘lsa, u holda tavtologiya bo‘ladi.
Yuqoridagilardan shu narsa kelib chiqadiki, agar predikatlar hisobida va isbotlanuvchi bo‘ladigan shunday formula mavjud bo‘lsa edi, u holda mulohazalar hisobida va lar tavtologiya, ya’ni isbotlanuvchi formulalar bo‘lar edi. Ammo bu mumkin emas. Demak, predikatlar hisobi zidsizdir. ■
Ta’kidlaymizki, operasiyasi predikatlar hisobining bir elementli sohaga interpretasiyasi bilan teng kuchlidir. Predikatlar hisobining hamma teoremalari bu interpretasiyada to‘g‘ridir (chindir).