Talim vazirligi buxoro davlat universiteti fizika-matematika fakulteti


Download 50.31 Kb.
bet1/3
Sana24.06.2020
Hajmi50.31 Kb.
  1   2   3

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS

TALIM VAZIRLIGI

BUXORO DAVLAT UNIVERSITETI

FIZIKA-MATEMATIKA FAKULTETI

MATEMATIKA” KAFEDRASI

Diskret matematika va matematik mantiq” fanidan


Mavzu: “Dizyunktiv va konyunktiv normal forma”.
Bajardi : Matematika fakulteti 1-1MAT-19 guruh talabasi

Sattarova Nargiza

Tekshirdi : ______________________________________

Kurs ishi himoya qilingan sana : “____”_____20____yil
Komissiya azolari : _____________ __________________________

(imzo) (FISH)

_____________ __________________________



(imzo) (FISH)

_____________ __________________________



(imzo) (FISH)
Ball: ___________

Buxoro -2020



Mavzu: Dizyunktiv va konyunktiv normal forma.

Reja:

I BOB Mulohazlar algebrasi.

    1. Mulohaza. Mulohazalar ustida mantiqiy amallar.

    2. Formulalarning normal shakllari.

1.3 Mulohaza tushunchasi.

1.4 Dizyunktiv va konyunktiv normal formalar.

1.5 .Mukammal dizyunktiv va mukammal konyunktiv normal formalar.

Xulosa.

Ilova

Foydalanilgan adabiyotlar ro’yxati

KIRISH

Bugungi kunda, “Farzandlarimiz bizdan ko’ra kuchli, bilimli, don ova albatta baxtli bo’lishi shart” degan hayotiy da’vat har birimizning, ota-onalar va keng jamoatchilikning ongi va qalbidan mustahkam o’rin egallagan. Hammamizni tarbiyalagan, voyaga yetkazgan- shu xalq. Barchamizga tuz-nasiba bergan ham-shu xalq. Bizga ishonch bildirgan, rahbar qilib saylagan ham aynan shu xalq.

Shunday ekan, biz birinchi navbatda kim bilan muloqot qilishimiz kerak- odamlarimiz bilan. Kim bilan bamaslaxat ish tutishimiz kerak- avvalo xalqimiz bilan. Shunda xalqimiz bizdan rozi bo’ladi. Xalq bizdan rozi bo’lsa, yaratgan ham bizdan rozi bo’ladi.

“Matematika sohasidagi ta’lim sifatini oshirish va ilmiy-tadqiqotlarni rivojlantirish chora tadbirlari to’g’risida” prezident qarori qabul qilindi. Xalq ta’limi vazirligi xabariga ko’ra, matematika sohasidagi ta’lim sifatini oshirish, ilmiy-tadqiqotlarni rivojlantirish va ilmiy ishlanmalarni amaliyotga joriy qilishning ustuvor yo’nalishlari belgilandi.

Qarorga ko’ra, har bir tumanda (shaharda) matematika fanini chuqurlashtirib o’qitishga ixtisoslashtirilgan maktablar (ixtisoslashtirilgan bog’chalar) bosqichma-bosqich tashkil etiladi.

Hozirgi kunda Diskret matematika va matematik mantiq amaliy masalalarni yechishning eng keng tarqalgan fanlardan biri, masalan, hisoblash texnikasining mantiqiy asoslari va dasturiy ta’minotini rivojlantirishda.

Matematik mantiq, bir tomondan, formal mantiqga muammolariga matematik metodlarni qo’llash bo’lsa, ikkinchi tomondan, matematikani asoslashga xizmat qiluvchi fan sifatida foydalanishdir. Hozirgi zamon matematik mantiqi avtomatika, mashina matematikasi, bir tildan ikkinchi tilga avtomatik tarzda tarjima qilish, matematik lingvistika, axborot nazariyasi va umuman kibernetikaning nazariy va asosi hisoblanadi.

Mavzuning dolzarbligi. Dizyunktiv va konyunktiv normal forma”Diskret matematika va matematik mantiq” kursida muhim tushunchalaridan biri hisoblanib, kurs davomida bu mavzu talabalarga mustaqil o’rganish uchun taqdim etiladi.

Ushbu kurs ishida mulohazalarda formula, qism formula, aynan chin, aynan yolg’on va bajariluvchi formulalar tushunchasi oliy o’quv yurtlari talabalarining bu boradagi bilimlarini mustahkamlashda muhim rol o’ynaydi. Talabalarning bu boradagi bilimlarini mustahkamlash bilan birga,kelajakdagi faoliyatlari uchun dastur-ul amal bo’lib xizmat qiladi.

Kurs ishining maqsadi. Yuqorida ishning dolzarbligi qismida bayon qilingan mulohazalar ishning maqsadini aniqlab beradi va ular quyidagilardan iborat:


  • Mulohaza. Mulohazalar ustida mantiqiy amallar.

