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

3- misol. formulani KNShga keltirish maqsadida 2- misoldagidek ish yuritib




teng kuchliliklarga ega bo‘lamiz. Shunday qilib, formula berilgan formula uchun KNSh bo‘lib, u ikkita va diz’yunktiv hadlarning kon’yunksiyasidan iboratdir. ■
2- teorema. Mantiq algebrasining formulasi tavtologiya bo‘lishi uchun uning KNShidagi barcha elementar diz’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.
Isboti. 1. Mantiq algebrasining formulasi
(5)
ko‘rinishda berilgan bo‘lib, uning KNShidagi barcha ( ) elementar diz’yunktiv hadlarida kamida bittadan elementar mulohaza bilan birga bu mulohazaning inkori ham qatnashsin. Faraz qilaylik, formulaning ( ) hadida qandaydir elementar mulohaza bilan birga uning inkori ham qatnashgan bo‘lsin. 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 tavtologiya bo‘ladi.
2. Mantiq algebrasining (5) ko‘rinishda ifodalangan formulasi tavtologiya bo‘lsin. Teorema tasdig‘iga teskari tasdiq o‘rinli deb faraz qilamiz. Ya’ni, formula tarkibidagi ( ) elementar diz’yunktiv hadlardan hech bo‘lmaganda bittasida hech qaysi bir elementar mulohaza o‘zining inkori bilan birga qatnashmagan bo‘lsin. Berilgan formulaning KNShidagi hech qaysi bir elementar mulohaza o‘zining inkori bilan birga qatnashmagan biror ( ) elementar diz’yunktiv hadini tahlil qilamiz. Bu formulada hech qaysi bir elementar mulohaza o‘zining inkori bilan birga qatnashmaganligi sababli formula uchun tuzilgan chinlik jadvalining shunday satri topiladiki, unda barcha elementar mulohazalar yo qiymatga ega bo‘ladi va formula tarkibidagi barcha diz’yunksiya amallarini bajarish natijasi ham shu satr uchun yo bo‘ladi. Shuning uchun, kon’yunksiya amalining ta’rifiga ko‘ra, formula uchun tuzilgan chinlik jadvalining o‘sha satridagi qiymat yo bo‘ladi. Bu esa teorema isbotining “ formula tavtologiya bo‘lsin” degan shartiga ziddir. ■
2- teorema berilgan formula tavtologiya yoki tavtologiya emasligini, chinlik jadvaliga murojaat qilmasdan, aniqlash imkonini beradi. Shuning uchun 2- teorema chinlik alomati deb yuritiladi. Chinlik alomatiga ko‘ra, berilgan formulaning tavtologiya bo‘lishi yoki bo‘lmasligini aniqlash uchun, uni KNShga keltirish kerak. Agar formulaning KNShdagi barcha elementar dizyunksiyalar ifodasida hech bo‘lmaganda bitta elementar mulohaza o‘zining inkori bilan birga qatnashgan bo‘lsa, u holda bu formula tavtologiya, aks holda esa tavtologiya emasligi aniqlanadi.