Formulalarning normal shakllari Elementar kon’yunksiya va elementar diz’yunksiya tushunchalari

1- misol. Distributivlik va idempotentlik qonunlariga asoslanib, formulaning kon’yunktiv normal shakllari, masalan, , va formulalar, formula uchun esa diz’yunktiv normal shakllar, masalan, va formulalar bo‘lishiga ishonch hosil qilish qiyin emas. ■

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.