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

2.2. KELTIRIB CHIQARISH QOIDASI. XULOSA QOIDASI. UMUMLASHTIRISH QOIDASI.
Keltirib chiqarish qoidasi. Xuddi mulohazalar hisobidagidek, H formulalar majmuasida keltirib chiqarish tushunchasidan foydalanamiz. H formulalar majmuasiga kiruvchi mulohazalami (formulalarni) shartlar deb ataymiz. Agar H majmuadan keltirib chiqarilgan ifodaning oxirida A mulohaza (formula) joylashgan bo’lsa, u holda A mulohaza H dan keltirib chiqarilgan deb aytamiz va H A ko’rinishda yozamiz. Xususan, bo‘1sa, u holda A ko‘rinishda yoziladi.
Birinchi tartibli nazariyaning keltirib chiqarish qoidasi tarkibiga ushbu ikkita qoida kiradi.

1. 
   Xulosa qoidasi (yoki modus ponens):
   

2. 
   Umumiylik kvantori bilan bog ‘lash qoidasi (yoki umumlashtirish qoidasi):
   

2.3. NAZARIYANING ZIDSIZLIK VA TO’LIQLILIK MUAMMOLARI

Zidsiz nazariya. Ziddiyatga ega bo ‘lgan nazariya. Zidsizlik muammosi.

Absolyut to’liq nazariya. Tor mа’noda to‘liq nazariya. To'liqlilik muammosi.

Yechilish muammosi. Birinchi tartibli predikatlar. Predikatlar hisobi. Predikatlar hisobining zidsizligi.

ZIDSIZLIK MUAMMOSI.

1- ta’rif. Agar T nazariyada shunday S mulohaza topilib, o’zining inkori S bilan birga teorema bo ‘lsa, u holda T ziddiyatga ega bo‘lgan nazariya deb ataladi. Aks holda T zidsiz nazariya deyiladi.

Agar T nazariyada S mulohaza topilib, u o‘zining inkori S bilan birga teorema bo’lmasa, shunda va faqat shundagina u zidsiz nazariya bo‘ladi.

20. 
    nazariyada keltirib chiqarish qoidasining biri sifatida xulosa qoidasi mavjud bo’lganidan, ziddiyatga ega bo‘lgan nazariyaning istalgan mulohazasi teorema bo’ladi. Haqiqatan ham, T nazariyaning istalgan A mulohazasi uchun S —» (S —> A ) ifoda teorema bo’ladi, chunki bu mulohaza S —> (S —> A ) tavtalogiyadir. Bu yerda S va S ning teorema ekanligini hisobga olgan holda ikki marta xulosa qoidasidan foydalanib, A teoremadir degan xulosaga kelamiz.
    

Aksiomatik nazariyalarda zidsizlik muammosini ko‘p hollarda model tushunchasi orqali yechish mumkin. Haqiqatan ham, agar T nazariya ziddiyatga ega bo‘lsa, u holda uning modeli ham ziddiyatga ega bo’ladi, chunki nazariyaning bir-biriga qarama-qarshi bo‘lgan juft teoremalari model holida bir-biriga qarama-qarshi bo‘lgan mulohazaga aylanadi. Demak, nazariya zidsiz bo’lishi uchun uning ziddiyatdan holi bo’lgan modeli mavjudligini ko‘rsatish kerak. Mulohazalar hisobining zidsizligini xuddi shu sxema orqali isbot qilgan edik.

Agar T nazariya uchun shunday interpretatsiyani topish mumkin bo’lsaki, uning interpretasiyasi chekli to‘plamdan iborat bo‘lsa, u holda bu interpretatsiyada ziddiyat mavjud emasligi masalasini yechish to‘g‘ridan-to‘g‘ri shu chekli to‘plamni ko‘rish bilan hal bo’ladi.

Masalan, bir elementli to‘plam a elementga ega bo’lsin. Agar bu to‘plamda a -a —a amali aniqlangan bo’lsa, u holda u ziddiyatga ega bo’lmagan guruh nazariyasining modeli bo’ladi. Demak, guruh nazariyasi zidsizdir. Ammo, ko‘pincha modelning zidsizligini isbotlash ancha murakkab fikr yuritishni talab qiladi. Bu, ayniqsa, T nazariya faqat cheksiz modellarga ega bo’lgan hollarda ko'proq yuz beradi.

