1. Formulalar. Teng kuchli formulalar. Aynan chin, aynan yolg‘on va bajariluvchi formulalar

Mavzu: Teng kuchlimas formulalar soni. Formulaning chinlik to’plami
Reja:
1. Formulalar. Teng kuchli formulalar.
2. Aynan chin, aynan yolg‘on va bajariluvchi formulalar.
3. Asosiy tengkuchliliklar. Teng kuchli formulalarga doir teoremalar
4 Teng kuchlimas formulalar soni
5 Fo’rmulalarning chinlik to’plami

Formula va teng kuchlilik tushunchalari
Oldingi paragrafda asosan mantiqiy amallar o‘rganildi. Endi mantiqiy amallar orasidagi bog‘lanishlar bilan shug‘ullanamiz. Bunday bog‘lanishlardan biri bilan tanishmiz: ekvivalensiya ikki tomonli implikatsiyadir, aniqrog‘i, berilgan x va y mulohazalarning x  y ekvivalensiyasi ikkita x  y va y  x implikatsiyalarning (x  y)  ( y  x) kon’yunksiyasi shaklida ifodalanadi.
Dastlab mulohazalar algebrasining formula tushunchasiga murojaat qilib, intiutiv ravishda, uni berilgan elementar mulohazalardan inkor, diz’yunksiya, kon’yunksiya, implikasiya, ekvivalensiya mantiqiy amallarining chekli kombinatsiyasi va, zarur bo‘lganda, mulohazalar ustida mantiqiy amallarning bajarilish tartibini ko‘rsatuvchi qavslar vositasida hosil qilingan murakkab mulohaza deb tushunamiz. Bu yerda qavslarni ishlatish qoidalari sonlar bilan ish ko‘ruvchi (oddiy) algebradagidek saqlanadi.
1- m i s o l . Ushbu x , ch , yo  (yo  y) , x  y  x , 1 2 3 1 4 [x (x x )x ]x , y  x , (x  y)  ( y  z)  (z  x), [ ( )] ( ) yo x1 x3 x3  x4 x2  va (x  y)  (x  y) ko‘rinishda yozilgan murakkab mulohazalarning har biri formuladir, lekin 1 2 3 1 [x (x x )]x va (x  y)  (z  (z  y) yozuvlarni formula sifatida qabul qilish mumkin emas, chunki ularning birinchisida kon’yunksiya belgisidan keyin yopuvchi “]” qavs yozilgan, ikkinchisida esa ikkinchi ochuvchi “(“ qavsga mos yopuvchi “)” qavs yozilmagan. ■
Formula tushunchasiga matematik induksiya usuliga tayangan holda quyidagicha qat’iy ta’rif beriladi.
1- t a ’ r i f. 1) Agar x elementar mulohaza bo‘lsa, u holda x formuladir;
2) agar A formula bo‘lsa, u holda A formuladir;
3) agar A va B formulalar bo‘lsa, u holda (A B) , (A B) , (A  B) va (A  B) formulalardir;
4) 1-, 2- va 3- bandlardagidan tashqari boshqa formula yo‘q.
1- ta’rifga ko‘ra ixtiyoriy formulaga, uning qiymati sifatida, vaziyatga qarab, {ch, yo} to‘plamning biror elementi mos qo‘yiladi. Formula tarkibidagi o‘zgarmas va o‘zgaruvchi (elementar) mulohazalarning har biri elementar formulalar deb hisoblanadi. Formula qiymatining n x , x ,..., x 1 2 o‘zgaruvchilarga (elementar mulohazalarga) bog‘liqligini ta’kilash kerak bo‘lgan holda ( , ,..., ) 1 2 n f x x x ko‘rinishdagi yozuvdan foydalaniladi.
Tabiiyki, formula tushunchasiga berilgan 1- ta’rif asosida ish yuritilsa, tuzilgan formula tarkibida qavslar ko’p bo‘ladi. Matematik mantiqda formula tarkibidagi qavslar sonini kamaytirish maqsadida, odatda, quyidagi kelishuvlardan foydalaniladi.
1) biror formula inkor ishorasi ostida bo‘lsa, u qavssiz yoziladi (masalan, (x  y)  z formulani x  y  z ko‘rinishda yozish mumkin).
2) kon’yunksiya amali diz’yunksiya, implikatsiya va ekvivalensiya amallariga nisbatan formulalarni mustahkamroq bog‘laydi deb hisoblanadi (masalan, x  (yz) formulani x  yz , xy  (yz) formulani xy  yz , (xy)  (zu) formulani esa xy  zu ko‘rinishda yozish mumkin).
3) diz’yunksiya amali implikatsiya va ekvivalensiya amallariga nisbatan formulalarni mustahkamroq bog‘laydi deb hisoblanadi (masalan, x  ( y  z) formulani x  y  z, x  y  (z  y) formulani esa x  y  z  y ko‘rinishda yozish mumkin).
4) implikatsiya amali ekvivalensiya amaliga nisbatan formulalarni mustahkamroq bog‘laydi deb hisoblanadi (masalan, x  ( y  z) formulani x  y  z ko‘rinishda yozish mumkin).
Bu kelishuvlar, yuqorida ta’kidlanganidek, formulalar tarkibidagi qavslar sonini kamaytirish imkonini beradi. Masalan, (((x  y)  (x  z))  (((x  y) (x  y)) (x  z))) formulani (x  y)  xz  xy  xy  (x  z) ko‘rinishda yozish mumkin.
Umuman olganda, matematik mantiqda mantiqiy amallarni bajarish imtiyozlari va qavslar haqidagi kelishuv deb ataluvchi qoidalar qabul qilingan.
Qavslarsiz yozilgan mantiqiy amallarni bajarish imtiyozlari (ketma-ketligi) navbat bilan inkor (  ), kon’yunksiya (  ), diz’yunksiya (  ), implikatsiya () amallariga berilgan, eng so‘nggi imtiyozga esa ekvivalensiya ( ) amali egadir.
Qavslar haqidagi kelishuv deganda quyidagi qoidalarga amal qilish nazarda tutiladi:
1. Agar formulada tashqi qavslar yozilmagan bo’lsa, u holda ular o‘z joylariga tiklanadi.
2. Agar formulada ikkita bir xil imtiyozga ega mantiqiy amallar qavslarsiz ketma-ket yozilgan bo‘lsa, u holda yozilish tartibiga ko‘ra chapda joylashgan amal uchun qavslar o‘z joylariga tiklanadi.
3. Agar formulada turli xil imtiyozlarga ega mantiqiy amallar qavslarsiz ketma-ket yozilgan bo‘lsa, u holda ularni bajarish ketma-ketligini anglatuvchi qavslar mantiqiy amallarni bajarish imtiyozlarini hisobga olgan holda navbat bilan o‘z joylariga tiklanadi.
2- m i s o l . x  y  y  z  (z  x) ko‘rinishda yozilgan formulani tahlil qilaylik. Bu formuladagi amallarni bajarish tartibi faqat bir joyda qavslar bilan aniqlangan. Mantiqiy amallarni bajarish imtiyozlari va qavslar haqidagi kelishuvga ko‘ra berilgan formulani ((x  ( y  y))  (z  (z  x))) ko‘rinishda ifodalash mumkin. ■
Tabiiyki, ixtiyoriy formula uchun chinlik jadvali16 tuzish mumkin. Berilgan formulaga mos chinlik jadvalini tuzishda shu formula tarkibidagi amallarga e’tibor bergan holda asosiy chinlik jadvallaridan ketma-ket foydalanish mumkin.
2- t a ’ r i f. Agar berilgan ikkita formula tarkibida ishtirok etuvchi elementar mulohazalarning har bir qiymatlar satri uchun bu formulalarning qiymatlari bir xil bo‘lsa, u holda ular teng kuchli formulalar deb ataladi.
3- t a ’ r i f. Agar berilgan ikkita formula tarkibida ishtirok etuvchi elementar mulohazalarning qiymatlar satrlaridan hech bo‘lmaganda bittasi uchun bu formulalarning qiymatlari har xil bo‘lsa, u holda ular teng kuchlimas formulalar deb ataladi.
Teng kuchli va teng kuchlimas iboralari na faqat formulalarga nisbatan, balki ixtiyoriy mantiqiy mulohazalarga nisbatan ham qo‘llanilisi mumkin. Ba’zan, teng kuchli va teng kuchlimas iboralari o‘rnida, mos ravishda, ekvivalent va ekvivalentmas iboralari ishlatiladi. Ekvivalentlik tushunchasi ekvivalensiya tushunchasiga ohangdosh bo‘lgani uchun, ularni bir-biridan farq qilish maqsadida ko‘proq teng kuchlilik iborasidan foydalanamiz.
Berilgan formulalarning teng kuchliligini ifodalashda “ ” belgidan, teng kuchlimasligini ifodalashda esa “ ” belgidan foydalaniladi. Masalan, agar berilgan A va B formulalar teng kuchli formulalar bo‘lsa, u holda A  B deb, A va B formulalar teng kuchlimas formulalar bo‘lganda esa, A B deb yoziladi. Ba’zan, formulalarning teng kuchliligini ifodalashda “  ” belgidan, teng kuchlimasligini ifodalashda esa “  ”belgidan ham foydalaniladi.
Berilgan formulalarning teng kuchli yoki teng kuchlimas bo‘lishini aniqlashda, odatda, ular uchun tuzilgan chinlik jadvallaridan foydalaniladi.
Matematik mantiqda formula tushunchasi bilan bir qatorda mantiqiy ifoda tushunchasi ham qo‘llaniladi. Mantiqiy ifoda shunday murakkab mulohazaki, uning tarkibida berilgan elementar mulohazalardan inkor, diz’yunksiya, kon’yunksiya, implikasiya, ekvivalensiya mantiqiy amallari bilan bir qatorda mulohazalar algebrasidagi boshqa amallarining ham chekli kombinatsiyasi va, zarur bo‘lganda, mulohazalar ustida mantiqiy amallarning bajarilish tartibini ko‘rsatuvchi qavslar qatnashishi mumkin. Mantiqiy ifoda tushunchasiga ham formula tushunchasiga matematik induksiya usuliga tayangan holda berilgan ta’rifga o‘xshash qat’iy ta’rif berilishi mumkin. Mantiqiy ifodalarning teng kuchliligi tushunchasini ham formulalar teng kuchliligi tushunchasiga o‘xshash aniqlash mumkin.
Oddiy algebrada aynan teng qiymatga ega ifodalarni bir-biri bilan almashtirish mumkin bo‘lganidek, mulohazalar algebrasida ham mantiqiy ifoda tarkibidagi qismiy mantiqiy ifodalarni (formulalarni, mulohazalarni) ularga teng kuchli bo‘lgan ifodalar (formulalar, mulohazalar) bilan almashtirish, ya’ni o‘rniga qo‘yish usulidan foydalanish mumkin. Bu esa murakkab ifodalarni (formulalarni, mulohazalarni) soddalashtirish imkonini beradi.