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

Mantiq algebrasi funksiyasini minimallashtirish muammosiga ekvivalent qoplamalar haqidagi geometrik masala. Mantiq algebrasi funksiyasi ni minimallashtirish (minimizasiyalash) muammosiga ekvivalent bo‘lgan qoplamalar haqidagi geometrik masala quyidagicha qo‘yiladi. Berilgan to‘plamning ( , ) intervallardan iborat shunday qobig‘ini topish kerakki, uning rangi eng kichik bo‘lsin, ya’ni qaralayotgan masala
(5)
topish masalasiga keladi.
Demak, mantiq algebrasi funksiyasini minimallashtirish masalasini ikki formada ko‘rish mumkin: birinchisi – analitik formada, ikkinchisi – geometrik formada. Shuning uchun adabiyotda ikki til ishlatiladi: analitik va geometrik. Ayrim hollarda ikki tilning kombinatsiyasidan foydalaniladi. Masalan, kon’yunksiyani interval va DNShni qoplama deb ataydilar.

Joiz (ruxsat etilgan) kon’yunksiyalar
Joiz kon’yunksiya tushunchasi. Ma’lumki, o‘zgaruvchilardan ta elementar kon’yunksiya va ta diz’yunktiv normal shakl tuzish mumkin. Masalan, bo‘lsa, ya’ni o‘zgaruvchilardan
, , , , , , , , , , , ,
, , , , , , , (1)
, , , , ,
elementar kon’yunksiya tuzish mumkin. Ammo, bu elementar kon’yunksiyalarning hammasi ham berilgan ixtiyoriy funksiyani realizasiya qiladigan diz’yunktiv normal shakllarning ifodasida ishtirok etavermaydi. Shuning uchun “ ta kon’yunksiyalarning qaysilari funksiyaning DNShda ishtirok qiladi?” degan masalani yechishga to‘g‘ri keladi. Buning uchun, birinchi navbatda, to‘plamning elementlarida 1 qiymat qabul qiladigan kon’yunksiyalarni topish kerak bo‘ladi. Masalan,
(2)
bo‘lsin. U holda
(3)
bo‘ladi. Demak, 1- jadvalga ega bo‘lamiz.

1- jadval
	1 qiymat qabul qiladigan kon’yunksiyalar
(0,0,0)
(0,0,1)

Ikkinchi navbatda, (1) kon’yunksiyalar orasidan 1-jadvaldagi kon’yunksiyalarni chetlashtiramiz, chunki funksiyaga ((3)ga qarang) to‘plam mos kelgani uchun 1-jadvaldagi kon’yunksiyalar (2) funksiyani realizasiya qiladigan diz’yunktiv normal shakllar ifodasida umuman qatnashmaydi. Bu operatsiya natijasida funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi mumkin bo‘lgan (qatnashishga ruxsat etilgan, qatnashishga joiz) kon’yunksiyalarga ega bo‘lamiz:
, , , , , ,
, , , , , (4)
, , , .
Shunday qilib, kon’yunksiyadan 15tasining berilgan funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi joiz ekan.
1- ta’rif. Ixtiyoriy funksiya va unga mos to‘plam berilgan bo‘lsin. funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi mumkin bo‘lgan kon’yunksiyalar, ya’ni to‘plamning nuqtalarida 1 qiymatga ega bo‘lgan kon’yunksiyalardan tashqari qolgan hamma kon’yunksiyalar joiz kon’yunksiyalar deb ataladi.
Masalan, (4) dagi hamma kon’yunksiyalar joiz kon’yunksiyalar bo‘ladi.