Masalan, agar Evklid geometriyasining tushunchalari Lobachevskiy1 geometriyasining interpretatsiyasi sifatida foydalanilsa, u holda Lobachevskiy geometriyasining zidsizligi masalasini Evklid geometriyasining zidsizligi masalasiga keltirish mumkin.

Shuni ta’kidlash kerakki, Evklid geometriyasining zidsizligi va haqiqiy sonlar nazariyasining zidsizligi hozirgacha isbot qilingan emas.

TO‘LIQLILIK MUAMMOSI

To‘liqlilik muammosi. Agar biror nazariyaning zidsizligi isbot qilingan bo’lsa (yoki isbot qilinishi mumkin deb hisoblansa), u holda bu nazariya uchun to’liqlilik muammosini qo‘yish ma’noga ega bo’ladi.

2 - ta’rif.Agar T nazariyaning istalgan S mulohazasi uchun yo S ,yoki uning inkori S teorema bo ‘lsa, и holda bu nazariya absolyut to’liq deb ataladi.

Bu ta’rifda ushbu hisobga olingan: T nazariyadagi istalgan S mulohazasining biror modelidagi interpretatsiyasi yo chin, yoki yolg‘on bo‘ladi. U holda T nazariyada yo S , yoki S teorema bo‘lishi kerak.

Bir vaqtda zidsiz va to’liq bo‘lgan T nazariya zidsizlikka nisbatan shu ma’noda maksimal bo‘ladiki, bu nazariyaga aksioma sifatida shu nazariyada mumkin boigan istalgan (ammo uning teoremasi bo'lmagan) mulohazani qo‘shganda, ziddiyatga ega bo'lgan nazariya hosil bo‘ladi.

Ko‘p matematik nazariyalar bir vaqtda zidsiz va to’liq lilik xususiyatiga ega emas.

3- ta’rif. Aksiomalari qatoriga hamma keltirib chiqarish qoidalarini saqlagan holda, istalgan isbotlanmaydigan tasdiqni qo ‘shganda, ziddiyatga ega bo’lgan nazariya hosil bo 'ladigan aksiomatik nazariya tor m a’noda to’liq deb ataladi.

Har qanday absolyut to’liq nazariya tor ma’noda ham to iiq boiadi. Haqiqatan ham, biror absolyut to’liq nazariya tor ma’noda to iiq boimasin. U holda bu nazariyada isbotlanmaydigan shunday A tasdiq topiladiki, avvalgi aksiomalar va yangi aksioma sifatidagi A tasdiqdan yaratilgan yangi nazariya zidsiz, demak A yangi nazariyaga tegishli boiadi. Ikkinchidan, dastlabki nazariyaning absolyut to’liq ligidan va unda

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.

ERKINLIK MUAMMOSI
Har qanday aksiomatik hisobda aksiomalarning erkinlik masalasi, ya’ni birorta aksiomani sistemaning qolgan aksiomalaridan keltirib chiqarish qoidasi orqali hosil etish mumkinmi yoki yo’qmi degan muammo mavjud bo’ladi. Agar biror aksioma uchun bu masala ijobiy X etilsa, u holda bu aksioma sistema aksiomalari ro’yxatidan chiqarib tashlanadi va mantikiy hisob bu bilan o’zgarmaydi, ya’ni isbotlanuvchi formulalar sinfi o’zgarmasdan qoladi .

4 - ta’rif . Agar A aksiomani Mulohazalar hisobining qolgan aksiomalaridan keltirib chikarish mumkin bulmasa, u shu Mulohazalar hisobining boshka aksiomalaridan erkin aksioma deb ataladi.

5 - ta’rif. Agar Mulohazalar hisobi aksiomalar sistemasining har bir aksiomasi erkin bulsa, u holda Mulohazalar hisobining aksiomalar sistemasi erkin deb ataladi.

6 - t e o r e m a . Mulohazalar hisobining aksiomalar sistemasi erkindir.

Isbot. A Mulohazalar hisobining ixtioriy aksiomasi bo’lsin. Bu aksiomaning erkinligini isbotlash uchun Mulohazalar hisobiga nisbatan quyidagi usulni qo’llaymiz: Mulohazalar hisobi o’zgaruvchilarini A yoki R qiymat qabul qiluvchi o’zgaruvchilar sifatida qaraymiz.Bu yerda A chin rolini va R yolg’on rolini o’ynaydi.

l , v , - amallarni shunday aniqlaymizki, quyidagi shartlar o’rinli bo’lsin:

1)A aksiomadan tashqari sistemaning hamma aksiomalari tarkibidagi o’zgaruvchilarning barcha qiymatlarida

