Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

I. Manfiy emasligi haqidagi aksioma. Har qanday DNSh uchun .
II. Monotonligi haqidagi aksioma (ko‘paytmaga nisbatan). Agar bo‘lsa, u holda
. (7)
III. Qavariqligi haqidagi aksioma (qo‘shishga nisbatan). Agar va bo‘lsa, u holda
. (8)
IV. Invariantlik haqidagi aksioma (izomorfizmga nisbatan). Agar DNSh DNShdan o‘zgaruvchilarni qayta nomlash (aynan tenglashtirishsiz) usuli bilan hosil qilingan bo‘lsa, u holda
Diz’yunktiv normal shakllar uchun soddalik indekslari deb ataluvchi quyidagi belgilashlarni kiritamiz.
1. – berilgan DNShdagi o‘zgaruvchilar harflarining soni.
2. – berilgan DNShdagi elementar kon’yunksiyalar soni.
3. – berilgan DNShdagi inkor ( ) simvollari soni.
, va indekslar yuqorida keltirilgan aksiomalarni qanoatlantiradi.
2- misol. 1- misoldagi va DNShlar berilgan bo‘lsin. Ravshanki, va , ya’ni DNSh o‘zgaruvchilar harflarining soni indeksiga nisbatan DNShga qaraganda soddaroqdir. va DNShlar uchun va bo‘lgani uchun DNSh elementar kon’yunksiyalar soni indeksiga nisbatan ham DNShga qaraganda soddaroqdir. va , ya’ni DNSh inkor simvollari soni indeksi uchun ham DNShga nisbatan soddaroq ekan. ■
Ma’lumki, o‘zgaruvchilar to‘plamidan ta elementar kon’yunksiya tuzish mumkin (“bo‘sh” kon’yunksiyaga 1 konstanta mos qilib qo‘yilgan). Bundan o‘z navbatida to‘plam elementlaridan ta diz’yunktiv normal shakl tuzish mumkinligi kelib chiqadi.
3- ta’rif. Agar funksiyani realizatsiya qiluvchi DNSh indeksga nisbatan minimal bo‘lsa, u holda bunday DNSh ga nisbatan minimal DNSh, indeksga nisbatan minimal bo‘lgan DNSh eng qisqa diz’yunktiv normal shakl deb ataladi.
Bundan keyin indeksga nisbatan minimal bo‘lgan DNShni minimal diz’yunktiv shakl deb ataymiz.