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

1- teorema. Mantiq algebrasining ixtiyoriy formulasini KNShga keltirish
mumkin.
Isboti. Mantiq algebrasining ixtiyoriy formulasini tahlil qilib, agar berilgan formula KNShda bo‘lmasa, u vaqtda quyidagi ikkita hollardan biri ro‘y berishini ta’kidlaymiz:
a) berilgan formuladagi elementar mulohazalar faqat , va belgilar bilangina birlashtirilgan bo‘lsada, belgilar eng so‘nggi amallarni ifodalamaydi;
b) berilgan formula tarkibidagi elementar mulohazalar , va belgilardan tashqari va/yoki belgilar bilan ham birlashtirilgan.
a) holda, diz’yunksiyaning kon’yunksiyaga nisbatan distributivlik xossasini ifodalovchi teng kuchlilikdan foydalanib, ((1)ga qarang) berilgan formulani unga teng kuchli formulaga keltiramiz.
b) holda, (1) teng kuchliliklardan foydalanib, berilgan formulaga teng kuchli va tarkibidagi elementar mulohazalari faqat , va belgilar bilangina birlashtirilgan formulani hosil qilamiz. Agar hosil qilingan formula KNShda bo‘lmasa, u vaqtda u, albatta, a) holda ifodalangan shaklda bo‘ladi. a) hol uchun ifodalangan jarayonni chekli marta qo‘llagandan so‘ng (zarur bo‘lsa (2) teng kuchliliklardan ham foydalanib) berilgan formulaga teng kuchli KNShdagi formulani hosil qilamiz. ■
Teoremaning yuqorida keltirilgan isboti konstruktiv xususiyatga ega, ya’ni
bu isbotdan mantiq algebrasining berilgan formulasi uchun KNShni hosil qilishda algoritm sifatida foydalanish mumkin.
2- misol. Ushbu formulaning biror KNShini topish talab etilgan bo‘lsin. Berilgan formulani bilan belgilab (1) va (2) formulalardan foydalansak, quyidagilarga ega bo‘lamiz:


.
Demak, . Berilgan formulaning topilgan KNShida va o‘zgaruvchilarning bittagina elementar diz’yunksiyasi bor, ya’ni berilgan formula
uchun KNSh bittagina diz’yunktiv haddan iboratdir. ■