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

3-§. TAVTOLOGIYA TUSHUNCHASI.
TAVTOLOGIYA HAQIDA TEOREMALAR

Propozitsional o‘zgaruvchilar larga bog‘liq M.A.F. berilgan bo‘lsin.

Agar ixtiyoriy lar uchun yoki bo‘lsa, ketma-ketlik propozitsional o‘zgaruvchilarning chinlik taqsimoti deyiladi.
Demak, propozitsional o‘zgaruvchilar larning chinlik taqsimoti 0 va 1 simvollardan tuzilgan ixtiyoriy ketma-ketlikni ifodalar ekan.
3.1-ta’rif. Agar formulada o‘zgaruvchilarning shunday chinlik taqsimoti topilib, bo‘lsa, bajariluvchi (radlanuvchi) formula deyiladi.
Masalan, formulada sababli u radlanuvchi formula, sababli u bajariluvchi formula bo‘ladi.
3.2-ta’rif. Agar formula propozitsional o‘zgaruvchi larning ixtiyoriy chinlik taqsimotida bir (nol) qiymat qabul qilsa, aynan rost yoki tavtologiya aynan (aynan yolg‘on yoki ziddiyat) deyiladi.
Masalan, Ushbu
formulada bo‘lgani uchun formula tavtologiya bo‘ladi.
quyidagi  formulada esa
bo‘lganligi sababli formula ziddiyat bo‘ladi.
Odatda formulani tavtologiya ekani, uni oldiga ushbu belgini qo‘yish bilan ifodalanib, ╞ kabi yoziladi.
Faraz qilaylik, hamda

formulalar berilgan bo‘lsin.

3.3-ta’rif. Agar larning ixtiyoriy chinlik taqsimoti lar uchun





bo‘lishidan ekani kelib chiqsa, u holda formula formulalarning mantiiqiy natijasi deyiladi. Uni
╞
kabi belgilanadi.
Masalan, hamda bo‘lsin. Ravshanki,

lar uchun hamda bo‘ladi. Demak,
╞
ya’ni
╞
bo‘ladi. (Bu misolda larning qolgan chinlik taqsimotlari uchun bo‘lganligi uchun va larning bu qiymatlari qaralmadi).
Ushbu
misolda bo‘lganligi sababli formula formulaning mantiqiy natijasi bo‘lmaydi (ya’ni ╞ munosabat o‘rinli emas).
Endi tavtologiya haqidagi teoremalarni keltiramiz.
3.1-teorema. Agar formula

formulalarning mantiqiy natijasi bo‘lsa, formula tavtologiya bo‘ladi va aksincha. Ya'ni:



va aksincha
.
Isbot. Aytaylik, formula formulalarning mantiqiy natijasi bo‘lsin: ╞ bo‘ladi. Shunga qaramasdan formula tavtologiya bo‘lmasin deb faraz qilaylik. Unda propozitsional o‘zgaruvchilar larning shunday chinlik taqsimoti topiladiki, bo‘lib, bo‘ladi.
Ravshanki,
bo‘lishidan
bo‘lishi kelib chiqadi. Ayni paytda
bo‘lishi ╞
ga ziddir. Bu ziddiyatni kelib chiqishiga sabab formula tavtologiya bo‘lmasin deb qilingan farazdir. Demak, ╞ bo‘lsa ╞ bo‘lar ekan.
Aytaylik, formula tavtologiya bo‘lsin: ╞
Unda implikatsiyaning chinlik jadvaliga binoan, biror chinlik taqsimoti uchun

bo‘lishidan, albatta bo‘lishi kelib chiqadi. Binobarin,
bo‘ladi. Bundan esa, formula formulalarning mantiqiy natijasi ekanini topamiz: ╞ . Teorema isbot bo‘ldi.
3.2-teorema. formulaning ziddiyat bo‘lishi uchun formulaning tavtologiya bo‘lishi zarur va etarli.
Bu teoremaning isboti ravshan.
3.3-teorema. Agar , hamda formulalar tavtologiya bo‘lsa, u holda formula ham tavtologiya bo‘ladi.
Isbot. Teskarisini faraz qilaylik, ya’ni teoremaning sharti bajarilsa ham formula tavtologiya bo‘lmasin. U holda larning shunday chinlik taqsimoti topiladiki, bo‘ladi.
hamda lar tavtologiya bo‘lganligi uchun
, bo‘ladi.
Ikkinchi tomondan , bo‘lishidan ekanligini topamiz. Bu esa ning tavtologiya ekanligiga zid. Teorema isbot bo‘ldi.
Faraz qilaylik, formula berilgan bo‘lsin. Bu formuladagi larning o‘rniga mos ravishda

formulalarni qo‘yish natijasida hosil bo‘lgan formulani deylik: