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

3- ta’rif. Agar va formulalar uchun formula tavtologiya bo‘lsa, u holda formula formulaning mantiqiy xulosasi deb ataladi.
4- ta’rif. Agar va formulalar uchun formula tavtologiya bo‘lsa, u holda berilgan formulalar mantiqiy ekvivalent formulalar deb ataladi.
4- misol. 1- misolda formula tavtologiya bo‘lishini ko‘rgan edik (1- jadvalga qarang). Shu sababli, 3- ta’rifga ko‘ra, formula formulaning mantiqiy xulosasidir.
2- jadvalga ko‘ra (2- misolga qarang) va formulalar mantiqiy ekvivalent formulalar bo‘ladi hamda, shu bilan birga, formula formulaning mantiqiy xulosasidir degan tasdiqlar to‘g‘ridir. Albatta, formula formulaning mantiqiy xulosasidir degan tasdiq ham to‘g‘ri. ■
1- teorema. Agar va formulalarning har biri tavtologiya bo‘lsa, u holda formula ham tavtologiya bo‘ladi.
Isboti. 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- teorema. Agar formula tarkibiga bir yoki ko‘p marta kirgan formula o‘rniga formulani qo‘yish natijasida formula hosil qilinsa, u holda
formula tavtologiya bo‘ladi.
Isboti. 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, formulaning qiymati qanday bo‘lishidan qat’iy nazar, 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 va formulalar ham bir xil qiymat qabul qiladi, chunki teoremaning shartiga asosan formula formuladan formulaning o‘rniga formulani qo‘yish natijasida hosil qilingan. Demak, bu holda va formulalarning ikkalasi ham ch qiymat qabul qiladi. Shuning uchun formula ham ch qiymat qabul qiladi.
Shunday qilib, yuqorida qaralgan mumkin bo‘lgan ikkala holda ham formula ch qiymat qabul qiladi. Demak, formula tavtologiya bo‘ladi. ■
2- teoremaga ko’ra, agar formula tarkibiga bir yoki ko‘p marta kirgan formula o‘rniga formulani qo‘yish natijasida formula hosil qilinsa, u holda va formulalarning mantiqiy ekvivalentligidan va formulalarning ham mantiqiy ekvivalentligi chiqadi.