faqat A qiymatni qabul qilingan;

2 ) A aksiomadan boshqa, aksiomalar majmuasidan keltirib chiqarilgan har qanday formula ham tarkibidagi o'zgaruvchilarning barcha qiymatlarida faqat A qiymatni qabul kilsin;

3) A aksioma tarkibidagi o’zgaruvchilarning ayrim qiymatlarida R qiymatni qabul qilsin.

Agar A aksiomaga nisbatan yuqorida keltirilgan interpretatsiya (izoxdash) urinli bo’lsa, u holda A aksioma boshqa aksiomalardan erkin ekanligi kelib chiqadi. Xaqiqatan ham, agar A aksiomani mulohazalar hisobining boshqa aksiomalaridan keltirib chiqarish mumkin bo’lganda edi ,u shartlarning ikkinchisiga asosan tarkibidagi o’zgaruvchilarning barcha qiymatlarida faqat a qiymatni qabul qilib, bu esa 3 - shartga zid bular edi. Demak, A aksiomani

Mulohazalar hisobining boshqa aksiomalaridan keltirib chiqarish mumkin emas va u sistemadagi erkin aksiomadir.

O’zgaruvchilarining urniga ularning ayrim qiymatlari qo’yilganda ham formulalar ma’noga ega deb kelishamiz. Masalan, R , a —>A, a —> ( R —» a ) va boshkalar.

6 - ta’rif . Tarkibidagi uzgaruvchilarni a va r bilan al-mashtirganda bir xil qiymat qabul kiluvchi A va V formulalar teng kuchli formulalar deb ataladi hamda bu A = V kuri­ nishda yoziladi.

Tenglik belgisi, l,v , mantikiy boglovchilarga nisbatan sustrok bog’laydi deb hisoblaymiz.

Endi II, aksiomaning erkinligini isbot qilaylik. Buning uchun kon’yunktsiyadan tashkari qolgan hamma mantikiy amallarni xuddi mantiq algebrasidagidek va kon’yunktsiya amalini tenglik orqali aniqlaymiz:

Ushbu interpretatsiya uchun yuqorida keltirilgan uchtashartning bajarilishini ko’rsatamiz.

II,aksiomadan tashqari Mulohazalar hisobining qolgan hamma aksiomalari o’zgaruvchilarning barcha qiymatlarida A qiymat qabul kiladi (bu xolni chinlik jadvali orqali ko’rsatish mumkin).

Xakikatan ham I,III va IV guruh aksiomalarida kon’yunktsiya amali qatnashmaydi. Qolgan mantikiy amallar xuddi Mulohazalar algebrasidagidek aniqlangan.

Mulohazalar algebrasida bu formulalar aynan chin formulalar bo’lganligidan ushbu interpretatsiyada o’zgaruvchilarning barcha qiymatlarida qiymat qabul qiladi .

I, II, va III, aksiomalarni ko’raylik.

P2 va N3 aksiomalar qabul qilingan interpretatsiyada

u —>u formulaga teng bo’ladi va x = R, x = a qiymat lardar qiymat qabul qiladi, ya’ni hech qachon A qiymat qabul qilmaydi.

Endi aynaniga teng formulalardan keltirib chiqarish qoidasiga asosan hosil qilingan formulalar hammaga tengligini ko’rsatish qoldi, ya’ni 2- shartning bajarilishini ko’rsatish kerak.

Oldingi paragraflarda aynan chin formulalarga o’rniga qo’yish va xulosa qoidalarini qo’llash natijasida chikarilgan formulalar aynan chin formulalar bo’lishini kursatgan edik. Demak, 2 - shart ham bajariladi. Shunday qilib , Mulohaza lar hisobining II, aksiomasi erkin aksioma ekan.Xuddi shu sxemadan foydalanib, Mulohazalar hisobi­ning I, II, III va IV guruh va aridagi har bir aksiomaningerkinligini ko’rsatish mumkin. Demak Mulohazalar hisobining aksiomalar sistemasi erkindir.

AMALIY ISH

Misollar:

1. 
   Misol.
   

2. 
   Misol
   

Sillogizm qoidasi

3-Misol











4-Misol

















5-Misol

3. 
   XULOSA
   

Kurs ishi tayyorlashda matematik mulohazalar qanday yechilishi va ular haqida umumiy ma’lumotga ega bo’ldim. Birinchi tartibli matematik nazariyaning tili, term va formulalari tushunchasi, mantiqiy va xos (maxsus) aksiomalar, keltirib chiqarish qoidasi, nazariyada isbotlash tushunchasi, tavtologiya xususiy hollarining isbotlanuvchanligi, deduksiya teoremasi, nazariya tilining interpretatsiyasi (talqini), berilgan interpretatsiyada formulalaming chinlik qiymatlari, interpretatsiyaning izomorfizmligi, nazariyaning modeli, qat’iyligi, zidsizlik, to‘liqlilik va yechilish muammolari, predikatlar hisobining zidsizligi, natural sonlar nazariyasi, Gyodelning to’liqsizlik haqidagi teoremasi singari masalalar yoritilgan.

Mulohazalar algebrasi va mulohazalar hisobida formulaning tavtalogiya bo’lishi yoki bo‘lmasligini aniqlashning samarali usullaridan biri chinlik jadvalidir. Ammo predikatlar mantiqida bu holat batamom o‘zgaradi. Predikatlar m antiqida ixtiyoriy formulaning umumqiymatli yoki umumqiymatli emasligi haqidagi masalani yechadigan samarali usul mavjud emas. Shuning uchun ham predikat va u bilan bog‘liq kvantor tushunchalaridan foydalanadigan matematik nazariyalarda aksiom atik usullardan foydalanish zarur bo‘lib qoladi.

Mulohazalar algebrasi va mulohazalar hisobida formulaning tavtalogiya bo'lishi yoki bo’lmasligini aniqlashning samarali usullaridan biri chinlik jadvalidir. Ammo predikatlar m antiqida bu holat batamom o‘zgaradi. Predikatlar m antiqida ixtiyoriy formulaning umumqiymatli yoki umum qiymatli emasligi haqidagi masalani yechadigan samarali usul mavjud emas. Shuning uchun ham predikat va u bilan bog‘liq kvantor tushunchalaridan foydalanadigan matematik nazariyalarda aksiom atik usullardan foydalanish zarur bo‘lib qoladi. Matematik mantiqning boshlang‘ich tushunchalaridan biri mulohaza tushunchasidir. “Mulohaza” deganda biz rost yoki yolg‘onligi haqida fikr yuritishi mumkin bo‘lgan darak gapni tushunamiz. Har qanday mulohaza yo rost yoki yolg‘on bo‘ladi. Hech bir mulohaza bir vaqtning o‘zida ham rost ham yolg‘on bo‘la olmaydi. Insonlar kundalik hayotda o’zaro muloqot qilish uchun turli mulohazalardan foydalanishadi.

4. 
   FOYDALANGAN ADABIYOTLAR
   

1. 
   H.T. To’rayev, I. Azizov Matematik mantiq va diskret matematika. 1,2 jild. ―Tafakkur-Bo’stoni, Toshkent, 2011y.
   
2. 
   Qasimov N.X., Dadajonov R.N., Ibragimov F.N. Diskret Matematika va matematik mantiq asoslari (o’quv qo’llanma), T., O’zbekiston Milliy universiteti, 2016.
   
3. 
   To’xtasinov M., Diskret matematika va matematik mantik.- T., Universitet, 2005.
   
4. 
   To’rayev X.T., Matematik mantiq va diskret matematika.- T., O’qituvchi, 2003.
   
5. 
   Yunusov A.S. Matematik mantiq va algoritmlar nazariyasi elementlari, T., 2003.
   

INTERNET RESURSLAR:

1. www.ziyo-net.uz

2. http://dimacs.rutgers.edu/

3. http://epubs.siam.org/sam-bin/dbq/toclist/SIDMA

4. http://www.vsppub.com/journals/jn-DisMatApp.html

5. http://www.uni-bonn.de/logic/world.html

6. http://www.math.uni-bonn.de/people/logic/

7. http://www.math.uu.se/logik/logic-server/