1. Formulalar. Teng kuchli formulalar. Aynan chin, aynan yolg‘on va bajariluvchi formulalar

Aynan chin, aynan yolg‘on va bajariluvchi formulalar
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. 
   t a ’ r i f. Tarkibidagi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlarida faqat ch qiymat qabul qiluvchi formula tavtologiya deb ataladi.
   

1-jadval

x	y	x  y	x  (x  y)	x  (x  y)  y
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, J 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- m i s o l . D  x  (x  y)  y formula tavtologiyadir. Bu tasdiqning to‘griligini 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 x  (x  y)  y  J . ■
2- m i s o l . Berilgan B  (x  y)  (x  y)  z formulani tekshirish uchun uning chinlik jadvalini tuzamiz
2-jadval

x	y	z	¯x	¯x  y	x  y	(¯x  y)  (x  y)	B
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, (x  y)  (x  y)  J , lekin B J . ■
   

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 n ta elementar o‘zgaruvchi mulohazalar qatnashsa, u holda bu formulaning chinlik jadvali n 2 ta satrga ega bo‘ladi va n 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.
Aynan yolg‘on formulalar. Formula uning tarkibida ishtirok etuvchi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlari ucnun faqat yo qiymat qabul qilishi ham mumkin.

3. 
   t a ’ r i f. Tarkibidagi 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 ucnun aynan yolg‘on formulani J 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. 
   t a ’ r i f. Agar А va В formulalar uchun А  В formula tavtologiya bo‘lsa, u holda В formula А formulaning mantiqiy xulosasi deb ataladi.
   

4- t a ’ r i f. Agar А va В formulalar uchun А  В formula tavtologiya bo‘lsa, u holda berilgan formulalar mantiqiy ekvivalent formulalar deb ataladi.
1-t e o r e m a . Agar А va А  В formulalarning har biri tavtologiya bo‘lsa, u holda В formula ham tavtologiya bo‘ladi.
I s b o t i . А va А  В formulalarning har biri tavtalogiya bo‘lsin. Teorema tasdig‘ining teskarisini, ya’ni А va В formulalar tarkibiga kiruvchi o‘zgaruvchilarning hech bo‘lmaganda bitta qiymatlar satrida В formula yo qiymat qabul qilsin deb faraz qilamiz. U holda, А formula tavtologiya bo‘lganligi uchun, o‘zgaruvchilarning o‘sha qiymatlar satr(lar)ida А ch qiymat qabul qiladi. Shu sababli А  В formula yo qiymat qabul qiladi. Bu esa А  В formula tavtologiyadir degan tasdiqqa qarama-qarshidir. Demak, В tavtologiyadir. ■
2-t e o r e m a . Agar А1 formula tarkibiga bir yoki ko‘p marta kirgan А formula o‘rniga В formulani qo‘yish natijasida В1 formula hosil qilinsa, u holda ( ) ( ) А  В  А1  В1 formula tavtologiya bo‘ladi.
I s b o t i . Agar tarkibidagi o‘zgaruvchilarning biror qiymatlar satrida А va В formulalar turli qiymatlarga ega bo‘lsa, u holda o‘sha qiymatlar satrida А  В formulaning qiymati yo bo‘ladi va, natijada, А1  В1 formulaning qiymati qanday bo‘lishidan qat’iy nazar, ( ) ( ) А  В  А1  В1 formula ch qiymat qabul qiladi.
Agar tarkibidagi o‘zgaruvchilarning qandaydir qiymatlar satrida А va В formulalar bir xil qiymat qabul qilsa, u holda o‘sha qiymatlar satrida А1 va В1 formulalar ham bir xil qiymat qabul qiladi, chunki teoremaning shartiga asosan В1 formula А1 formuladan А formulaning o‘rniga В formulani qo‘yish natijasida hosil qilingan. Demak, bu holda А  В va А1  В1 formulalarning ikkalasi ham ch qiymat qabul qiladi. Shuning uchun ( ) ( ) А  В  А1  В1 formula ham ch qiymat qabul qiladi.
Shunday qilib, yuqorida qaralgan mumkin bo‘lgan ikkala holda ham ( ) ( ) А  В  А1  В1 formula ch qiymat qabul qiladi. Demak, ( ) ( ) А  В  А1  В1 formula tavtologiya bo‘ladi. ■
2- teoremaga ko’ra, agar А1 formula tarkibiga bir yoki ko‘p marta kirgan А formula o‘rniga В formulani qo‘yish natijasida В1 formula hosil qilinsa, u holda А va В formulalarning mantiqiy ekvivalentligidan А1 va В1 formulalarning ham mantiqiy ekvivalentligi chiqadi.