Diskret tuzilmalar

O`ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA KOMMUNIKATSIALARINI
RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT
AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
TT va KT FAKULTETI
TT 13-22S GURUH TALABASINING
DISKRET TUZILMALAR
Fanidan
3-mustaqil ish
 
BAJARILDI: Hasanboyev.N
QABUL QILDI : Ro`zimurodov.I
QARSHI-2023
FORMULALAR. ASOSIY TENG KUCHLI FORMULALAR. NORMAL FORMALAR. MULOHAZALAR HISOBINI QURISH. TENG KUCHLI ALMASHTIRISHLAR. NORMAL FORMALAR.
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.

2. 
   
   Agar formulaning ko‘rinishi Á *  dan iborat bo‘lsa, u holda uning formulaostilari Á ,  , Á *  , hamda Á va  larning barcha formulaostilaridan iborat bo‘ladi. Bu erda * - Ù , Ú , Þ , Û amallaridan biri.
   
3. 
   
   Agar formulaning ko‘rinishi ù Á bo‘lsa, uning formulaostilari Á formula, Á formulaning barcha formulaostilari va ù Á ning ûzidan iborat.
   
4. 
   
   Boshqa formulaostilari yo‘q.