Teng kuchli formulalar. Tavtologiya va ziddiyatlar

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI
VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Algoritmlash va matematik modellashtirish kafedrasi

Diskret tuzilmalari fanidan
MUSTAQIL ISH
MAVZU: Teng kuchli formulalar. Tavtologiya va ziddiyatlar
Bajardi:072-21 guruh talabasi
Rasulev Dilmurot
Toshkent – 2022
Reja:

1. 
   Normal formalar.
   
2. 
   Mulohazalar hisobini qurish.
   
3. 
   Teng kuchli formulalar
   
4. 
   Xulosa.
   

1. Mulohazalar algebrasi.Mulohazalar ustida mantiq amallari.
I.1.1 – ta’rif. Rost yoki yolg‘onligini bir qiymatli aniqash mumkin bo‘lgan darak gap mulohaza deyiladi.
« sayin – daraxt », « Negrlar – oq tanli odamlar »,
« 5 > 2 », « Bugun – 5 – may » kabi gaplar mulohazalarga misol bo‘la oladilar. Lekin щar qanday gap ham mulohaza bo‘la olmaydi, masalan, « YAshasin O‘zbekiston yoshlari! », « Sen nechanchi kursda o‘qiysan? » kabi gaplar mulohazalar emas, chunki ular darak gaplar emas.
Demak, biror bir gap mulohaza bo‘lishi uchun, u albatta darak gap bo‘lishi va rost yoki yolg‘onligi bir qiymatli aniqlanishi shart.
Ûzbek tilidagi barcha mulohazalar to‘plamini ℳ orqali belgilaylik. ℳ to‘plamning elementlarini lotin alifbosining bosmacha, indeksli yoki indekssiz bosh щarflari bilan belgilashga kelishib olamiz. YA’ni A , V , S , . . . , A ₁,
A ₂ , . . . , A _n - mulohazalardir. A mulohaza rost bo‘lsa, unga 1 ni, yolg‘on bo‘lsa, 0 ni mosqo`yamiz.
I.1.2 – ta’rif. A va V mulohazalarning kon’yunksiyasi deb, A va V mulohazalar rost bo‘lgandagina rost, qolgan hollarda yolg‘on bo‘ladigan A V mulohazaga aytiladi.

Mulohazalar kon’yunksiyasi mantiqiy ko‘paytirish deb ham ataladi va A · V yoki A & V kabi belgilanishi mumkin.
I.1.3 - ta’rif. A va V mulohazalar diz’yunksiyasi deb, A va V mulohazalarning ikkalasi ham yolg‘on bo‘lgandagina yolg‘on, qolgan hollarda rost bo‘ladigan A Ú V mulohazaga aytiladi.
Mulohazalar diz’yunksiyasi mantiqiy qo‘shish deb ham yuritiladi va A + V kabi belgilanishi ham mumkin.

I.1.4 - ta’rif. A mulohaza rost bo‘lganda yolg‘on, yolg‘on bo‘lganda rost bo‘ladigan ù A mulohaza A mulohazaning inkori deyiladi.

A mulohazaning inkori `A orqali belgilanishi ham mumkin.
Mulohazalar ustida bajariladigan amallar rostlik jadvali deb ataladigan jadvallar yordamida ham berilishi mumkin. YUQorida ta’riflangan amallar rostlik jadvali quyidagi ko‘rinishda bo‘ladi :

A	V	A Ù V	A Ú V	ù A
1	1	1	1	0
1	0	0	1	0
0	1	0	1	1
0	0	0	0	1

Bundan tashqari yana bir qancha amallar, ya’ni :
Þ - implikatsiya yoki mantiqiy xulosa,
Û yoki ~- ekvivalensiya yoki mantiqiy teng kuchlilik,
ï - SHefer shtrixi,
¯ - Pirs strelkasi,
Å - qat’iy diz’yunksiya, ya’ni 2 modul bo‘yicha qo‘shish amallari quyidagi jadval orqali beriladi:

A	V	A Þ V	A Û V	A ô V	A ¯ V	A Å V
1	1	1	1	0	0	0
1	0	0	0	1	0	1
0	1	1	0	1	0	1
0	0	1	1	1	1	0

I.2. Mulohazalar algebrasi. Mulhozalar algebrasi alfaviti, formula tushunchasi.
I.2.1 - ta’rif. < M , ù , Ù , Ú ,Þ , Û > - universal algebra mulohazalar algebrasi deyiladi.

