Mavzu: Bul funksiyalarining o’zgaruvchilar bo’yicha yoyilmasi. Mulohazalar algebrasi formulasining normal shakllari. Mukammal diz’yunktiv va konyunktiv normal shakllar. Elementar kon’yunksiya va elementar diz’yunksiya tushunchalari

Formulaning normal shakllari. Formulaning normal shakllari quyidagi ta’rif asosida aniqlanadi.
2- ta’rif. Berilgan formulaning kon’yunktiv normal shakli deb unga teng kuchli va elementar diz’yunksiyalarning kon’yunksiyalaridan tashkil topgan formulaga, diz’yunktiv normal shakli deb esa unga teng kuchli va elementar kon’yunksiyalarning diz’yunksiyalaridan tashkil topgan formulaga aytiladi.
“Kon’yunktiv normal shakl” iborasini, qisqacha, KNSh, “diz’yunktiv normal shakl” iborasini esa, DNSh deb yozamiz.
(3) formula DNShning kon’yunktiv hadi, (4) formula esa KNShning diz’yunktiv hadi deb ham yuritiladi.
1- va 2- ta’riflarga ko‘ra, teng kuchli almashtirishlar bajarib, mantiq algebrasining ixtiyoriy formulasi uchun turli KNShlar va DNShlar topilishi mumkin.
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.