Algebra va sonlar nazariyasi fanidan

5. Ekvivalensiya amali.

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 ga bo’linadi”, q: “berilgan sonning raqamlar yig’indisi 3 ga bo’linadi”.
pq: “Berilgan sonning 3 ga bo’linishi uchun uning raqamlari yig’indisi 3 ga bo’linishi zarur va yetarli”.
Ekvivalensiya amaliga quyidagi rostlik jadvali mos keladi:

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

Har bir qaralayotgan mulohazaga rostlik ustunidan bitta ustun mos keladi. Bu ustunni qiymatlar ustuni deb yuritamiz.

Ta’rif: Qiymatlari ustuni teng bo’lgan mulohazalar o’zaro teng kuchli mulohazalar deyiladi.
Masalan: p=>q va ┐q=>┐ p mulohazalarning teng kuchliligini quyidagi rostlik jadvali orqali ko’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=>q va ┐q=>┐p mulohazalarning ustuni bir xil bo’lgani uchun p=>q=┐q=>┐p bo’ladi.

Ta’rif: universial algebra mulohazalar algebrasi deb yuritiladi.

Tarif: 1. p, q, r,... lar mulohazalar algebrasining formulalaridir.
2. Agar p va q lar mulohazalar algebrasining formulalari bo’lsa, u holda ┐p, pq, pq, p=>q, pq ham formula bo’ladi.
3. Mulohazalar algebrasidagi formulalar faqat 1-va 2-formulalar yordamida tuziladi. Ko’p hollarda 2. yordamida aniqlangan formulalar murakkab formulalar deb yuritiladi.
Murakkab formulaga argumentlari rost yoki yolg’on qiymatni qabul qiluvchi funktsiya deb qarash mumkin.


Ta’rif: x_i, argumentlarning har bir qabul qilishi mumkin bo’lgan barcha 1 va 0 qiymatlar tizimida A(x₁, x₂,…,x_n) formulani ifodalovchi mantiqiy funktsiya rost (yolg’on) qiymatga erishsa, u holda bu formula aynan rost (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 kuchli formulalar va asosiy teng kuchliliklar

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 formulalar teng kuchli bo’lsalar, u holda va lar aynan rost formulalar bo’lishi ravshandir. Aksincha, qandaydir va (bir xil propozitsional o’zgaruvchilarga ega bo’lgan) formulalar uchun va lar aynan rost furmulalar bo’lsa, u holda bo’ladi.

va formulalar teng kuhli formulalar ekanini ko’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

Shunday qilib, bu tengkuchliliklarnda ko’rinadiki, bo’lishi uchun formula aynan rost formula bo’lishi zarur va yetarlidir. Teng kuchli bo’lish munosabati ekvivalent binary munosabat ekanligi ravshandir, ya’ni bu munosabat

1. 
   
   –refleksivlik.
   

2. Agar bo’lsa, u holda bo’ladi ­– simmetriklik va

   
   

3. Agar va bo’lsa, u holda bo’ladi – tanzitivlik xossalariga egadir.

   
   

Teorema: – jumlalar algebrasining ixtiyoriy formulasi, uning qism formulasi bo’lsin. agar bo’lsa, u holda bo’ladi.

Isboti: bo’lgani uchun va formulalar ularda qatnashgan propozitsional o’zgaruvchilar qiymatlarining barcha naborlarida bir xil qiymatlarga erishadilar. va formulalarning qiymatlari yoki bo’lgani uchun yo , yoki hosil bo’ladi. Bu esa ekanini ko’rsatadi.

Teorema: , lar va formulalarning har birida qatnashgan barcha propozitsional o’zgaruvchilar, lar esa ixtiyoriy formulalar bo’lsin. U holda bo’ladi; bunda har bir propozitsional o’zgaruvchi berilgan tengkuchlilikda necha joyda qatnashgan bo’lsa, shuncha joyda mos formula bilan almashtiriladi.

Isbot. tengkuchlilikda qatnashgan har bir propozitisional o’zgaruvchi 1 yoki 0 qiymat qabul qiladi. formula ham o’zida qatnashgan propozitsional o’zgaruvchilar qiymatlarining barcha naborlarida 1 yoki 0 qiymat qabul qiladi. formula tarkibida qatnashgan propozitsional o’zgaruvchilar bo’lsin. bu propozitsional o’zgaruvchilar qiymatlari naborlaridan biri va formulalarning nabordagi qiymatlari nabori bo’lsin. uzunligi bo’lgan nabor propozitsional o’zgaruvchilar qabul qiladigan qiymatlar naborlari srasida mavjuddir. va formulalar ta naborning har birida bir xil qiymatga ega bo’lgani uchun ular naborda ham bir xil qiymat qabul qiladilar.
Yuqorida isbotlangan teoremalardan bevosita quyidagi natijlaar kelib chiqadi.
Agar va bo’lsa, u holda
1)
2)
3)
4)
5)


