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

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI
VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Algoritmlash va matematik modellashtirish kafedrasi

Diskret tuzilmalari fanidan
MUSTAQIL ISH
MAVZU: Mukammal diz’yunktiv normal shakl(MDNSh), uni tuzish usuliri
Bajardi:072-21 guruh talabasi
Sattorov Bunyod
Toshkent – 2022
Reja:

1. 
   Dezʼyunktiv normal shakllar
   
2. 
   Qisqartirilgan diz’yunktiv normal shaklni yasash algoritmi
   
3. 
   Tupikli diz’yunktiv normal shakllarni yasash algoritmi
   
4. 
   Xulosa
   
5. 
   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. ■