Mukammal diz’yunktiv va kon’yuktiv normal formalar

Quyidagi belgilashni kiritamiz:

Quyidagi belgilashni kiritamiz:

(1)

1-ta`rif. propozitsional o`zgaruvchilar, 1 va 0 lardan tuzilgan tizim bo`lsa, u holda formula elementar kon`yunksiya deyiladi (bunda propozitsional o`zgaruvchilar takrorlangan bo`lishi ham mumkin).

1-misol. formulalar elementar kon`yunksiyalardir.

2-ta`rif. Elementar kon`yunksiyalarning har qanday diz`yunktiyasi diz`yunktiv normal forma (DNF) deyiladi.

2-misol. formula 1-misolda keltirilgan elementar kon`yunksiyalardan tuzilgan DNF dir.

•  

3-ta`rif. Agar elementar kon`yunksiyaga har bir propozitsional o`zgaruvchi (inkor belgisi qatnashganini ham e`taborga olsak) bir martadan ortiq kirmagan bo`lsa, bunday elementar kon`yunksiya to`g`ri elementar kon`yunksiya deyiladi.

3-ta`rif. Agar elementar kon`yunksiyaga har bir propozitsional o`zgaruvchi (inkor belgisi qatnashganini ham e`taborga olsak) bir martadan ortiq kirmagan bo`lsa, bunday elementar kon`yunksiya to`g`ri elementar kon`yunksiya deyiladi.

3-misol. formulalar to`g`ri elementar kon`yunksiyalardir. 2-misolda keltirilgan formulaning dastlabki ikkita hadi to`g`ri elementar kon`yunksiyadir.

4-ta`rif. propozitsional o`zgaruvchilardan tuzilgan to`g`ri elementar kon`yunksiyadagi har bir propozitsional o`zgaruvchi bu kon`yunksiyaga faqat bir marta kirgan bo`lsa, bunday elementar kon`yunksiya o`zgaruvchilarga nisbatan to`liq elementar kon`yunksiya deyiladi.

4-misol. Elementar kon`yunksiyalar o`zgaruvchilardan tuzilgan bo`lsin. U holda formulalar to`liq elementar kon`yunksiyalardir.

•  

5-ta`rif. Tarkibida bir hil elementar kon`yunksiyalar bo`lmagan hamda barcha elementar kon`yunksiyalar o`zgaruvchilarga nisbatan to`g`ri va to`liq bo`lgan DNF o`zgaruvchilarga nisbatan mukammal diz`yunktiv normal forma (MDNF) deyiladi.