Algebra va sonlar nazariyasi fanidan

1.3-§.Formulaning normal shakllari.
Formulaning normal shakllari quyidagi ta’rif asosida aniqlanadi.


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.

Teorema. Mantiq algebrasining ixtiyoriy formulasini KNShga keltirish mumkin.

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.

Teorema. Mantiq algebrasining ixtiyoriy formulasini DNShga keltirish mumkin.

Teorema. Mantiq algebrasining formulasi aynan yolg‘on bo‘lishi uchun uning DNShdagi barcha elementar kon’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.
To‘g‘ri va to‘liq elementar kon’yunksiya va diz’yunksiyalar. Yuqorida teng kuchli almashtirishlar bajarib, mantiq algebrasining berilgan formulasi uchun turli KNShlar va DNShlar topish mumkinligi haqida ma’lumot berilgan edi. Formulalar uchun turli KNShlar va DNShlar orasida muayyan shartlarni qanoatlantiradiganlari muhim hisoblanadi. Quyida shunday shakllar o‘rganiladi.


Ta’rif. Agar elementar kon’yunksiya (diz’yunksiya) ifodasida ishtirok etuvchi har bir elementar mulohaza shu ifodada faqat bir marta uchrasa, u holda bu ifoda to‘g‘ri elementar kon’yunksiya (diz’yunksiya) deb ataladi.

Tarif Agar berilgan elementar mulohazalarning har biri elementar kon’yunksiya (diz’yunksiya) ifodasida faqat bir matra qatnashsa, bu ifoda shu elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya (diz’yunksiya) deb ataladi.

Ta’rif. Agar formulaning KNShi (DNShi) ifodasida bir xil elementar diz’yunksiyalar (kon’yunksiyalar) bo‘lmasa va barcha elementar diz’yunksiyalar (kon’yunksiyalar) to‘g‘ri hamda ifodada qatnashuvchi barcha elementar mulohazalarga nisbatan to‘liq bo‘lsa, u holda bu ifoda mukammal kon’yunktiv normal shakl (mukammal diz’yunktiv normal shakl) deb ataladi.¹