Mavzu: Predikatlaralgebrasi, mulohazalarhisobiformulasitushunchasi

5. Ekvivalensiyaamali.

Ta’rif: p va q mulohazalarning ekvivalensiyasi deb p va q larning bir xil qiymatlarida rost, turli qiymatlarida yolg’on bo’lgan yangi mulohazaga aytiladi va uni  ko’rinishda belgilanadi.
Ekvivalensiya amaliga “Agar … bo’lsa, shu holda va faqat shu holda ... bo’ladi”, “...bajarilishi uchun ... bajarilishi zarur va etarli” kabi bog’lovchi so’zlar mos keladi.
Masalan, p: “berilgan natural son 3 gabo’linadi”, q: “berilgansonningraqamlaryig’indisi 3 gabo’linadi”.
pq: “Berilgansonning 3 gabo’linishiuchununingraqamlariyig’indisi 3 gabo’linishizarurvayetarli”.
Ekvivalensiyaamaligaquyidagirostlikjadvalimoskeladi:

p	q	pq
1	1	1
1	0	0
0	1	0
0	0	1

Har birqaralayotganmulohazagarostlikustunidanbittaustunmoskeladi. Bu ustunniqiymatlarustuni deb yuritamiz.
Ta’rif:Qiymatlariustunitengbo’lganmulohazalaro’zarotengkuchlimulohazalardeyiladi.
Masalan: p=>q va ┐q=>┐ p mulohazalarningtengkuchliliginiquyidagirostlikjadvaliorqaliko’rsataylik:

p	q	┐p	┐q	p=>q	┐q=>┐p
1	1	0	0	1	1
1	0	0	1	0	0
0	1	1	0	1	1
0	0	1	1	1	1

p=>qva ┐q=>┐pmulohazalarningustunibirxilbo’lganiuchunp=>q=┐q=>┐pbo’ladi.
Ta’rif: universial algebra mulohazalaralgebrasi deb yuritiladi.
Tarif: 1. p, q, r,... lar mulohazalaralgebrasiningformulalaridir.
2. Agar p va q lar mulohazalaralgebrasiningformulalaribo’lsa, u holda ┐p, p q, p q, p=>q, pq ham formula bo’ladi.
3. Mulohazalaralgebrasidagiformulalarfaqat 1-va 2-formulalar yordamidatuziladi. Ko’phollarda 2. yordamidaaniqlanganformulalarmurakkabformulalar deb yuritiladi.
Murakkabformulagaargumentlarirostyokiyolg’onqiymatniqabulqiluvchifunktsiya deb qarashmumkin.
Ta’rif: x_i, argumentlarning har birqabulqilishimumkinbo’lganbarcha 1 va 0 qiymatlartizimidaA(x₁, x₂,…,x_n) formulaniifodalovchimantiqiyfunktsiyarost (yolg’on) qiymatgaerishsa, u holdabu formula aynanrost (yolg’on) formula deyiladi.
Misol:

A	B
1	1	1	1
1	0	1	1
0		0	1
0	0	1	1

Agar A(x₁, x₂, …, x_n) formulada n ta elementar mulohaza bo’lsa, u holda bu formulaning rostlik jadvali 2ⁿ ta satr (yo’l) dan iborat bo’ladi.

1.2-§. Teng kuchliformulalarvaasosiytengkuchliliklar
Ta’rif: Tarkibidagi x_i(i= ) o’zgaruvchilarning mumkin bo’lgan barcha qiymatlar tizimida A(x₁, x₂, …, x_n) va B(x₁, x₂, …, x_n) formulalarning qiymatlari ustuni bir xil bo’lsa, u holda bu formulalar o’zaro teng kuchli formulalar deyiladi va uni A(x₁, x₂, …, x_n)≡B(x₁, x₂, …, x_n) ko’rinishda belgilanadi.
Misol:

A	B	C
1	1	1	0	1	1	1	1
1	1	0	0	1	1	0	0
1	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0
0	1	1	1	1	1	1	1
0	1	0	1	1	1	0	0
0	0	1	1	1	1	1	1
0	0	0	1	1	1	0	0

Agar va formulalartengkuchlibo’lsalar, u holda va lar aynanrostformulalarbo’lishiravshandir.Aksincha, qandaydir va (birxilpropozitsionalo’zgaruvchilargaegabo’lgan) formulalaruchun va lar aynanrostfurmulalarbo’lsa, u holda bo’ladi.
va formulalartengkuhliformulalarekaniniko’rsataylik:

A	B
1	1	1	1	1	1
1	0	0	1	0	0
0	1	1	0	0	0
0	0	1	1	1	1

Shundayqilib, butengkuchliliklarndako’rinadiki, bo’lishiuchun formula aynanrost formula bo’lishizarurvayetarlidir. Teng kuchlibo’lishmunosabatiekvivalent binary munosabatekanligiravshandir, ya’nibumunosabat

1. 
   –refleksivlik.
   
2. 
   Agar bo’lsa, u holda bo’ladi– simmetriklikva
   
3. 
   Agar va bo’lsa, u holda bo’ladi – tanzitivlikxossalarigaegadir.
   

Teorema: – jumlalaralgebrasiningixtiyoriyformulasi, uningqismformulasibo’lsin. agar bo’lsa, u holda bo’ladi.
Isboti: bo’lganiuchun va formulalarulardaqatnashganpropozitsionalo’zgaruvchilarqiymatlariningbarchanaborlaridabirxilqiymatlargaerishadilar. va formulalarningqiymatlari yoki bo’lganiuchunyo , yoki hosilbo’ladi. Bu esa ekaniniko’rsatadi.
Teorema: , lar va formulalarning har biridaqatnashganbarchapropozitsionalo’zgaruvchilar, lar esaixtiyoriyformulalarbo’lsin. U holda bo’ladi; bunda har bir propozitsionalo’zgaruvchiberilgantengkuchlilikdanechajoydaqatnashganbo’lsa, shunchajoydamos formula bilanalmashtiriladi.
Isbot. tengkuchlilikdaqatnashgan har birpropozitisionalo’zgaruvchi 1 yoki 0 qiymatqabulqiladi. formula ham o’zidaqatnashganpropozitsionalo’zgaruvchilarqiymatlariningbarchanaborlarida 1 yoki 0 qiymatqabulqiladi. formula tarkibidaqatnashganpropozitsionalo’zgaruvchilar bo’lsin. bupropozitsionalo’zgaruvchilarqiymatlarinaborlaridanbiriva formulalarning nabordagiqiymatlarinaboribo’lsin. uzunligi bo’lgan nabor propozitsionalo’zgaruvchilarqabulqiladiganqiymatlarnaborlarisrasidamavjuddir. va formulalar ta naborning har biridabirxilqiymatgaegabo’lganiuchunular naborda ham birxilqiymatqabulqiladilar.
Yuqoridaisbotlanganteoremalardanbevositaquyidaginatijlaarkelibchiqadi.
Agar va bo’lsa, u holda
1)
2)
3)
4)
5)
Ta’rif: Agar formulaningtarkibidafaqatkonyuksiya, dizyunksiyavainkoroperatsiyalariqatnashganbo’lib, inkorsperatsiyasipropozitsionalo’zgaruvchilargaginategishlibo’lsa, u holdabunday formula keltirilgan formula deyiladi.
Misol: keltirilganformuladir, ammo keltirilgan formula emas, chunkibuformuladaimplikatsiyaoperatsiyasiqatnashishibilanbirgalikdainkoroperatsiyasimurakkab formula gategishlidir.
3.3-Teorema:Mulohazalaralgebrasining har bir formulasiningyoo’zikeltirilgandiryokiunitengkuchlikeltirilgan formula bilanalmashtirishmumkin.
Bu teoremaniisbotlashuchunmulohazalaralgebrasiningasosiytengkuchliliklaribilantanishibchiqamiz. Mulohazalaralgebrasiningtengkuchliliklariquyidagilar:

1. 
   (qo’shinkortengkuchliligi)
   
2. 
   (dizyunksiyakommuntativligi)
   
3. 
   (konyuksiyaningkommuntativligi)
   
4. 
   (dizyunksiyaassotsiativligi)
   
5. 
   (konyunksiyaningassotsiativligi)
   
6. 
   (dizyunksiyaningkonyuksiyaganisbatandistributivligi)
   
7. 
   (konyuksiyaningdizyunksiyaganisbatandistributivligi)
   
8. 
   (dizyunksiyaidempotentligi)
   
9. 
   (konyuksiyaningidempotentligi)
   
10. 
    (yutilishtengkuchliligi)
    
11. 
    (yutilishtengkuchliligi)
    
12. 
    (de Morgan tengkuchliligi)
    
13. 
    (de Morgan tengkuchliligi)
    
14. 
    (uchinchiniinkoretishtengkuchliligi)
    
15. 
    (qarama-qarshiliktengkuchliligi)
    
16. 
    a) , b) c) d)
    
17. 
    (kontrapozitsiyatengkuchliligi)
    

Bu tengkuchliliklaro’rinliekanliginirostlikjadvaliyordamidabevositatekshiribko’rishmumkin. Masalan, XIII tengkuchlilikuchunrostlikjadvaliniko’raylik:

A	B
1	1	0	0	1	0	0
1	0	0	1	0	1	1
0	1	1	0	0	1	1
0	0	1	1	0	1	1

II–XI, XIV–XVI tengkuchliliklarnitashkiletuvchiformulalarkeltirilganformulalarekanligiravshandir.
Bundantashqari,
(1)
tengkuchliliko’rinliekanliginirostlikjadvalituzibko’rsatishqiyinemas. Yuqorida ekanligiko’rsatilganedi. Implikatsiyaninginkorvadizyunksiyabilanalmashtirishmumkinekanligidanquyidagitengkuchliliknihosilqilamiz:
(2)
Demak, va formulalarkeltirilganformulalarbilanalmashtirilishimumkinekan. I, XII, XIII tengkuchliliklarqo’shinkorhamdadizyunksiyavakonyuksiyalarinkorlariniqandaykeltirilganformulalarbilanalmashtirishmumkinekaniniko’rsatadi.
Endi 3.3-teoremaning isbotinikeltiramiz. Agar formulaningo’zikeltirilgan formula bo’lsa, u holdateoremaisbotlanganbo’ladi.
Agar formula tarkibidaimplikatsiyavaekvivalentsiyaoperatsiyalariqatnashganbo’lsa, ularni (1) va (2) tengkuchliliklaryordamidaalmashtirishmumkin; formula tarkibida ko’rinishdagiqism formula qatnashganbo’lsa, uni bilan, yoki ko’rinishidagiqism formula qatnashganbo’lsa, ularnimosravishda va formulalarbilanalmashtirishmumkin. Bu protsessniyetarlimartatarkrorlab, nihoyat formulagatengkuchlibo’lgankeltirilganformulagakelamiz.
Shundayqilib, 3.3-teoremaga asosanmulohazalaralgebrasining har birformulasiniasosiyvaboshqatengkuchliliklaryordamidaalmashtiribungatengkuchliformulalarhosilqilishmumkin. Bu shaklalashtirishlarba’zibirmasalalarniyechishdakengko’lamdaishlatiladi. Bu yerdaformulalarnishaklalmashtirsihgaoidba’zinamunalarnikeltiramiz.
3.3-misol. formulaningshaklinialmashtiringvasoddalashtiring.

	(1) gaasosan
	XIII va XII gaasosan
	XII va XII gaasosan
	1 gaasosan
	VII gaasosan
	XIV va II gaasosan
	XVI gaasosan
	VII gaasosan
	XIV gaasosan
	XVI va II gaasosan
	XIV va XVI gaasosan

Demak, berilgan formula aynanteng formula ekan.
XULOSA
Ta’limmuassalaridamatematikadamulohazalar algebrasi interpritatsiyalaridoirmavzuvamasalalaryetarlichauchraydi. Ushbukursishiesamatematikmantiqningyuqoridagitushunchalariniyoritishgaqaratilgan. Bunday mavzudagimisol,o’quvchilaruchunqiyino’zlashtiriluvchibo’libhisoblanadi. Shuninguchunbundaymavzularbo’yichaishlasho’quvchilardanmalakavako’nikmalarnitarkibtoptirishlozimligini talab qiladi.
Ushbukursishidanxulosaqilibshuniaytishmumkinki, biz yuqoridamisollarniyechishdamulohazalaralgebrasi, mulohazalarhisobiformulalarivaularningxossalaridanfoydalandik.
Mulohazalaralgebrasivauninginterpritatsiyasilaridankelibchiqadigannatijalarbizgarele–kontaktsxemalariniyasashgayordamberadi. Mulohazalarhisobivamulohazalaralgebrasiorasidagimunosabatlarmulohazalarhisobidagiformulaningaynan chin(tavtalogiya, umumqiymatli) formula bo’lishiniisbotlashgayordamberadi.
Kurs ishidamulohazalarhisobibo’lishiuchunhisobningsimvollartavsifi, formulalarvakeltiribchiqarishformulalarita’rifidaniboratbo’lishiekanligiko’rsatildi.
Kurs ishinibajarishdadavomidaoliyta’limmuassalaridagidarsliklargabog’liqba’zimavzularnibayonetishdanamunaviydasturiydarsmatnlarinikiritdik.
Ta’limmuassasalariuchunmo’ljallanganmatematikmantiqvadiskretmatematikadarsliklariningmisollarkeltirilganqismlarida biz keltirganxossavaisbotlashlarningba’ziusullaridanfoydalanisho’quvchigaqulaylikyaratadi.
Mazkurkursishidanfoydalanisholiyta’limmuassasalario’quvchilarigashumavzudagidarsliklardaginazariyma’lumotlargaqo’shimcharavishdabo’lib,mavzunichuqurroqtushunishvamalakaviyko’nikmmagaegabo’lishimkoniniberadi.
FOYDALANILGAN ADABIYOTLAR.

1. 
   “O’zbekistonRespublikasiyanadarivojlantirishbo’yichaharakatlarstrategiyasito’g’risida”giO’zbekistonRespublikasiPrezidentiningFarmoni. Toshkent: Adolat 2017.
   
2. 
   I.A.KarimovYuksakma`naviyat-yengilmaskuch.-T.: Sharq, 2008.
   
3. 
   O`zbekistonRespublikasi «Ta`limto`g`risida» Qonuni. Barkamolavlod - O`zbekistontaraqqiyotiningpoydevori. -T.: Sharq, 1997.
   
4. 
   To’rayev H.T. Matematikmantiqvadiskretmatematika. T: TaffakurBo’stoni, 2011
   
5. 
   To’rayev H.T. Mulohazalarhisobivapredikatlarmantiqi. MuammolilektsiyalarkursiSamarqandSamDUnashriyoti, 2003
   
6. 
   Nazarov R.N., Toshpo’latov B.T., Dusumbetov A.D. Algebra vasonlarnazariyasi. T, o’qituvchi 2 qism, 1995 й.
   
7. 
   Куликов Л. Я. Алгебра и теория чисел.Москва: Высш.шк.1979 г. (
   
8. 
   Ziyonet.uz
   
9. 
   Referat.uz
   
10. 
    Lex.uz