- Formulalarning normal shakllari.

- Mulohaza tushunchasi.

- Dizyunktiv va konyunktiv normal formalar.

- Mukammal dizyunktiv va mukammal konyunktiv normal formalar.



Tadqiqot usuli va uslubiyoti.O’quv-qo’llanma sifatida foydalanish mumkin.Talabalar keyingi faoliyatida dasturiy vosita sifatida foydalana olishi mumkin. Kurs ishidan oliy o'quv yurtlari talabalari diskret matematika va matematik matiq fanini o'rganishda foydalanishlari mumkin.

-Kurs ishining predmeti. Formulalarning normal shakllari.

Dizyunktiv va konyunktiv normal formalar.



  • Kurs ishining ilmiy yangiligi. Ishda ilmiy yangilik qilinmagan,u refarativ uslubiy xarakterga ega bo'lib, unda mulohazalar algebrasi konyunktiv va dizyunktiv normal formalar haqida ma`lumotlar keltirilgan

  • Kurs ishining metodologik asosi. Ushbu kurs ishi uchun mulohazalar algebrasi bo’limini o'rganishda metodologik asos bo'lib xizmat qiladi.

  • Kurs ishining hajmi va tuzilishi. Kurs ishi kirish qismidan, 1 ta bob, 5 ta paragraf, xotima hamda foydalanilgan adabiyotlar ro’yxatidan iborat bo’lib, ishning hajmi 22 betni tashkil etadi.


Mulohazalar algebrasi formulasining normal shakllari.
1. Mulohazalar algebrasi formulasining normal shakllari.
2. Yechilish muammosi.
3. Dizyunktiv va konyunktiv normal formalar .
4. Mulohazalar algebrasi formulasining normal shakllari.
Tengkuchli almashtirishlar bajarib, mulohazalar algebrasining formulalarini har xil
ko'rinishlarda yozish mumkin. Masalan, ABCformulani A BC yoki (A B) (A C)
ko'rinishlarda yoza olamiz. Mantiq algebrasining kontakt va rele-kontaktli sxemalar, diskret
texnikadagi tatbiqlarida va matematik mantiqning boshqa masalalarida formulalarning normal
shakllari katta ahamiyatga ega.
Quyidagi belgilashni kiritamiz:

Xᵟ=

= c ekanligi aniq.


1-ta'rif. x₁ᵟ x₂ᵟ …xₙᵟ (1)
ko'rinishdagi formulaga elementar kon'yunksiya deb aytamiz. Bu yerda {1,2,...,n} ixtiyoriy qiymatlar satri va xi o'zgaruvchilar orasida bir xillari bo'lishi mumkin.
2-ta'rif. x₁ᵟ x₂ᵟxₙᵟ (2)