Ta’rif: Agar formulaning tarkibida faqat konyuksiya, dizyunksiya va inkor operatsiyalari qatnashgan bo’lib, inkor speratsiyasi propozitsional o’zgaruvchilargagina tegishli bo’lsa, u holda bunday formula keltirilgan formula deyiladi.

Misol: keltirilgan formuladir, ammo keltirilgan formula emas, chunki bu formulada implikatsiya operatsiyasi qatnashishi bilan birgalikda inkor operatsiyasi murakkab formula ga tegishlidir.

3.3-Teorema: Mulohazalar algebrasining har bir formulasining yo o’zi keltirilgandir yoki uni teng kuchli keltirilgan formula bilan almashtirish mumkin.
Bu teoremani isbotlash uchun mulohazalar algebrasining asosiy tengkuchliliklari bilan tanishib chiqamiz. Mulohazalar algebrasining tengkuchliliklari quyidagilar:

1. 
   
   (qo’sh inkor tengkuchliligi)
   
2. 
   
   (dizyunksiya kommuntativligi)
   
3. 
   
   (konyuksiyaning kommuntativligi)
   
4. 
   
   (dizyunksiya assotsiativligi)
   
5. 
   
   (konyunksiyaning assotsiativligi)
   
6. 
   
   (dizyunksiyaning konyuksiyaga nisbatan distributivligi)
   
7. 
   
   (konyuksiyaning dizyunksiyaga nisbatan distributivligi)
   
8. 
   
   (dizyunksiya idempotentligi)
   
9. 
   
   (konyuksiyaning idempotentligi)
   
10. 
    
    (yutilish tengkuchliligi)
    
11. 
    
    (yutilish tengkuchliligi)
    
12. 
    
    (de Morgan tengkuchliligi)
    
13. 
    
    (de Morgan tengkuchliligi)
    
14. 
    
    (uchinchini inkor etish tengkuchliligi)
    
15. 
    
    (qarama-qarshilik tengkuchliligi)
    

16. a) , b) c) d)

    
    
17. 
    
    (kontrapozitsiya tengkuchliligi)
    

Bu teng kuchliliklar o’rinli ekanligini rostlik jadvali yordamida bevosita tekshirib ko’rish mumkin. Masalan, XIII tengkuchlilik uchun rostlik jadvalini ko’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 tengkuchliliklarni tashkil etuvchi formulalar keltirilgan formulalar ekanligi ravshandir.

Bundan tashqari,


(1)
tengkuchlilik o’rinli ekanligini rostlik jadvali tuzib ko’rsatish qiyin emas. Yuqorida ekanligi ko’rsatilgan edi. Implikatsiyaning inkor va dizyunksiya bilan almashtirish mumkin ekanligidan quyidagi tengkuchlilikni hosil qilamiz:


(2)
Demak, va formulalar keltirilgan formulalar bilan almashtirilishi mumkin ekan. I, XII, XIII tengkuchliliklar qo’sh inkor hamda dizyunksiya va konyuksiyalar inkorlarini qanday keltirilgan formulalar bilan almashtirish mumkin ekanini ko’rsatadi.

Endi 3.3-teoremaning isbotini keltiramiz. Agar formulaning o’zi keltirilgan formula bo’lsa, u holda teorema isbotlangan bo’ladi.

Agar formula tarkibida implikatsiya va ekvivalentsiya operatsiyalari qatnashgan bo’lsa, ularni (1) va (2) tengkuchliliklar yordamida almashtirish mumkin; formula tarkibida ko’rinishdagi qism formula qatnashgan bo’lsa, uni bilan, yoki ko’rinishidagi qism formula qatnashgan bo’lsa, ularni mos ravishda va formulalar bilan almashtirish mumkin. Bu protsessni yetarli marta tarkrorlab, nihoyat formulaga teng kuchli bo’lgan keltirilgan formulaga kelamiz.
Shunday qilib, 3.3-teoremaga asosan mulohazalar algebrasining har bir formulasini asosiy va boshqa tengkuchliliklar yordamida almashtirib unga teng kuchli formulalar hosil qilish mumkin. Bu shakl alashtirishlar ba’zi bir masalalarni yechishda keng ko’lamda ishlatiladi. Bu yerda formulalarni shakl almashtirsihga oid ba’zi namunalarni keltiramiz.

3.3-misol. formulaning shaklini almashtiring va soddalashtiring.

	(1) ga asosan
	XIII va XII ga asosan
	XII va XII ga asosan
	1 ga asosan
	VII ga asosan
	XIV va II ga asosan
	XVI ga asosan
	VII ga asosan
	XIV ga asosan
	XVI va II ga asosan
	XIV va XVI ga asosan

Demak, berilgan formula aynan teng formula ekan.

“Sheffer shtrixi” va “Pirs strelkasi” operatsiyalariga qaytamiz. Logik operatsiyalarning jadval formularini taqqoslasak:


,


ekanligini ko’ramiz. Demak, “Sheffer shtrixi” va “Pirs strelkasi” inkor va mos ravishda konyuksiya va dizyunksiya orqali ifoda qilinar ekan.