Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

Aynan chin, aynan yolg‘on va bajariluvchi formulalar

Tavtologiya². Tabiiyki, berilgan formula uning tarkibida qatnashuvchi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlari ucnun turli qiymatlar, jumladan, faqat ch yoki faqat yo qiymat qabul qilishi mumkin.
1- ta’rif. Tarkibidagi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlarida faqat ch qiymat qabul qiluvchi formula tavtologiya deb ataladi.

1- jadval
yo	yo	ch	yo	ch
yo	ch	ch	yo	ch
ch	yo	yo	yo	ch
ch	ch	ch	ch	ch

Tavtologiya iborasi o‘rnida aynan chin yoki doimo chin formula iborasi ham qo‘llanilishi mumkin. Tavtologiya, ko‘pincha, yoki 1 bilan belgilanadi. Aynan chin formula, uning tarkibida ishtirok etuvchi o‘zgaruvchilarning qiymatlariga bog‘liq bo‘lmay, faqat bitta (ch) qiymat qabul qiladi.
Berilgan formula tavtologiya bo‘lishi yoki bo‘lmasligi, odatda, uning qiymatlar jadvali vositasida aniqlanadi.
1- misol. formula tavtologiyadir. Bu tasdiqning
to‘griligini tekshirish uchun 1- jadvalni ( formulaning qiymatlar jadvalini) tuzamiz.
Berilgan formula uning tarkibida qatnashuvchi va elementar mulohazalarning mumkin bo‘lgan hamma qiymatlar satrlarida faqat ch qiymat qabul qilgani uchun, u tavtologiyadir, ya’ni . ■
2- misol. Berilgan formulani tekshirish uchun uning chinlik jadvalini tuzamiz (2- jadvalga qarang).

2- jadval
yo	yo	yo	ch	ch	ch	ch	yo
yo	yo	ch	ch	ch	ch	ch	ch
yo	ch	yo	ch	ch	ch	ch	yo
yo	ch	ch	ch	ch	ch	ch	ch
ch	yo	yo	yo	yo	yo	ch	yo
ch	yo	ch	yo	yo	yo	ch	ch
ch	ch	yo	yo	ch	ch	ch	yo
ch	ch	ch	yo	ch	ch	ch	ch

2- jadvaldan ko‘rinib turibdiki, , lekin . ■
Aynan chin formulalar mantiqda katta ahamiyatga ega bo‘lib, ular mantiq qonunlarini ifodalaydi. Shu sababli, mantiq algebrasida yechilish muammosi deb yuritiluvchi chekli miqdordagi amal yordamida berilgan ixtiyoriy mantiqiy formulaning aynan chin yoki aynan chin emasligini aniqlash masalasi dolzarb muammo hisoblanadi. Yechilish muammosi faqat mulohazalar algebrasi uchungina emas, balki boshqa mantiqiy sistemalar uchun ham qo‘yilishi mumkin. Yechilish muammosi mulohazalar algebrasi uchun ijobiy hal etiladi (ushbu bobning 5- paragrafiga qarang). Tabiiyki, yechilish muammosini turli usullar yordamida hal qilish mumkin. Bunday usullarni yechuvchi usullar deb ataymiz. Yechuvchi usul iborasi o‘rnida yechish protsedurasi yoki yechish algoritmi iboralari ham qo‘llanilishi mumkin.
Yechish protsedurasi sifatida chinlik jadvalini qo‘llashga asoslangan usulni olish mumkin, chunki chinlik jadvali har bir muayan formula uchun yechilish muammosini to‘liq hal qilish imkonini beradi. Agar berilgan formulaga mos keladigan chinlik jadvalning oxirgi ustunida faqat ch bo‘lsa, u holda bu formula aynan chin, agar oxirgi ustunda hech bo‘lmaganda bitta yo bo‘lgan holda esa formula aynan chin emas bo‘ladi. Tabiiyki, amalda bu usulni har doim ham qo‘llab bo‘lavermaydi, chunki u quyidagi asosiy kamchilikka ega. Agar berilgan formulada ta elementar o‘zgaruvchi mulohazalar qatnashsa, u holda bu formulaning chinlik jadvali ta satrga ega bo‘ladi va ning yetarli katta qiymatlarida bu yechish protsedurasini, hattoki, komp’yuter yordamida ham oxiriga yetkazib bo‘lmaydi. Lekin, prinsip jihatdan olganda, “chinlik jadvalini qo‘llashga asoslangan usul yordamida chekli miqdordagi amallar bajarib yechilish muammosini hal qilish mumkin” degan tasdiq to‘g‘ridir. Ushbu bobning keyingi paragraflarida boshqa bir yechuvchi protsedurani keltiramiz. Bu yechuvchi protsedura berilgan formulani normal shaklga keltirish usuliga asoslangan. Normal shakllar matematik mantiqning boshqa masalalarida ham ishlatiladi.