ko'rinishdagi formulaga elementar diz'yunksiya deb aytamiz. Bu yerda ham
1 {1,2,...,n} ixtiyoriy qiymatlar satri va xi o'zgaruvchilar orasida bir xillari bo'lishi mumkin.
3-ta'rif. Elementar diz'yunksiyalarning kon'yunksiyasiga formulaning kon'yunktiv normal shakli (KNSh) va elementar kon'yunksiyalarning diz'yunksiyasiga formulaning diz'yunktiv normal shakli (DNSh) deb aytiladi.
KNShga (x y) ( z) (x z) formula va DNShga x y z x z formula misol bo'la oladi.
1-teorema. Elementar mulohazalarning har bir P formulasiga tengkuchli kon'yunktiv normal shakldagi Q formula mavjud.
Bu teoremani isbotlashda ushbu tengkuchliliklardan foydalanamiz:
1 ;2. ;
3. A B B; 4. A ; (3)
5. A B ( B) (A ); 6. A B (A ) ( B).
Isbot. P formula normal kon'yunktiv shaklda bo'lmasa, quyidagi hollar bo'lishi mumkin:
a) P dagi elementar mulohazalar va amallari bilangina birlashtirilgan bo'lsa ham, lekin
so'nggi amalni ifodalamaydi. Bu holda A (B C) (A B) (A B) distributivlik
qonunidan foydalanib, so'nggi amali dan iborat tengkuchli Q formulaga keltiramiz.
b) P formula , , ,  mantiqiy amallar vositasida tuzilgan qandaydir formulani
ifodalasin. U holda P ga (3) tengkuchliliklarni tatbiq etib P bilan tengkuchli va , ,
bilan ifodalangan P1 formulani hosil qilamiz. Agar P1 KNSh ko'rinishida bo'lmasa, unga
A (B C) (A B) (A B) distributivlik qonunini tatbiq etib, chekli qadamlardan keyin
P bilan tengkuchli Q kon'yunktiv normal shakldagi formulaga kelamiz.
Izoh. P formulani kon'yunktiv normal shaklga keltirish jarayonida
A A A, A A A, A J A, A J J ,
A = , A = A , A = J (4)
tengkuchliliklardan foydalanib, uni soddalashtirish mumkin.
Misollar. 1. P [(x y) ( )][x ( y)]
P {[(x y) ( )] x}{[(x y) ( )] ( y)}
[(x y) x][( ) x] [(x y) ( y)][( ) ( y)]
(x y) [J ] (J y) ( J) (x y) J J J x y ;
P x y .
Shunday qilib, P formulaning KNSh bittagina diz'yunktiv (x y) haddan iborat ekan.
2. P x y
P x y (x y) [] [() ()] [(x y) (x y)][( ) ( )]
[(x y) (x y)] [( ) ( )]
[(x y x) (x y y)][( y ) (x )]
(x y) (x y) (x ) (x ) (x y) (x ):
P (x y) (x y).
P formulasi tavtologiya ekanligini chinlik jadvaliga murojaat qilmay turib aniqlash
mumkinmi degan savolga quyidagi chinlik alomati deb atalgan teorema ijobiy javob beradi.
2-teorema. P formula doimo chin bo'lishi uchun uning KNSh dagi har bir elementar diz'yunktiv hadida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham mavjud bo'lishi zarur va yetarli.
Isbot: a) P formulaning
P A1 A2 ... An (5)
KNSh dagi har bir Ai hadida kamida bitta elementar mulohaza bilan birga bu mulohazaning
inkori ham mavjud bo'lsin, ya'ni Ai x y ...... u shaklida bo'lsin, u holda x J va J A J larga asosan Ai J (y .... u V) J bo'ladi.
Demak, P J J ... J J bo'ladi, ya'ni aynan chin formula bo'ladi.
b) Endi P - tavtologiya bo'lsin va Ai uning KNSh dagi shunday elementar diz'yunktiv hadi
bo'lsinki, unda birorta elementar mulohaza bilan birga uning inkori qatnashmagan bo'lsin.
Masalan, Ai x y ..... u shaklida bo'lsin. Endi, elementar mulohazalarning shunday
qiymatlar satrini olaylikki, bu satrda x ning qiymati yo, y ning qiymati ch, z ning qiymati
yo,......, u ning qiymati yo bo'lsin. U vaqtda
Ai x ..... u yo ch ..... yo = yo .... yo = yo.
Demak, P A1 A2 ... An ning qiymati ham yolg'on bo'ladi. Ammo, teoremaning shartiga asosan P ning qiymati aynan chindir. Natijada qarama-qarshilikka keldik. Demak, elementar diz'yunksiyalarning har bir hadida birorta mulohaza o'zi va o'zining inkori bilan qatnashishi
shart.
Har qanday mantiqiy sistemalaridagidek mulohazalar algebrasi uchun masalani qo‘yish mumkin: mulohazalar algebrasining har qanday formulasi formula yoki formula emasligini chekli qadamdan so‛ng aniqlab beradigan yagona usul (algoritm) mavjudmi yoki mavjud emasmi? Bu masala yechilish muammosi deb ataladi. Yechilish
muammosini faqat formulalar uchun emas, balki formulalar sinfidan kengroq bo‘lgan bajariluvchi formulalar sinfi uchun qo‘ysa bo‘ladi. Albatta, keyingi muammoning yechimi oldingi muammoning ham yechimi bo‘lishi ravshandir.
Mulohazalar algebrasi uchun bu muammo ijobiy tarzda hal etiladi. Haqiqatan, mulohazalar algebrasining ixtiyoriy formulasi bo‘lsa, uning rostlik jadvalini tuzish bilan formulaning bajariluvchi formula yoki formula ekanligini bir qiymatli aniqlash mumkin. Demak, yuqoridagi muammoni ijobiy hal etuvchi yagona usul (algoritm) mavjud bo‘lib, bu algoritm rostlik jadvalidan iboratdir. Ammo bu algortmning muhim kamchligi bor ekanligini sezish mumkin.
Haqiqatan, formula tarkibida ta propozitsional o‘zgaruvchi qatnashgan bo‘lsa, u holda uning qiymatlarini propozitsional o‘zgaruvchilar qiymatlarining ta tanlanmada hisoblashga to‘g‘ri keladi. Ravshanki, bu usul hatto uncha murakkab bo‘lmagan formulalar qiymatlarini hisoblashda ham juda katta qiyinchiliklar tug‘diradi. Shuning uchun ham bu usul amaliy foydalanish nuqtai nazaridan qulaysizdir. Biz quyida amaliy jihatdan katta qulaylik beradigan boshqa usul tanishamiz.

Download 50.31 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling