Mavzu: Mulohazalar hisobining keltirib chiqariluvchi formulalari bilan mulohazalar algebrasining umumqiymatli formulalar orasidagi bog’lanish. Reja: 1. Mulohazalar hisobi. 2. Keltirib chiqariluvchi formulalar. 3. Mulohazalar algebrasi. 4 Mulohazalar hisobi formulalari bilan mulohazalar algebrasi formulalari orasidagi bog’lanish. 1. MULOHAZALAR HISOBI. Mulohazalar hisobi (MH) aksiomatik nazariya bo'lib, mulohaza tushunchasiga hech qanday mazmun berilmaydi. Mulohazalarni odatdagidek lotin alifbosining bosh harflari bilan belgilaymiz. Mulohazalarga qo‘yiladigan talab bitta, u ham bo‘lsa, mulohazalar hisobining aksiomalarini qanoatlantirishi kerak. Mulohazalar algebrasini mulohazalar hisobining interpretatsiyalaridan biri sifatida qarash mumkin. Mulohazalar hisobida formula tushunchasi Mulohazalar hisobini qurish uchun avval uning alfaviti, ya’ni MHda ishlatiladigan belgilar sanab chiqiladi, so‘ngra shu belgilarning ketma-ketligidan tuzilgan so‘z - formula tushunchasi va nihoyat, keltirib chiqariluvchi formulalar ta’riflanadi. MHning alfaviti uchta tur belgilardan iborat: 1. A, B, C,..., X, Y, Z,... - o‘zgaruvchi mulohazalar. 2. ˥,&,˅,⇒ - mantiqiy bog‘lovchilar. 3. (,) - chap va o‘ng qavslar. MHda boshqa belgilar yo‘q. 1. Ta’rif. 1. A,B,C, ...,X,Y,Z, ... lar formuladir. 2. Agar A va B lar formulalar bo‘lsa, u holda (˥A), (A&B), (A v B), (A⇒B) -lar ham formuladir. 3. Boshqa usulda formula hosil qilib bo'lmaydi. O‘zgaruvchi mulohazalarni elementar formulalar deb ataymiz. Mulohazalar hisobida formulaosti tushunchasi mulohazalar algebrasidagidek kiritiladi. Qavslarni tashlab yuborish tartibi ham mulohazalar algebrasidagidek. Shu sababli, bular ustida to‘xtalib o‘tmaymiz. 2. KELTIRIB CHIQARILUVCHI FORMULALAR. Mulohazalar hisobini qurishning keyingi bosqichi isbotlanuvchi formulalarni ajratib olishdan iborat. Avval aksiomalarni bayon qilamiz, keyin aksiomalardan keltirib chiqariluvchi, ya’ni isbotlanuvchi formulalarni keltirib chiqarish qoidalarini beramiz. 2.1. Mulohazalar hisobining aksiomalari Mulohazalar hisobining aksiomalari 4 ta guruhga bo‘1ingan ro‘yxatdagi 11 aksiomadan iborat. I guruh aksiomalari: I1 A⇒(B⇒A). I2. (A⇒(B⇒C))⇒((A⇒B)⇒(A⇒C)). II guruh aksiomalari: II1. A&B⇒A. II2. A&B⇒B. II3. (A⇒B)⇒((A⇒C)⇒(A⇒B&C)). III guruh aksiomalari: III1. A⇒A˅B. III2. B⇒A˅B. III3. (A⇒C)⇒((B⇒C)⇒(A˅B⇒C)). IV guruh aksiomalari: IV1. (A⇒B) ⇒ (˥B⇒˥A). IV2. A⇒˥˥A. IV3. ˥˥A⇒A. 2.2. Keltirib chiqarish qoidalari 1. O’rniga qo’yish qoidasi. MHning tarkibida A o’zgaruvchi mulohaza qatnashgan À(A) hamda ixtiyoriy B formulalari berilgan bo’lsin. Agar À(A) mulohazalar hisobining keltirib chiqariluvchi (k.ch.) formulasi bo’lsa, u holda À(B) formula ham mulohazalar hisobining keltirib chiqariluvchi formulasi bo’ladi. Bu qoida qisqacha sxematik ravishda À(A) À(B) ko‘rinishda belgilanadi. 2. Xulosa chiqarish (Modus ponens-MP) qoidasi. Agar A⇒B va A formulalar MHning keltirib chiqariluvchi formulalari bo’lsa, u holda B formula ham MHning keltirib chiqariluvchi formulasidir. Bu qoida qisqacha quyidagi ko’rinishda belgilanadi: A,A⇒B B 2.3-ta’rif. 1°. Har bir aksioma mulohazalar hisobining keltirib chiqariluvchi formulasidir. 2°. Mulohazalar hisobining keltirib chiqariluvchi formulasiga o‘rniga qo‘yish qoidasini qo‘llash natijasida hosil qilingan formula mulohazalar hisobining keltirib chiqariluvchi formulasidir. 3°. Mulohazalar hisobining keltirib chiqariluvchi formulalariga xulosa chiqarish qoidasini qo‘llash natijasida hosil qilingan formula mulohazalar hisobining keltirib chiqariluvchi formulasidir. 4°. Mulohazalar hisobining boshqa keltirib chiqariluvchi formulalari yo‘q. 2.4-ta’rif. Agar formulalarning chekli ketma-ketligi A1 ,A2,..., An da har bir Ai (i=L,n) formula yo mulohazalar hisobining keltirib chiqariluvchi formulasi, yo o’zidan oldingi formulalardan o’rniga qo’yish yoki xulosa chiqarish qoidalari yordamida hosil qilingan formulalar bo’lsa, u holda bu ketma-ketlik oxirgi An formulaning formal isboti, n esa isbotning uzunligi deyiladi. Mulohazalar hisobining aksiomalari isbotining uzunligi 1 ga teng isbotlanuvchi formulalar sifatida qaralishi mumkin. Mulohazalar hisobining isbot uzunligi birdan katta bo‘lgan isbotlanuvchi formulalarini teoremalar deb ataymiz. «À formula mulohazalar hisobining keltirib chiqariluvchi formulasi» degan jumlani qisqacha |—À belgi orqali ifodalaymiz. 2.5-teorema. |—A⇒A. Isbot. Quyidagi ketma-ketlikni qaraylik: 1. A⇒(B⇒A). 2. (A⇒(B⇒A))⇒((A⇒B)⇒(A⇒A)). 3. (A⇒B)⇒(A⇒A). 4. (A⇒(B⇒A))⇒(A⇒A). 5. A⇒A. 6. A⇒A. Bu ketma-ketlik A⇒A formulaning formal isboti ekanligini ko‘rish qiyin emas. Haqiqatan ham, A⇒(B⇒A) formula I1 aksioma; (A⇒(B⇒A))⇒((A⇒B)⇒(A⇒A)) formula I2 aksiomadagi C ni A bilan almashtirish natijasida hosil qilingan; (A⇒B)⇒(A⇒A) formula 2-formulaga MP qoidasini qo‘llash natijasida hosil qilingan; (A⇒(B⇒A))⇒(A⇒A) formula o‘zidan oldingi formulada B ni B⇒A formula bilan almashtirish natijasida hosil qilingan; A⇒A formula 4-formulaga MP qoidasini qo’llash natijasida hosil qilingan; A⇒A formula A ni A bilan almashtirish natijasida hosil qilingan. Bundan keyin mulohazalar hisobining keltirib chıqariluvchi formulasini Ɽ xarfi, ˥Ɽ ni Ӻ harfi bilan belgilab olamiz. 2.6-teorema. À mulohazalar hisobining ixtiyoriy formulasi bo’lsin. U holda À⇒Ɽ mulohazalar hisobining keltirib chiqariluvchi formulasi bo’ladi, ya’ni |—À⇒Ɽ. Isbot. 1. A⇒(B⇒A). 2. Ɽ⇒(B⇒Ɽ). 3. B⇒Ɽ. 4. À⇒Ɽ. Bu ketma-ketlik teoremaning formal isbotidir. Haqiqatdan ham, l-formula I1 aksioma. 2-formula 1-formuladan A ni Ɽ bilan almashtirish natijasida hosil qilingan. 3-formula 2-formuladan MP qoida yordamida hosil qilingan. 4-formula esa 3-formulada B ni À formula bilan almashtirish natijasida hosil qilingan. 2.7-teorema. |—Ӻ⇒˥˥A. Isbot. 1. (A⇒B)⇒(˥B⇒˥A). 2. (˥A⇒B)⇒(˥B⇒˥˥A). 3. (˥A⇒Ɽ)⇒(˥Ɽ⇒˥˥A). 4. ˥Ɽ⇒˥˥A. 5. Ӻ⇒˥˥A. 3. MULOHAZALAR ALGEBRASI. Mulohazalar algebrasi tushunchasini kiritish uchun avval algebra tushunchasini eslatib o‘tamiz. A≠Ø to‘plam va ΩA to‘plamda aniqlangan algebraik amallar to‘plami beri1gan bo‘lsin. U holda (A,Ω)- juftlikni algebra deb ataymiz. 2.1-ta’rif. <Ḿ{˥,˄,˅,⇒,⇔}> algebra mulohazalar algebrasi deyiladi. Mulohazalar algebrasini qisqacha MA deb belgilaymiz. MAning alifbosi quyidagilardan iborat: A, B, C,... - mulohazalarni belgilash uchun ishlatiladigan harflar; ˥,˄,˅,⇒,⇔ - mantiq amallarini belgilash uchun ishlatiladigan belgilar; (,) - chap va o‘ng qavslar. Mulohazalar algebrasining asosiy tushunchalaridan biri formula tushunchasidir. Unga induktiv ta’rif beramiz. 2.2-ta’rif. 1) Har bir A,B,C,...harflar formuladir. 2) Agar À va Ɓ lar formulalar bo‘lsa, u holda (˥À), (À˄Ɓ), (À˅Ɓ), (À⇒Ɓ), (À⇔Ɓ) lar ham formulalardir. 3) 1) va 2) lar yordamida hosil qilingan ifodalargina formulalardir. Masalan, A,B,C lar 1) ga asosan formulalar; (˥B), (A⇒(˥B)), (((A⇒(˥B))⇒A)˄C) lar 2) ga asosan formulalardir. Formulalarning tarkibidagi qavslarni kamaytirish maqsadida mantiq amallarining bajarilish tartibini ˥,˄,˅,⇒,⇔ deb belgilab olamiz. Demak, qavslar bo‘lmaganda avval ˥ keyin ˄ va h.k. amallar bajariladi. Bundan tashqari, tashqi qavslarni ham ehtiyoj bo’lmaganda tashlab yuboramiz. Bunday o‘zgartirishlardan keyin ((A˄B)˅((˥A)⇒C)) formulani A˄B˅(˥A⇒C) ko‘rinishda yozishimiz mumkin bo‘ladi. 2.3-ta’rif. Formulada qatnashgan mantiq amallari soni formulaning rangi deyiladi. Yuqorida keltirilgan formulaning rangi 4 ga teng. 2.4-ra’rif. 1. À formula A dan iborat bo’Isa, uning formulaosti faqat uning o‘zidan iborat. 2. Agar formulaning ko‘rinishi À*Ɓ dan iborat bo‘lsa, u holda uning formulaostilari À,Ɓ,À*Ɓ hamda À va Ɓ larning barcha formulaostilaridan iborat bo‘ladi. Bu yerda *,-,˄,˅,⇒,⇔ amallaridan biri. 3. Agar formulaning ko’rinishi ˥À bo‘lsa, uning formulaostilari À formula, À formulaning barcha formulaostilari, ˥À ning o‘zidan iborat. 4. Boshqa formulaostilari yo‘q. 2.5-misol. (A˄B)⇒˥A formulaning formulaostilari ta’rifga ko‘ra quyidagilardan iborat: A, B, ˥A, A˄B, (A˄B)⇒˥A. Agar À formula tarkibiga faqat A1, A2,…,An mulohazalar kirgan bo’lsa, bu mulohazalarni propozitsional o’zgaruvchilar deb ataymiz va formulani ehtiyoj bo’lganda À (A1, A2,…,An)ko’rinishda yozamiz. Koordinatalari 0 yoki 1 lardan iborat (i1,i2,…,in) vektor, bu yerda ik lar 0 yoki 1 lardan iborat, propozitsional o’zgaruvchilarning qiymatlari tizimi deyiladi. A1, A2,…,An propozitsional o‘zgaruvchilarning barcha qiymatlari tizimi 2ⁿ ta ekanligini ko‘rish qiyin emas. Demak, agar mulohazalar algebrasining biror À formulasi tarkibiga n ta mulohaza kirgan bo‘lsa, bu formulaning rostlik jadvalida 2ⁿ ta qiymatlar tizimi qatnashar ekan. 2.6-misol. A˄B⇒˥A˅C formulaning rostlik jadvalini tuzing. ABC˥AA˄B˥A˅CA˄B⇒˥A˅C11101111100100101001110000010111011010101100110110001011 4. MULOHAZALAR HISOBI FORMULALARI BILAN MULOHAZALAR ALGEBRASI FORMULALARI ORASIDAGI BOG’LANISH. Mulohazalar hisobining formulalaridagi har bir o‘zgaruvchi mulohazaga mazmun bersak, ya’ni o‘zgaruvchi mulohaza yo 0, yo 1 qiymatni qabul qiladi deb qarasak, mulohazalar algebrasining formulasini hosil qilamiz. 8.1-teorema. Mulohazalar hisobining har bir keltirib chiqariluvchi formulasi, agar mulohazalar algebrasining formulasi sifatida qaralsa, mulohazalar algebrasining aynan rost formulasi bo’ladi. Isbot. Haqiqatdan ham, mulohazalar hisobining har bir aksiomasini mulohazalar algebrasining formulasi sifatida qarasak, u holda bu formula aynan rost formula bo‘lishini ko‘rish qiyin emas. Buning uchun, har bir aksioma uchun rostlik jadvalini tuzish yetarli. Masalan, I. A⇒ (B⇒A) aksioma uchun rostlik jadvalini tuzaylik: ABB⇒AA⇒(B⇒A)1111101101010011 Shunday qilib, har bir aksiomani aynan rost formula deb hisoblaymiz. Aynan rost formulalarga mulohazalar hisobining keltirib chiqarish qoidalarini qo‘llasak, yana aynan rost formulalar hosil bo‘1adi. À (B) – aynan rost formula bo‘lsin, u holda B qanday qiymat qabul qilishidan qat’iy nazar, À (B) = 1 bo‘ladi. Demak, À (B) – 1. À, À⇒Ɓ formulalar aynan rost formulalar bo‘lsalar, implikatsiya amalining ta’rifidan Ɓ ham aynan rost formula ekanligi kelib chiqadi. Foydalanilgan adabiyotlar ro’yxati 1. A.S.Yunusov. Matematik mantiq va algoritmlar nazariyasi elementlari (2006-yil) 2. library.samdukf.uz