Mulohazalar algebrasini qisqacha MA deb belgilaymiz.
MA ning alfaviti quyidagilardan iborat :
A , V , S , . . . – mulohazalarni belgilash uchun ishlatiladigan xarflar;
ù , Ù , Ú , Þ , Û - mantiq amallarini belgilash uchun ishlatiladigan belgilar;
( , ) - chap va o‘ng qavslar .
Mulohazalar algebrasining asosiy tushunchalaridan biri formula tushunchasidir. Unga induktiv ta’rif beramiz.

I.2.2 - ta’rif. 1). Xar bir mulohaza formuladir.
2). Agar Á va  lar formulalar bo‘lsa, u holda
( ù Á) , ( Á Ù Â ) , ( Á Ú Â ) , ( Á Þ Â ) , ( Á Û Â ) lar ham formulalardir.
3). 1) va 2) lar yordamida щosil qilingan ifodalargina formulalardir.

Masalan, A , V , S lar 1) ga asosan formulalar; ( ù V ),
( A Þ ( ù V )), ( ( ( A Þ ( ù V )) Þ A ) Ù S ) lar 2) ga asosan formulalardir.
Formulalarning tarkibidagi qavslarni kamaytirish ma=sadida mantiq amallarining bajarilish tartibini
ù , Ù , Ú , Þ , Û deb belgilab olamiz. Demak, qavslar bo‘lmaganda avval ù , keyin Ù va щ.k. amallar bajariladi. Bundan tashqari tash=i qavslarni ham extiyoj bo‘lmaganda tashlab yuboramiz. Bunday ûzgartirishlardan keyin
( ( A Ù V ) Ú ( (ù A ) Þ S ) ) formulani A Ù V Ú (ù A Þ S ) ko‘rinishda ¸zishimiz mumkin bo‘ladi.

I.2.3 - ta’rif. Formulada qatnashgan mantiq amallari soni formulaning rangi deyiladi.

YUQorida keltirilgan formulaning rangi 4 ga teng.

