|
3.3 - m i s o l .
2-bo’limdagi 2.1-jadval bilan berilgan
)
,
,
(
3
2
1
x
x
x
f
funksiya
uchun
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
D
,
1
3
2
2
x
x
x
D
diz’yunktiv
normal
shakllar
topilgan
edi.
Bu
DNShlarga
)}
1
,
1
,
1
(
),
0
,
1
,
1
(
),
1
,
0
,
1
(
),
0
,
0
,
1
(
),
0
,
0
,
0
{(
f
N
to‘plamning quyidagi ikkita qoplamasi mos
keladi:
5
4
3
2
1
k
k
k
k
k
f
N
N
N
N
N
N
,
,
2
0
1
0
k
k
f
N
N
N
bu yerda
)}
0
,
0
,
0
{(
1
k
N
,
)}
0
,
0
,
1
{(
2
k
N
,
)}
1
,
0
,
1
{(
3
k
N
,
)}
0
,
1
,
1
{(
4
k
N
,
)}
1
,
1
,
1
{(
5
k
N
,
)}
0
,
0
,
1
(
,
)
0
,
0
,
0
{(
0
1
k
N
,
)}
1
,
1
,
1
(
,
)
0
,
1
,
1
(
,
)
1
,
0
,
1
(
,
)
0
,
0
,
1
{(
0
2
k
N
. Birinchi qoplama beshta
nuqtadan, ikkinchisi esa qirra va ikki o‘lchovli yoqdan iborat.
N
k
i
intervalning rangi
i
r
bo‘lsin (u
i
K
kon’yunksiyaning rangiga teng). U holda
r
r
i
i
s
1
(4)
qoplamaning rangi
deb ataladi.
3.2. Mantiq algebrasi funksiyasini minimallashtirish muammosiga
ekvivalent qoplamalar haqidagi geometrik masala.
Mantiq algebrasi funksiyasi
)
,...,
,
(
2
1
n
x
x
x
f
ni minimallashtirish (minimizasiyalash) muammosiga ekvivalent
bo‘lgan qoplamalar haqidagi geometrik masala quyidagicha qo‘yiladi. Berilgan
s
k
k
k
f
N
N
N
N
...
2
1
to‘plamning
s
k
k
k
N
N
N
,...,
,
2
1
(
f
k
N
N
j
,
s
j
,...,
2
,
1
)
intervallardan iborat shunday qobig‘ini topish kerakki, uning
r
rangi eng kichik
bo‘lsin, ya’ni qaralayotgan masala
min
min
r
r
i
i
s
1
(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.
4. Joiz (ruxsat etilgan) kon’yunksiyalar
4.1.
Joiz
kon’yunksiya
tushunchasi.
Ma’lumki,
n
x
x
x
,...,
,
2
1
o‘zgaruvchilardan
n
3
ta elementar kon’yunksiya va
2
3
n
ta diz’yunktiv normal shakl
tuzish mumkin. Masalan,
3
n
bo‘lsa, ya’ni
3
2
1
,
,
x
x
x
o‘zgaruvchilardan
1
,
1
x
,
2
x
,
3
x
1
x
,
2
x
,
3
x
,
2
1
x
x
,
3
1
x
x
,
3
2
x
x
,
2
1
x
x
,
2
1
x
x
,
3
1
x
x
,
3
1
x
x
3
2
x
x
,
3
2
x
x
,
2
1
x
x
,
3
1
x
x
,
3
2
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
,
(1)
3
2
1
x
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
elementar kon’yunksiya tuzish mumkin. Ammo, bu elementar kon’yunksiyalarning
hammasi ham berilgan ixtiyoriy
)
,
,
(
3
2
1
x
x
x
f
funksiyani realizasiya qiladigan
diz’yunktiv normal shakllarning ifodasida ishtirok etavermaydi. Shuning uchun “
n
3
ta kon’yunksiyalarning qaysilari
)
,...,
,
(
2
1
n
x
x
x
f
funksiyaning DNShda ishtirok
qiladi?” degan masalani yechishga to‘g‘ri keladi. Buning uchun, birinchi navbatda,
f
n
N
E
\
to‘plamning elementlarida 1 qiymat qabul qiladigan kon’yunksiyalarni
topish kerak bo‘ladi. Masalan,
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
z
y
x
f
)
,
,
(
1
(2)
bo‘lsin. U holda
)}
1
,
1
,
1
(
),
0
,
1
,
1
(
),
1
,
0
,
1
(
),
0
,
1
,
0
(
),
1
,
1
,
0
(
),
0
,
0
,
0
{(
1
f
N
(3)
bo‘ladi. Demak, 4.1-jadvalga ega bo‘lamiz.
4.1-jadval
Е
N
n
f
\
1
1 qiymat qabul qiladigan kon’yunksiyalar
(0,0,0)
z
y
x
z
y
z
x
y
x
z
y
x
,
,
,
,
,
,
,
1
(0,0,1)
z
y
x
z
y
z
x
y
x
z
y
x
,
,
,
,
,
,
,
1
Ikkinchi
navbatda,
(1)
kon’yunksiyalar
orasidan
4.1-jadvaldagi
kon’yunksiyalarni chetlashtiramiz, chunki
)
,
,
(
z
y
x
f
funksiyaga
N
f
1
((3)ga qarang)
to‘plam mos kelgani uchun 4.1-jadvaldagi kon’yunksiyalar (2) funksiyani
realizasiya qiladigan diz’yunktiv normal shakllar ifodasida umuman qatnashmaydi.
Bu operatsiya natijasida
)
,
,
(
1
z
y
x
f
funksiyani realizasiya qiladigan DNShlar
ifodasida qatnashishi mumkin bo‘lgan (qatnashishga ruxsat etilgan, qatnashishga
joiz) kon’yunksiyalarga ega bo‘lamiz:
x
,
y
,
xy
,
xz
,
y
x
,
z
x
,
yz
,
y
x
,
z
y
,
xyz
,
z
xy
,
(4)
yz
x
,
z
y
x
,
z
y
x
,
z
y
x
.
Shunday qilib,
27
3
3
kon’yunksiyadan 15tasining berilgan
)
,
,
(
z
y
x
f
funksiyani realizasiya qiladigan DNShlar ifodasida qatnashishi joiz ekan.
Do'stlaringiz bilan baham: |
