2-bob mulohazalar algebrasi 1-§. Mulohazalar va ular ustida amallar

3.4-teorema.Agar formula tavtologiya bo‘lsa, u holda ham tavtologiya bo‘ladi.
Isbot. Formuladagi propozitsional o‘zgaruvchilarning ixtiyoriy chinlik taqsimoti bo‘lsin. Unda

bo‘ladi. Agar bu qiymatlarni dagi o‘zgaruvchilarning o‘rniga qo‘yilsa, unda ning chinlik qiymati bilan ning chinlik qiymati ustma-ust tushishini aniqlaymiz. Unda, formula tavtologiya bo‘lgani uchun bo‘ladi.

Demak,



formula uchun ham bo‘ladi.
Bu esa teoremani isbotlaydi.
3.5-teorema.Faraz qilaylik, formula formuladan, unda bir yoki bir necha joyda ishtirok etgan qismformulani formula bilan almashtirish natijasida hosil qilingan bo‘lsin. U holda:
1) ╞
bo‘ladi.
2) ╞


bo‘lishidan ╞ bo‘lishi kelib chiqadi.
Isbot. Aytalik, va formulalarda ishtirok etuvchi propozitsional o‘zgaruvchilarning ixtiyoriy chinlik taqsimotida

bo‘lsin. U holda, ravshanki,

bo‘ladi.
Agar

bo‘lsa, u holda

bo‘ladi. Chunki, formula formuladagi ni ga almashtirish natijasida hosil bo‘lganidan, ularning chinlik qiymatlari bir xil bo‘ladi.

Demak,

Endi teoremaning ikkinchi qismini isbotlaymiz.

Shartga ko‘ra
╞

Yuqorida keltirilgan isbotga binoan

╞

bo‘ladi.
Mazkur paragrafda keltirilgan 3.3-teoremadan foydalanib ╞ bo‘lishini topamiz. Teorema isbot bo‘ldi. Endi mulohazalar algebrasida muhim bo‘lgan formulalarning ekvivalentligi tushunchasini keltiramiz.

Ikki va formulalar berilgan bo‘lsin.
3.4-ta’rif.Agar formula tavtologiya bo‘lsa, ya’ni bo‘lsa, u holda va mantiqiy ekvivalent formulalar deyiladi va  kabi belgilanadi.
Ma’lumki, ekvivalentlik tushunchasi to‘plamlarni sinflarga ajratish imkonini berar edi. Bu erda ham formulalarning ekvivalentligi tushunchasi hamma formulalarni sinflarga ajratadi. Turli sinfga mansub bo‘lgan formulalar bir-biriga ekvivalent bo‘lmaydi.
Misol. Ushbu

formulalarni qaraymiz. Ular uchun chinlik jadvalini tuzamiz:

0	0	1	1	1
0	1	1	1	1
1	0	0	1	0
1	1	1	1	1

Bu jadvaldan ko‘rinadiki, formula tavtologiya, ya’ni ╞ ekan.

Bu esa ta’rifga binoan va formulalarning ekvivalent bo‘lishini bildiradi:




3.6-teorema. va formulalar berilgan bo‘lsin.Quyidagi uchta shart o‘zaro teng kuchli:


1) 


2) ╞


3) ╞ ╞


Isbot. Aytaylik, va formulalar mantiqiy ekvivalent bo‘lsin:  . Ta’rifga binoan ╞ bo‘ladi. Bunda, agar va formulalarda ishtiok etuvchi o‘zgaruvchilarning shunday chinlik taqsimoti topilib qolsaki, ular uchun bo‘ladigan bo‘lsa,


yoki

bo‘lib, undan esa

yoki bo‘lib qolishini aniqlaymiz. Bu esa  bo‘lishiga ziddir.Demak, ╞ .
Shunday qilib,  bo‘lganda ╞ bo‘lishi ko‘rsatildi.
Aytaylik, ╞ bo‘lsin. U holda kon’yunksiyaning chinlik jadvaliga ko‘ra ixtiyoriy chinlik taqsimotida


,
bo‘ladi. Demak,
╞

Unda 3.1-teoremaga muvofiq

╞ ╞
bo‘ladi.
Shunday qilib ╞ bo‘lishidan bo‘lishi kelib chiqadi.
Endi ╞ va ╞ bo‘lsin. Unda 3.1-teoremaga ko‘ra hamda formulalar tavtologiya bo‘lmasin deb qaraydigan bo‘lsak, u holda shunday chinlik taqsimot topilib, bo‘lib qoladi.
Bunda bo‘ladigan bo‘lsa, ╞ bo‘lishiga zid, bo‘lsa, ╞ bo‘lishiga zid natijalarga kelamiz.
Demak, ixtiyoriy chinlik taqsimotda ya’ni ╞ bo‘ladi. Ta’rifga binoan  bo‘ladi.
Shunday qilib, 3.6-teoremadagi 1, 2 va 3 tasdiqlar orasida

munosabat borligi ko‘rsatildi. Bu esa teoremani isbotlaydi.

Yuqorida, tavtologiya haqida keltirilgan teoremalardan foydalanib ba’zi xulosalarni chiqaramiz.
Ma’lumki,
(
ya’ni
(

bo‘ladi.

Agar va larni mos ravishda va larga almashtirilsa, unda 4-teoremaga binoan
(

formula ham tavtologiya bo‘ladi. Boshqacha qilib aytganda ixtiyoriy va formulalar uchun formula ( formulaga mantiqan ekvivalent bo‘ladi.

Agar va formulalarning o‘zida amali qatnashgan bo‘lsa, unda 3.5-teoremadan foydalanib ularni va amallar bilan almashtiramiz.
Shunday qilib amali qatnashgan formula, faqat va amallari qatnashgan, ayni paytda unga mantiiqan ekvivalent bo‘lgan formulaga ega bo‘linar ekan.
Agar biror formulada amal ishtirok etsa, uni 3.6-teoremadan foydalanib va amallar bilan, so‘ngra amalni esa va amallar orqali ifodalab, amal qatnashgan formuladan , va amallar qatnashgan, ayni paytda unga mantiqan ekvivalent bo‘lgan formulaga kelamiz.
Demak, mantiqiy ekvivalentlik aniqligida, barcha formulalarda va amallar ishtirok etmaydi deb qarash mumkin ekan.
Misol. Quyidagi ikki teoremani qaraylik:
1-teorema. Agar vektorlar sistemasi chiziqli -chiziqli fazoda erkli bo‘lsa, u holda ixtiyoriy sistema osti ham chiziqli erkli bo‘ladi.
2-teorema. Agar vektorlar sistemasining biror-bir sistema osti chiziqli bog‘liq bo‘lsa, u holda vektorlar sistemasining o‘zi chiziqli bog‘liq bo‘ladi.
Quyidagi belgilashlarni kiritamiz:


-vektorlar sistemasi chiziqli erkli.
ning ixtiyoriy sistema osti chiziqli erkli.

U holda 1-teorema , 2-teorema esa ko‘rinishni oladi.

Bu ikki teorema bir-biriga mantiqan ekvivalentmi?
Mulohazalar algebrasida ixtiyoriy lar uchun

bo‘ladi. Chinlik jadvalini tuzib,
╞ ( )
bo‘lishini ko‘rsatish qiyin emas.
Agar deb olinsa, unda yuqoridagi ikki teoremaning bir-biriga mantiqan ekvivalent ekanligi kelib chiqadi. Demak, bu ikki teoremadan birini isbotlash kifoya.