I.2.4 - ta’rif. 1. Á formula - mulohaza bo‘lsa , uning formulaosti faqat uning ûzidan iborat.
Agar formulaning ko‘rinishi Á *  dan iborat bo‘lsa, u holda uning formulaostilari Á ,  , Á *  , hamda Á va  larning barcha formulaostilaridan iborat bo‘ladi. Bu erda * - Ù , Ú , Þ , Û amallaridan biri.
Agar formulaning ko‘rinishi ù Á bo‘lsa, uning formulaostilari Á formula, Á formulaning barcha formulaostilari va ù Á ning ûzidan iborat.
Boshqa formulaostilari yo‘q.
Teng kuchli formulalar. Tavtologiya – mantiq qonunii.
I.3.1 - ta’rif. MA ning Á va  formulalari berilgan bo‘lib, bu formulalar tarkibiga kirgan barcha mulohazalar A₁ ,. . ., A_m - lardan iborat bo‘lsin. Agar A₁ , . . . , A _m mulohazalarning barcha qiymatlar tizimlari ( i₁, . . . , i_m ) lar uchun Á va  formulalar bir щil qiymatlar qabul qilsalar, u holda, bu formulalar teng kuchli formulalar deyiladi.
Á va  formulalarning teng kuchliligi Á º  ko‘rinishda ifodalanadi.
I.3.2 - ta’rif. Mulohazalar algebrasining
Á( A₁,. . . , A_n) formulasi A₁ ,. . . , A_n mulohazalarning barcha qiymattizimi ( i₁, . . . , i_n) uchun 1 qiymat qabul qilsa, aynan rost formula yoki tavtologiya yoki mantiq qonunii deyiladi.
Aynan rost formulani qisqacha AR deb belgilaymiz.
I.3.3 - ta’rif. MA ning Á ( A ₁, . . . , A _n ) formulasi
A₁ ,. . . , A_n mulohazalarning barcha qiymattizimi
( i₁ , . . . , i_n ) lar uchun 0 qiymat qabul qilsa, aynan yolg‘on yoki ziddiyat deyiladi
I.3.4 - ta’rif. Agar mulohazalar algebrasining
Á (A₁ , . . . , A_n) formulasi A₁ , . . . , A_n larning kamida bitta ( i₁ , . . . , i_n ) qiymattizimida 1 ga teng qiymat qabul qilsa, u holda bu formula bajariluvchi formula deyiladi.
I.3.5 - teorema. Mulohazalar algebrasining Á va  formulalari teng kuchli formulalar bo‘lishi uchun, Á Û Â formula aynan rost formula bo‘lishi zarur va etarli.
Isbot. Á º  bo‘lsin. U holda Á va  formulalarga kirgan barcha propozitsional o‘zgaruvchilarning barcha qiymattizimlarida Á va  formulalar bir xil qiymatlar qabul qiladilar. YA’ni, Á Û Â = 1 bo‘ladi.
Aksincha, Á Û Â = 1 bo‘lsa, Á = 1 bo‘lganda  = 1 va
Á = 0 bo‘lganda  = 0 bo‘ladi.
I.3.6. Asosiy teng kuchli formulalar.
A Ù A º A (kon’yunksiyaning idempotentlik qonunii).
A Ú A º A (diz’yunksiyaning idempotentlik qonunii).
A Ù 1 º A .
A Ú 1 º 1.
A Ù 0 º 0 .
A Ú 0 º A .
A Ú ù A º 1 – uchinchisini inkor qilish qonunii.
A Ù ù A º 0 - ziddiyatga keltirish qonunii.
ù ( ù A ) º A - qo‘sh inkor qonunii.
A Ù ( V Ú A ) º A .
A Ú ( V Ù A ) º A .
A Û V º ( A Þ V ) Ù ( V Þ A ).
A Þ V º ù A Ú V .
ù ( A Ù V ) º ù A Ú ù V .
ù ( A Ú V ) º ù A Ù ù V .
A Ù V º ù ( ù A Ù ù V ).
A Ú V º ù ( ù A Ù ù V ).
A Ù V º V Ù A – kon’yunksiyaning kommutativlik qonunii.
A Ú V º V Ú A – diz’yunksiyaning kommutativlik qonunii.
A Ù ( V Ú S ) º ( A Ù V ) Ú ( A Ù S ) - Ù ning Ú ga nisbatan distributivlik qonunii.
A Ú ( V Ù S ) º ( A Ú V ) Ù ( A Ú S ) - Ú ning Ù ga nisbatan distributivlik qonunii.
A Ù ( V Ù S ) º ( A Ù V ) Ù S – kon’yunksiyaning assotsiativlik qonunii.
A Ú ( V Ú S ) º ( A Ú V ) Ú S – diz’yunksiyaning assotsiativlik qonunii.
Xulosa.
Men bu kurs ishini yozish davomida quyidagilarni bildimki.MA ning ( va ( formulalari berilgan bo‘lib, bu formulalar tarkibiga kirgan barcha mulohazalar A1 ,. . ., Am - lardan iborat bo‘lsin. Agar A1 , . . . , A m mulohazalarning barcha qiymatlar tizimlari ( i1, . . . , im ) lar uchun ( va ( formulalar bir щil qiymatlar qabul qilsalar, u holda, bu formulalar teng kuchli formulalar deyiladi.
I va U formulalarning teng kuchliligi I=U ko‘rinishda ifodalanadi.
FOYDALANILGAN ADABIYOTLAR.
“O’zbekiston Respublikasi yanada rivojlantirish bo’yicha harakatlar strategiyasi to’g’risida”gi O’zbekiston Respublikasi Prezidentining Farmoni. Toshkent: Adolat 2017.
I.A.Karimov Yuksak manaviyat-yengilmas kuch.-T.: Sharq, 2008.
Ozbekiston Respublikasi «Talim togrisida» Qonuni. Barkamol avlod - Ozbekiston taraqqiyotining poydevori. -T.: Sharq, 1997.
To’rayev H.T. Matematik mantiq va diskret matematika. T: Taffakur Bo’stoni, 2011
To’rayev H.T. Mulohazalar hisobi va predikatlar mantiqi. Muammoli lektsiyalar kursi Samarqand SamDU nashriyoti, 2003
Nazarov R.N., Toshpo’latov B.T., Dusumbetov A.D. Algebra va sonlar nazariyasi. T, o’qituvchi 2 qism, 1995 й.
Куликов Л. Я. Алгебра и теория чисел. Москва: Высш.шк. 1979 г. (
Ziyonet.uz
Referat.uz