Mavzu: mulohazalar hisobida yechilish, zidsizlik, to’liqlilik va erkinlik muomolari

A isbotlanmaydigan tasdiq boiganidan A isbotlanadigan tasdiq bo’ladi.

Shunday qilib, yangi nazariyada A va A isbotlanuvchi boidi, ya’ni qarama-qarshilikka keldik. Demak, farazimiz noto‘g‘ri va har qanday absolyut to’liq nazariya tor ma’noda ham to’liq bo’lar ekan.

2.4 NAZARIYANING YECHILISH VA ERKINLIK MUAMMOLARI

YECHILISH MUAMMOSI

Yechilish muammosi. Yechilish muammosi algoritmik muammo bo’lib, unda berilgan A to'plam uchun shunday algoritm (uni bilan belgilaymiz) tuzish kerakki, bu algoritm A ni boshqa В to‘plamga nisbatan (A cz B) yechuvchi (hal etuvchi) boisin, ya’ni bu U algoritm В ning har bir elementiga tatbiq etiladi hamda x e A lar uchun £/(*) = 1, x e В \ A lar uchun esa U ( x ) —0 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 ( A to‘plam) nazariyaning hamma formulalar to‘plamiga ( В to‘plam) nisbatan yechilish muammosidir. Biz uni mulohazalar hisobining aksiomatik nazariyasi uchun ko‘rgan edik.