Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

Mavzuni jonlashtirish uchun savollar:

1. 
   Formula, elementar formula deb nimaga aytiladi?
   
2. 
   Teng kuchli va teng kuchlimas formulalar farqini ayting.
   
3. 
   Aynan chin, aynan yolg‘on formulalarnining mohiyati nimadan iborat?
   
4. 
   Bajariluvchi formula, bajarilmaydigan formulani ayting.
   
5. 
   Asosiy teng kuchliliklarni keltiring.
   

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 va mulohazalarning ekvivalensiyasi ikkita va implikatsiyalarning 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- misol. Ushbu , , , , , , , va ko‘rinishda yozilgan murakkab mulohazalarning har biri formuladir, lekin va 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- ta’rif. 1) Agar elementar mulohaza bo‘lsa, u holda formuladir;
2) agar formula bo‘lsa, u holda formuladir;
3) agar va formulalar bo‘lsa, u holda , , va 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 o‘zgaruvchilarga (elementar mulohazalarga) bog‘liqligini ta’kilash kerak bo‘lgan holda 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, formulani ko‘rinishda yozish mumkin).
2) kon’yunksiya amali diz’yunksiya, implikatsiya va ekvivalensiya amallariga nisbatan formulalarni mustahkamroq bog‘laydi deb hisoblanadi (masalan, formulani , formulani , formulani esa ko‘rinishda yozish mumkin).
3) diz’yunksiya amali implikatsiya va ekvivalensiya amallariga nisbatan formulalarni mustahkamroq bog‘laydi deb hisoblanadi (masalan, formulani , formulani esa ko‘rinishda yozish mumkin).
4) implikatsiya amali ekvivalensiya amaliga nisbatan formulalarni mustahkamroq bog‘laydi deb hisoblanadi (masalan, formulani ko‘rinishda yozish mumkin).
Bu kelishuvlar, yuqorida ta’kidlanganidek, formulalar tarkibidagi qavslar sonini kamaytirish imkonini beradi. Masalan, formulani 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.