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



Download 53,5 Kb.
bet1/5
Sana28.05.2023
Hajmi53,5 Kb.
#945027
  1   2   3   4   5
Bog'liq
Diskret tenglamalar


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.


Download 53,5 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish