Matematika

II BOB. Tavtologiya, aynan chin, aynan yolg’on va bajariluvchi formulalar.

2. Tavtologiya, aynan yolg’on va bajariluvchi formulalar.

Tavtologiya. Tabiiyki, berilgan formula uning tarkibida qatnashuvchi elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlari uchun turli qiymatlar, jumladan, faqat ch yoki faqat yo qiymat qabul qilishi mumkin.

1. 
   T a ‘ r i f. Tarkibida elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlarida faqat ch qiymat qabul qiluvchi formula tavtologiya deb ataladi.
   

2.1.1-jadval

x	y
0	0	1	0	1
0	1	1	0	1
1	0	0	0	1
1	1	1	1	1

Tavtologiya iborasi o’rnida aynan chin yoki doimo chin formula iborasi ham qo’llanilishi mumkin. Tavtologiya ko’pincha J yoki I 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.

2.1.1-misol. formula tavtologiyadir. Bu tasdiqning to’g’riligini tekshirish uchun 1-jadvalni (D formulaning qiymatlar jadvalini) tuzamiz.

Berilgan D formula uning tarkibida qatnashuvchi x va y elementar mulohazalarning mumkin bo’lgan hamma qiymatlar satrlarida faqat ch qiymat qabul qilgani uchun, u tavtologiyadir, ya’ni

2.1.2-misol. Berilgan formulani tekshirish uchun uning chinlik jadvalini tuzamiz (2.1.2-jadvalga qarang).

x	y	z					B
0	0	0	1	1	1	1	0
0	0	1	1	1	1	1	1
0	1	0	1	1	1	1	0
0	1	1	1	1	1	1	1
1	0	0	0	0	0	1	0
1	0	1	0	0	0	1	1
1	1	0	0	1	1	1	0
1	1	1	0	1	1	1	1

2.1.2-jadvaldan ko’rinib turibdiki lekin

Aynan chin formulalar mantiqda kata 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. Tabiiyki yechilish muammosini turli usullar yoqdamida hal qilish mumkin. Bunday usullarni yechuvchi usullar deb ataymiz. Yechuvchi usul iborasi o’rnida yechish rotsedurasi yoki yechish algoritmi iboralari ham qo’llanilishi mumkin.

Yechish protsedurasi sifatida chinlik jadvalini qo’llashga asoslanganusulni olish mumkin, chunki chinlik jadvali har bir muayyan formula uchun yechilish muammosini to’liq hal qilish imkonini beradi. Agar berilgan formulaga mos keladigan chinlik jadvalining oxirgi ustinida hech bo’lmaganda bitta yo bo’lgan holda esa formula aynan chin emas bo’ladi. Tabiiyki, amalda bu usulni har doim qo’llab bo’lavermaydi, chunki u quyidagi asosiy kamchilikka ega. Agar berilgan formulada n ta elementar o’zgaruvchi mulohazalar qatnashsa, u holda bu formulaning chinlik jadvali ta satrga ega bo’ladi va n ning yetarli kata qiymatlarida bu yechish protsedurasini, hattoki komputer yordamida ham oxiriga yetkazib bo’lmaydi. Lekin prinsip jihatdan olgandda “chinlik jadvalini qo’llashga “ asoslangan usul yordamida chekli miqdordagi amallar bajarib yechilish muammosini hal qilish mumkin degan tasdiq to’g’ridir.

Aynan yolg’on formulalar. Formula uning tarkibida ishtirok etuvchi elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlari uchun faqat yo qiymat qabul qilishi ham mumkin.

1. 
   T a ‘ r i f . Tarkibida elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlarida faqat yo qiymat qabul qiluvchi formula aynan yolg’on (doimo yolg’on) yoki bajarilmaydigan formula deb ataladi.
   

1-va 2- ta’riflardan yaqqol ko’rinib turibdiki, aynan yolg’on formula tavtologiyaning inkoridir, va aksincha, tavtologiya aynan yolg’on formulaning inkoridir. Shuning uchun aynan yolg’on formulani yoki 0 bilan belgilash joizdir.

Aynan yolg’on formula ham, aynan chin formula kabi, o’z tarkibida ishtirok etuvchi o’zgaruvchilarning qiymatlariga bog’liq emas, u faqat bitta (yo) qiymat qabul qiladi. Berilgan formulaning bajarilmaydigan formula bo’lishi yoki bo’lmasligi ham, odatda, uning qiymatlar jadvali yordamida aniqlanadi.

2.1.3-misol. formula aynan yolg’on formuladir. Haqiqatan ham asosiy chinlik jadvallari yordamida A formulaning chinlik jadvalini tuzsak, natijada 2.1.3-jadvalga ega bo’lamiz.

x	y
0	0	1	1	1	0	0
0	1	1	1	1	0	0
1	0	0	0	0	1	0
1	1	0	1	1	0	0

2.1.3-jadvalning oxirgi ustiniga ko’ra

2.1.3-ta’rif. Agar A va B formulalar uchun formula tavtologiya bo’lsa, u holda B formula A formulaning mantiqiy xulosasi deb ataladi.