MAVZU: MULOHAZALAR ALGEBRASI FORMULALARI VA MULOHAZALAR HISOBI FORMULALARI ORASIDAGI MUNOSABATLAR REJA: Mulohazalar. Mulohazalar ustida mantiqiy amallar. Teng kuchli formulalar va asosiy teng kuchliliklarFormulaning normal shakllari. Mulohazalar. Mulohazalar ustida mantiqiy amallar. Har qanday matematik nazariya u yoki bu matematik jumlaning rost yoki yolg’onligini o’rganadi. Ta’rif: Rost yoki yolg’onligi bir qiymatli aniqlangan darak gapga jumla (mulohaza) deyiladi. Ta’rifga ko’ra “0<1”, “2*5=10”, “7 – juft son”, “1 – tub son” gaplar mulohaza bo’lib, ulardan birinchisi va ikkinchisi rost, uchinchisi va to’rtinchisi yolg’on mulohazalardir. Mulohazalar nazariyasining boshlang’ich ob’yektlari sodda (oddiy) mulohazalardan iborat. Sodda mulohazalar lotin alifbosining katta harflari A, B, C, …. yoki kichik harflari a, b, c,.... orqali belgilanadi. Mulohazalarning rost yoki yolg’onligi ularning mazmuniga qarab aniqlanadi. Rost mulohazalarning qiymati 1, yolg’onligi mulohazalarning qiymati 0 orqali belgilanadi. Mulohaza bir vaqtning o’zida ham rost, ham yolg’on bo’la olmaydi. Matematikada har bir teorema mulohaza hisoblanadi. Sodda mulohazalardan bog’lovchi yoki bog’lovchi so’zlar orqali murakkab mulohazalar hosil qilinadi. “emas”, “va”, “yoki”, “... kelib chiqadi”, “zarur va yetarli” kabi bog’lovchi so’zlarga bittadan mantiqiy amal mos keladi. Mulohazalar ustida bajariladigan inkor, kon’yuksiya, dizyunksiya, implikatsiya, ekvivalensiya amallari mavjud. 1. Inkor amali. Ta’rif: p mulohazaning inkori deb p rost bo’lganda yolg’on, p yolg’on bo’lganda rost bo’ladigan mulohazaga aytiladi. Inkor amaliga “emas” bog’lovchisi mos keladi. p mulohazaning inkorini yoki ┐p ko’rinishlarda belgilanadi. Masalan, p: “5-juft son” bo’lsa, u holda ┐p: “5-juft son emas” bo’ladi. Bu yerda p mulohaza yolg’on bo’lib, ┐p mulohaza rost bo’ladi. p mulohazaning inkorining inkori yana p mulohazaning o’zi, ya’ni ┐(┐p)= ┐┐p= p bo’ladi. Buni ikki karrali inkor deb yuritiladi. Inkor amaliga quyidagi rostlik jadvali mos keladi: p┐p1001 2. Konyuksiya amali. Ta’rif: p va q mulohazalarning konyuksiyasi deb p va q mulohazalar rost bo’lganda rost, boshqa hollarda yolg’on bo’lgan yangi mulohazaga aytiladi va uni yoki ko’rinishlarda belgilanadi. Konyuksiya amaliga “va” bog’lovchisi mos keladi. Masalan, p: “5-tub son”, q: “5-toq son”, : “5-tub va toq son”. Konyuksiya amaliga quyidagi rostlik jadvali mos keladi: pq111100010000 Mulohazalarning konyuksiyasi ikkitadan ortiq mulohazalar uchun ham o’rinli bo’ladi. p1, p2, p3,…,pn mulohazalarning barchasi rost bo’lsa, u holda yolg’on bo’ladi. 3. Dizyunksiya amali. Ta’rif: p va q mulohazalarning dizyunksiyasi deb p va q mulohazalarning kamida bittasi rost bo’lganda rost, boshqa hollarda yolg’on bo’lgan yangi mulohazaga aytiladi va u orqali belgilanadi. Dizyunksiya amaliga “yoki” bog’lovchisi mos keladi. Masalan, p: “3<4” - rost, q: “3=4” - yolg’on, : “” - rost. Dizyunktsiya amaliga quyidagi rostlik jadvali mos keladi: pqpq111101011000 Mulohazalarning diz’yunktsiyasi ikkitadan ham ortiq mulohazalar uchun ham o’rinli bo’ladi. p1,p2,…,pn mulohazalarning diz’yunktsiyasi orqali belgilaylik. p1,p2,…,pn larning kamida bittasi rost bo’lsa, rost, p1,p2,…,pn larning barchasi yolg’on bo’lsa yolg’on bo’ladi. 4. Implikatsiya amali. Ta’rif: p va q mulohazalarning implikatsiyasi deb p rost, q yolg’on bo’lganda yolg’on, boshqa hollarda rost bo’lgan yangi mulohazaga aytiladi va uni p=>q ko’rinishda belgilanadi. Implikatsiya amaliga “agar …, bo’lsa, u holda, … bo’ladi” kabi bog’lovchi so’zlar mos keladi. Masalan, p: ”5*5=25” – rost, q: ”6*6=36” - rost, p=>q: ”Agar 5*5=25 bo’lsa, u holda 6*6=36” bo’ladi – rost. p=>q implikatsiya quyidagicha o’qiladi: “p dan q kelib chiqadi”, “p bo’lishi uchun q ning bo’lishi zarur”, “p mulohaza q mulohaza uchun etarli”. Implikatsiya amaliga quyidagi rostlik jadvali mos keladi: pqp=>q111100011001 5. Ekvivalensiya amali. Ta’rif: p va q mulohazalarning ekvivalensiyasi deb p va q larning bir xil qiymatlarida rost, turli qiymatlarida yolg’on bo’lgan yangi mulohazaga aytiladi va uni ó ko’rinishda belgilanadi. Ekvivalensiya amaliga “Agar … bo’lsa, shu holda va faqat shu holda ... bo’ladi”, “...bajarilishi uchun ... bajarilishi zarur va etarli” kabi bog’lovchi so’zlar mos keladi. Masalan, p: “berilgan natural son 3 ga bo’linadi”, q: “berilgan sonning raqamlar yig’indisi 3 ga bo’linadi”. póq: “Berilgan sonning 3 ga bo’linishi uchun uning raqamlari yig’indisi 3 ga bo’linishi zarur va yetarli”. Ekvivalensiya amaliga quyidagi rostlik jadvali mos keladi: pqpóq111100010001Har bir qaralayotgan mulohazaga rostlik ustunidan bitta ustun mos keladi. Bu ustunni qiymatlar ustuni deb yuritamiz. Ta’rif: Qiymatlari ustuni teng bo’lgan mulohazalar o’zaro teng kuchli mulohazalar deyiladi. Masalan: p=>q va ┐q=>┐ p mulohazalarning teng kuchliligini quyidagi rostlik jadvali orqali ko’rsataylik: pq┐p┐qp=>q┐q=>┐p110011100100011011001111p=>q va ┐q=>┐p mulohazalarning ustuni bir xil bo’lgani uchun p=>q=┐q=>┐p bo’ladi. Ta’rif: universial algebra mulohazalar algebrasi deb yuritiladi. Tarif: 1. p, q, r,... lar mulohazalar algebrasining formulalaridir. 2. Agar p va q lar mulohazalar algebrasining formulalari bo’lsa, u holda ┐p, pq, pq, p=>q, póq ham formula bo’ladi. 3. Mulohazalar algebrasidagi formulalar faqat 1-va 2-formulalar yordamida tuziladi. Ko’p hollarda 2. yordamida aniqlangan formulalar murakkab formulalar deb yuritiladi. Murakkab formulaga argumentlari rost yoki yolg’on qiymatni qabul qiluvchi funktsiya deb qarash mumkin. Ta’rif: xi, argumentlarning har bir qabul qilishi mumkin bo’lgan barcha 1 va 0 qiymatlar tizimida A(x1, x2,…,xn) formulani ifodalovchi mantiqiy funktsiya rost (yolg’on) qiymatga erishsa, u holda bu formula aynan rost (yolg’on) formula deyiladi. Misol: AB111110110 010011 Agar A(x1, x2, …, xn) formulada n ta elementar mulohaza bo’lsa, u holda bu formulaning rostlik jadvali 2n ta satr (yo’l) dan iborat bo’ladi. Teng kuchli formulalar va asosiy teng kuchliliklar Ta’rif: Tarkibidagi xi(i=) o’zgaruvchilarning mumkin bo’lgan barcha qiymatlar tizimida A(x1, x2, …, xn) va B(x1, x2, …, xn) formulalarning qiymatlari ustuni bir xil bo’lsa, u holda bu formulalar o’zaro teng kuchli formulalar deyiladi va uni A(x1, x2, …, xn)≡B(x1, x2, …, xn) ko’rinishda belgilanadi. Misol: ABC1110111111001100101000001000000001111111010111000011111100011100Agar va formulalar teng kuchli bo’lsalar, u holda va lar aynan rost formulalar bo’lishi ravshandir. Aksincha, qandaydir va (bir xil propozitsional o’zgaruvchilarga ega bo’lgan) formulalar uchun va lar aynan rost furmulalar bo’lsa, u holda bo’ladi. va formulalar teng kuhli formulalar ekanini ko’rsataylik: AB111111100100011000001111Shunday qilib, bu tengkuchliliklarnda ko’rinadiki, bo’lishi uchun formula aynan rost formula bo’lishi zarur va yetarlidir. Teng kuchli bo’lish munosabati ekvivalent binary munosabat ekanligi ravshandir, ya’ni bu munosabat –refleksivlik.Agar bo’lsa, u holda bo’ladi ­– simmetriklik va Agar va bo’lsa, u holda bo’ladi – tanzitivlik xossalariga egadir.Teorema: – jumlalar algebrasining ixtiyoriy formulasi, uning qism formulasi bo’lsin. agar bo’lsa, u holda bo’ladi. Isboti: bo’lgani uchun va formulalar ularda qatnashgan propozitsional o’zgaruvchilar qiymatlarining barcha naborlarida bir xil qiymatlarga erishadilar. va formulalarning qiymatlari yoki bo’lgani uchun yo , yoki hosil bo’ladi. Bu esa ekanini ko’rsatadi. Teorema: , lar va formulalarning har birida qatnashgan barcha propozitsional o’zgaruvchilar, lar esa ixtiyoriy formulalar bo’lsin. U holda bo’ladi; bunda har bir propozitsional o’zgaruvchi berilgan tengkuchlilikda necha joyda qatnashgan bo’lsa, shuncha joyda mos formula bilan almashtiriladi. Isbot. tengkuchlilikda qatnashgan har bir propozitisional o’zgaruvchi 1 yoki 0 qiymat qabul qiladi. formula ham o’zida qatnashgan propozitsional o’zgaruvchilar qiymatlarining barcha naborlarida 1 yoki 0 qiymat qabul qiladi. formula tarkibida qatnashgan propozitsional o’zgaruvchilar bo’lsin. bu propozitsional o’zgaruvchilar qiymatlari naborlaridan biri va formulalarning nabordagi qiymatlari nabori bo’lsin. uzunligi bo’lgan nabor propozitsional o’zgaruvchilar qabul qiladigan qiymatlar naborlari srasida mavjuddir. va formulalar ta naborning har birida bir xil qiymatga ega bo’lgani uchun ular naborda ham bir xil qiymat qabul qiladilar. Yuqorida isbotlangan teoremalardan bevosita quyidagi natijlaar kelib chiqadi. Agar va bo’lsa, u holda 1) 2) 3) 4) 5) Ta’rif: Agar formulaning tarkibida faqat konyuksiya, dizyunksiya va inkor operatsiyalari qatnashgan bo’lib, inkor speratsiyasi propozitsional o’zgaruvchilargagina tegishli bo’lsa, u holda bunday formula keltirilgan formula deyiladi. Misol: keltirilgan formuladir, ammo keltirilgan formula emas, chunki bu formulada implikatsiya operatsiyasi qatnashishi bilan birgalikda inkor operatsiyasi murakkab formula ga tegishlidir. 3.3-Teorema: Mulohazalar algebrasining har bir formulasining yo o’zi keltirilgandir yoki uni teng kuchli keltirilgan formula bilan almashtirish mumkin. Bu teoremani isbotlash uchun mulohazalar algebrasining asosiy tengkuchliliklari bilan tanishib chiqamiz. Mulohazalar algebrasining tengkuchliliklari quyidagilar: (qo’sh inkor tengkuchliligi) (dizyunksiya kommuntativligi) (konyuksiyaning kommuntativligi) (dizyunksiya assotsiativligi) (konyunksiyaning assotsiativligi) (dizyunksiyaning konyuksiyaga nisbatan distributivligi) (konyuksiyaning dizyunksiyaga nisbatan distributivligi) (dizyunksiya idempotentligi) (konyuksiyaning idempotentligi) (yutilish tengkuchliligi) (yutilish tengkuchliligi) (de Morgan tengkuchliligi) (de Morgan tengkuchliligi) (uchinchini inkor etish tengkuchliligi) (qarama-qarshilik tengkuchliligi)a) , b) c) d) (kontrapozitsiya tengkuchliligi)Bu teng kuchliliklar o’rinli ekanligini rostlik jadvali yordamida bevosita tekshirib ko’rish mumkin. Masalan, XIII tengkuchlilik uchun rostlik jadvalini ko’raylik: AB1100100100101101100110011011II–XI, XIV–XVI tengkuchliliklarni tashkil etuvchi formulalar keltirilgan formulalar ekanligi ravshandir. Bundan tashqari, (1) tengkuchlilik o’rinli ekanligini rostlik jadvali tuzib ko’rsatish qiyin emas. Yuqorida ekanligi ko’rsatilgan edi. Implikatsiyaning inkor va dizyunksiya bilan almashtirish mumkin ekanligidan quyidagi tengkuchlilikni hosil qilamiz: (2) Demak, va formulalar keltirilgan formulalar bilan almashtirilishi mumkin ekan. I, XII, XIII tengkuchliliklar qo’sh inkor hamda dizyunksiya va konyuksiyalar inkorlarini qanday keltirilgan formulalar bilan almashtirish mumkin ekanini ko’rsatadi. Endi 3.3-teoremaning isbotini keltiramiz. Agar formulaning o’zi keltirilgan formula bo’lsa, u holda teorema isbotlangan bo’ladi. Agar formula tarkibida implikatsiya va ekvivalentsiya operatsiyalari qatnashgan bo’lsa, ularni (1) va (2) tengkuchliliklar yordamida almashtirish mumkin; formula tarkibida ko’rinishdagi qism formula qatnashgan bo’lsa, uni bilan, yoki ko’rinishidagi qism formula qatnashgan bo’lsa, ularni mos ravishda va formulalar bilan almashtirish mumkin. Bu protsessni yetarli marta tarkrorlab, nihoyat formulaga teng kuchli bo’lgan keltirilgan formulaga kelamiz. Shunday qilib, 3.3-teoremaga asosan mulohazalar algebrasining har bir formulasini asosiy va boshqa tengkuchliliklar yordamida almashtirib unga teng kuchli formulalar hosil qilish mumkin. Bu shakl alashtirishlar ba’zi bir masalalarni yechishda keng ko’lamda ishlatiladi. Bu yerda formulalarni shakl almashtirsihga oid ba’zi namunalarni keltiramiz. 3.3-misol. formulaning shaklini almashtiring va soddalashtiring. (1) ga asosanXIII va XII ga asosanXII va XII ga asosan1 ga asosanVII ga asosanXIV va II ga asosanXVI ga asosanVII ga asosanXIV ga asosanXVI va II ga asosanXIV va XVI ga asosanDemak, berilgan formula aynan teng formula ekan. “Sheffer shtrixi” va “Pirs strelkasi” operatsiyalariga qaytamiz. Logik operatsiyalarning jadval formularini taqqoslasak: , ekanligini ko’ramiz. Demak, “Sheffer shtrixi” va “Pirs strelkasi” inkor va mos ravishda konyuksiya va dizyunksiya orqali ifoda qilinar ekan.