|
4.1 - t a ’ r i f .
Ixtiyoriy
)
,...,
,
(
2
1
n
x
x
x
f
funksiya va unga mos
f
N
to‘plam
berilgan bo‘lsin.
)
,...,
,
(
2
1
n
x
x
x
f
funksiyani realizasiya qiladigan DNShlar ifodasida
qatnashishi mumkin bo‘lgan kon’yunksiyalar, ya’ni
f
n
N
E
\
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.
4.2. Joiz kon’yunksiyalarni topish.
M i s o l .
Berilgan
3
2
1
3
2
1
3
2
1
2
)
,
,
(
x
x
x
x
x
x
x
x
x
f
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
(5)
va unga mos
)}
0
,
1
,
0
(
),
0
,
1
,
1
(
),
1
,
1
,
1
(
),
1
,
0
,
1
(
),
1
,
0
,
0
(
),
0
,
0
,
0
{(
2
f
N
(6)
to‘plam berilgan bo‘lsin.
Joiz kon’yunksiyalarni topish uchun 2-jadvalni tuzamiz.
4.2-jadval
f
n
N
E
\
1 qiymat qabul qiladigan kon’yunksiyalar
)
0
,
0
,
1
(
3
2
1
3
2
3
1
2
1
3
2
1
,
,
,
,
,
,
,
1
x
x
x
x
x
x
x
x
x
x
x
x
)
1
,
1
,
0
(
3
2
1
3
2
3
1
2
1
3
2
1
,
,
,
,
,
,
,
1
x
x
x
x
x
x
x
x
x
x
x
x
U holda (1) dagi kon’yunksiyalardan 4.2-jadvaldagi kon’yunksiyalarni
chetlashtirish natijasida quyidagi joiz kon’yunksiyalarga ega bo‘lamiz:
2
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
1
x
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
,
(7)
3
2
1
x
x
x
,
3
2
1
x
x
x
,
3
2
1
x
x
x
. ■
O’zgaruvchilar soni
n
ta bo‘lganda,
n
3
ta kon’yunksiya va ulardan
2
3
n
ta
)
,...,
,
(
2
1
n
x
x
x
f
funksiyani realizasiya qilishi mumkin bo‘lgan DNSh tuzish
mumkinligini aytgan edik. Demak, berilgan ixtiyoriy
)
,...,
,
(
2
1
n
x
x
x
f
funksiyani
realizasiya qiladigan tupikli (minimal) DNShlarni
2
3
n
ta DNShlar orasidan
izlamasdan, balki
2
DNShlar ichidan izlash kerak degan natijaga keldik, bu yerda
– joiz kon’yunksiyalar soni.
5. Qisqartirilgan diz’yunktiv normal shakl
5 . 1 . Maksimal interval va oddiy implikant tushunchalari.
5.1 - t a ’ r i f .
Agar
f
N
to‘plamning qism to‘plami bo‘lgan
k
N
interval uchun:
1)
f
k
k
N
N
N
1
;
2)
1
k
N
intervalning rangi
k
N
intervalning rangidan kichik
shartlarni qanoatlantiruvchi
1
k
N
interval mavjud bo‘lmasa, u holda
k
N
(
f
N
ga
nisbatan) maksimal interval deb ataladi.
5.1 - m i s o l .
2
1
3
2
1
1
)
,
,
(
x
x
x
x
x
k
,
2
1
3
2
1
2
)
,
,
(
x
x
x
x
x
k
,
2
3
2
1
3
)
,
,
(
x
x
x
x
k
bo‘lsin. U
holda
N
N
k
k
2
3
,
maksimal intervallar bo‘lib,
N
k
1
interval esa
f
N
ning maksimal
intervali bo‘lmaydi, chunki
3
1
k
k
N
N
va
N
k
3
ning rangi
N
k
1
ning rangidan kichik. ■
5.2 - m i s o l .
4-bo’limdagi (4) joiz kon’yunksiyalarga mos kelgan 15ta
intervaldan faqat
N
x
1
va
N
x
2
intervallar va o‘sha bo’lim, (7) dagi 12ta intervaldan
faqat
N
x x
1 2
,
N
x x
1 3
,
3
2
x
x
N
,
3
2
x
x
N
,
2
1
x
x
N
,
3
1
x
x
N
, intervallargina mos ravishda
N
f
1
va
N
f
2
to‘plamlarga nisbatan maksimal intervallar bo‘ladi. ■
5.2 - t a ’ r i f .
f
N
to‘plamning
k
N
maksimal intervaliga mos kelgan
K
kon’yunksiya
f
funksiyaning oddiy implikanti deb ataladi.
Agar
1
k
kon’yunksiyaning hamma ko‘paytuvchilari
k
kon’yunksiyada ham
mavjud bo‘lsa, u holda
1
k
k
N
N
deb yozish mumkin. U holda, ma’lum ma’noda,
f
funksiyaning
k
oddiy implikanti ifodasidan birorta ham ko‘paytuvchini
chetlashtirish mumkin emas, chunki ko‘paytuvchini chetlashtirish natijasida
f
k
N
N
1
munosabatda bo‘lgan
1
k
kon’yunksiyaga ega bo‘lamiz.
Har qanday
k
N
intervalni
)
(
f
k
N
N
maksimal intervalgacha kengaytirish
mumkin.
f
N
to‘plamning hamma maksimal intervallari
0
0
2
0
1
,...,
,
m
k
k
k
N
N
N
(1)
lardan iborat bo‘lsin. U holda
0
0
2
0
1
...
m
k
k
k
f
N
N
N
N
(2)
bo‘ladi, chunki
f
k
N
N
i
0
)
,...,
2
,
1
(
m
i
va
f
N
ning har bir nuqtasi (1) dagi maksimal
intervallarning birortasining elementi bo‘ladi. (2) tenglik quyidagi munosabatga
ekvivalentdir:
0
0
2
0
1
...
m
k
k
k
f
.
(3)
5 . 2 . Qisqartirilgan DNSh tushunchasi.
5.3 - t a ’ r i f .
f
funksiyani hamma oddiy implikantlarining diz’yunksiyasi (3)
qisqartirilgan DNSh deb ataladi.
Demak,
0
0
2
0
1
......
)
(
m
s
k
k
k
f
D
(4)
f
funksiyaning qisqartirilgan DNShi bo‘ladi.
)
(
f
D
s
qisqartirilgan DNSh
f
funksiya orqali bir qiymati aniqlanadi va
f
funksiyani realizasiya qiladi.
5.3 - m i s o l .
4-bo’limdagi (2) formulada berilgan
)
,
,
(
3
2
1
1
x
x
x
f
uchun
maksimal intervallardan iborat
0
2
0
1
1
k
k
f
N
N
N
(5)
Qobiqqa va o‘sha yerdagi (5) formulada berilgan
)
,
,
(
3
2
1
2
x
x
x
f
funksiya uchun
N
N
N
N
N
N
N
f
k
k
k
k
k
k
2
1
2
3
4
5
6
(6)
qobiqqa ega bo‘lamiz. Bu yerda
1
0
1
x
k
,
2
0
2
x
k
,
2
1
1
x
x
k
,
3
1
2
x
x
k
,
3
2
3
x
x
k
,
3
2
4
x
x
k
,
2
1
5
x
x
k
,
3
1
6
x
x
k
. Bu qobiqlarga
2
1
1
)
(
x
x
f
D
s
,
3
1
2
1
3
2
3
2
3
1
2
1
2
)
(
x
x
x
x
x
x
x
x
x
x
x
x
f
D
s
qisqartirilgan DNShlar mos keladi. ■
Do'stlaringiz bilan baham: |
