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

4- misol. 2- teoremadan foydalanib va formulalarning tavtologiya bo‘lishi yoki bo‘lmasligini tekshiramiz. Berilgan formulalarni, mos ravishda, va bilan belgilab, (1) va (2) formulalardan foydalansak, quyidagi KNShlarga ega bo‘lamiz:
,
.
Bu formulalarning KNShlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashgani uchun berilgan formulalarning har biri tavtologiyadir. ■
3- teorema. Mantiq algebrasining ixtiyoriy formulasini DNShga keltirish mumkin.
Isboti. 1- teoremaga ko‘ra mantiq algebrasining ixtiyoriy formulasini
qandaydir KNShga keltirish mumkin, bu yerda ( ) – elementar dizyunksiyalar. Ravshanki, elementar dizyunksiyning inkori elementar konyunksiya bo‘ladi. Shuning uchun berilgan formulaning inkori

DNShda bo‘ladi, bunda ( ) – elementar konyunksiyalar. ■
4- teorema. Mantiq algebrasining formulasi aynan yolg‘on bo‘lishi uchun uning DNShdagi barcha elementar kon’yunktiv hadlarida kamida bittadan
elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.
Isboti. 1. Mantiq algebrasining formulasi ko‘rinishda berilgan bo‘lib, uning DNShidagi barcha ( ) elementar kon’yunktiv hadlarida kamida bittadan elementar mulohaza bilan birga bu mulohazaning inkori ham qatnashsin. Berilgan formulaning ( ) hadida qandaydir elementar mulohaza bilan birga uning inkori ham qatnashgan bo‘lsin deb faraz qilaylik. U holda va teng kuchliliklarga asosan barcha uchun o‘rinlidir. Demak, agar barcha uchun hadlar tarkibida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham qatnashgan bo‘lsa, u holda , ya’ni aynan yolg‘on bo‘ladi.
2. Mantiq algebrasining formulasi aynan yolg‘on bo‘lsin. U holda formulaning inkori doimo chin bo‘ladi. Shuning uchun, 2- teoremaga asosan, formulaning KNShdagi barcha elementar diz’yunksiyalarida kamida bittadan elementar mulohaza bilan birga uning inkori ham topiladi. Demak, fopmulaning DNShdagi barcha kon’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashadi. ■
4- teorema berilgan formulaning doimo yolg‘on bo‘lishi yoki bo‘lmasligini, chinlik jadvaliga murojaat qilmasdan, aniqlash imkonini bergani uchun, uni yolg‘onlik alomati deb atash mumkin.