I kirish II. Asosiy qism matematik mantiq funksiyalarining minimallashtirish muammosi masalasining qo‘yilishi

I. Manfiy emasligi haqidagi aksioma. Har qanday DNF uchun .

II.Monotonligi haqidagi aksioma (ko‘paytmaga nisbatan). Agar bo‘lsa, u vaqtda

(7)

III.Qavariqligi haqidagi aksioma (qo‘shishga nisbatan). Agar va bo‘lsa, u vaqtda

(8)

IV. Invariantlik haqidagi aksioma (izomorfizmga nisbatan). Agar R¹ DNSH R DNSH dan o‘zgaruvchilarni qayta nomlash (aynan tenglashtirishsiz) usuli bilan hosil etilgan bo‘lsa, u vaqtda

Dizyunktiv normal shakllar uchun mavjud bo‘lgan soddalik indekslarini keltiraylik.

1. dizyunktiv normal shakldagi o‘zgaruvchilar harflarining soni. Masalan, bizning misolimizdagi va lar uchun va , ya’ni bu indeksga nisbatan DNSH ga qaraganda soddaroqdir.

2. dizyunktiv normal shakldagi elementar konyunktsiyalar soni. va lar uchun va . Bu indeksga nisbatan ham ga qaraganda soddaroqdir.

3. dizyunktiv normal shakldagi inkor (-) simvolining soni. va lar uchun va , ya’ni bu indeks uchun ham ga nisbatan soddaroq ekan.

, va indekslar yuqorida keltirilgan aksiomalarni qanoatlantiradi.

Ma’lumki, o‘zgaruvchilar to‘plamidan 3ⁿ ta elementar konyunktsiya tuzish mumkin (“bo‘sh” konyunktsiyaga 1 konstanta mos qilib qo‘yilgan). Bundan o‘z navbatida to‘plam elementlaridan ta dizyunktiv normal shakl tuzish mumkinligi kelib chiqadi.