Samarqand davlat universiteti raqamli texnalogiya fakulteti amaliy matematika va informatikayo’nalishi

3.1. Mulohazalar algebrasi formulasini minimallashtirish muammosi.
3.1.-Ta’rif. O’ziga ekvivalent bo’lgan barcha diz’yunktiv normal shakllarga nisbattan eng kam belgilarga ega bo’lgan diz’yunktiv normal shakl minimal diz’yunktiv normal shakl deyiladi.
Agar DNShda belgilar sonini aniqlashda x_i simvol formulada ikki marta qatnashsa, ikki marta ham sanaladi.

To’g’ri elementar konyunksiyaning rangi deb unga kiruvch belgilar soniga aytiladi.

Har bir formulaga uning chilik to’plami deb ataluvchi
N _f  ₁ ,₂ , ,_n | А₁ ,₂ , ,_n 1 qism to’plam mos keladi.

Aytaylik

АK1K2

 K n

DNSh

bo’lsin,

bu yerda K i

-

elementer

konyunksiyalar. r -rangli

K elementar kon’yunksiyaga mos bo’lgan N K qism to’plam r -rangli

interval deb

nomlanadi.

А

formulaning

har bir

DNSh

kurinishiga NK

, NK

2

, ,NK

n

1

intervallar bilan berilgan

N Ki  N f shartni bajaruvchi N f  N K1 N K 2N K n qoplama mos

keladi.

Bul funksiyasi uchun N K

 N K   N f

shartni bajaruvchi

N K  interval mavjud bo’lmasa,

N _Ki  N _f interval maksimal interval deb ataladi.
Agar N_K1 , N_K2 , , N _Km intervallar N _f qism to’plamning barcha maksimal intervallari bo’lsa, u holda N _f  N_K1 N_K2 N_Km bo’ladi.

3.2.-Ta’rif. f funksiyaning N _f qism to’plami qobig’iga mos bo’lgan barcha maksimal intervallargdan tuzilgan K₁  K₂  K_m DNSh ifodasiga qisqartirilgan DNSh deyiladi.

Istalgan Bul f funksiyasini qisqartirilgan DNShga keltirish mumkin. Buning uchun bir qancha akgoritmlar mavjud.

3.2. Qisqartirilgan Dnshni aniqlash usullari.
3.3.-Ta’rif. Funksiya DNSh cidan ahamiyatsiz o’zgaruvchilarni chetlatish natijasida hosil bo’lgan DNSh, qisqartirilgan DNSh deyiladi.
Qisqartirilgan DNSh ni aniqlashning bir nechta usullari mavjud.
Birinchi bo’lib jadval usulida qisqartirilgan DNSh ni aniqlash algoritmini ko’rib
chiqamiz:
3.1-misol. f x₁, x₂ , x₃  x₂ x₃  x₁x₃  x₁x₂ funksiyani qisqartirilgan DNSh ga keltiring.

	^x3	0,1,1 1,1,1					^x2
	0,0,1			1,0,1
				1,1,0
	0					x1
	Chinlik to’plamini aniqlab olamiz N f				 1,1,0;1,1,1;0,0,1;1,0,1;0,1,1
NK	 0,0,1; 0,1,1; 1,1,1; 1,0,1 va	^NK	2	 1,1,0; 1,1,1 - intervallar barcha maksimal
	1

intervallardir. 3.2.-ta’rifga ko’ra maksimal intervallarga mos konyunksiyalardan tuzilgan DNSh qisqartirilgan DNSh bo’ladi.

6. 
    K₁  K₂  x₃  x₁x₂ - qisqartirilgan DNSh.
   

Ikkinchi algoritm Bleyk usuli deb nomlanadi:

1. 
   DNSh ko’rinishiga keltiramiz;
   

2. 
   xK₁  xK₂  xK₁  xK₂  K₁K₂ - umumlashgan birlashtirish qoidasini qo’llaymiz;
   

3. 
   K₁  K₁K₂  K₁ va K₁  K₁  K₁ -yutilish va idempotentlik qoidasini qo’llaymiz.
   

3.2-misol. A funksiyani qisqartirilgan DNSh ga keltiring.
Umumlashgan birlashtirish qoidasini qo’llab, quyidagi ifodani hosil qilamiz:
x₁x₂  x₁x₃  x₂ x₃  x₂ x₃  x₃  x₁x₃ .
Yutilish qoidasini qo’llab x₁ x₂  x₃ ga ega bo’lamiz.
Uchinchi algoritm Nelson usuli deb nomlanadi:

1. 
   formulani KNSh ga keltiramiz;
   

2. 
   distrubutivlik qonunini qo’llab qavslarni ochamiz;
   

3) yutilish va idumpotentlik qoidalarini qo’llaymiz.
3.3-misol. f x, y, z x  yx  y  z formulani qisqartirilgan DNSh ga keltiring.
Formulaga distrubutivlik qonunini qo’llab qavslarni ochgach xx  xy  xz  yx  yy  yz ko’rinishga keladi. xx  0 , yy  y ekanligidan, xy  xz  yz  y  yz ga ega bo’lamiz.

Yutilish qoidasini qo’llab qisqartirilgan DNShga ega bo’lamiz:

xz  y
To’rtinchi algoritm Mak-Klaski usuli deb nomlanadi.
3.4-misol. f x, y, z, u 1001100111010011 formulani qisqartirilgan DNSh ga keltiring.

	xyzu	f x, y, z, u
1	0000	1
2	0001	0
3	0010	0
4	0011	1
5	0100	1
6	0101	0
7	0110	0
8	0111	1
9	1000	1
10	1001	1
11	1010	0
12	1011	1
13	1100	0
14	1101	0
15	1110	1
16	1111	1

qisqartirilgan DNShga keltirish uchun quyidagi qadamlarni bajaramiz:

I. Funksiyaning birga teng bo’lgan qiymatlarini aniqlaymiz.
0000
0011
0100
0111
1000
1001

1011
1110

1111

35. 
    I-qadamdagi qiymatlarni 1 lar soni ishtirokiga nisbatan o’sih tartibida saralaymiz.
    

61. 
    Oddiy birlashtirish qoidasini qo’llymiz, qavslarda birlashgan satrlar nomerini qo’yamiz.
    

II	III
1. 0000	0-00	(1,2)
2. 0100	-000	(1,3)
3. 1000	100-	(3,5)
3. 0011	0-11	(4,6)
4. 1001	-011	(4,7)
5. 0111	10-1	(5,7)
6.1011	-111	(6,9)
7.1110	1-11	(7,9)
8. 1111	111-	(8,9)

IV. III-qadam natijalarini “-” belgini joylashish o’rniga nisbatan saralaymiz.

V. IV-qadam natijalariga oddiy birlashtirish qoidasini qo’llymiz, qavslarda birlashgan satrlar nomerini qo’yamiz.
VI. V-qadam natijalaridagi bir hil ifodalarni tashlab yuboramiz.

		IV	V
1.		-000	-000
2.		-011	--11	(2,3)
3.		-111	0-00
4.		0-00	--11	(5,6)
5.		0-11	10-1
6. 1-11			100-
7.		10-1	111-

8. 
   100-
   

8. 
   111-
   

VI
-000

0-00

birlashtiramiz 10-1

100-
111-
--11

VII. Hosil bo’lgan oxirgi VI-natijadai ifodalarga mos e.k. larni yozib dizyunksiya amali bilan birlashtiramiz.
IZOH. Birlshtirishda ishtirok etmagan satrlar keying qadamga ko’chirildi.
DNSh= y zu  x zu  x yu  x y z  xyz  zu

Maksimal intervallari

N_k1  {(0,0,0,0),(1,0,0,0)},.k₁  yzu

N_k2  {(0,0,0,0),(0,1,0,0)},.k₂  xzu

N_k3  {(1,0,0,1),(1,0,1,1)},.k₃  x yu

N_k4  {(1,0,0,0),(1,0,0,1)},.k₄  x yz

N _k5  {(1,1,1,0), (1,1,1,1)},.k₅  xyz
N _k6  {(0,0,1,1), (0,1,1,1), (1,0,1,1), (1,1,1,1)},.k₆  zu
Tupikli(Minimal) DNSh qisqartirilgan DNSh dan ayrim elementar konyunksiyalarni chetlatish yo’li bilan hosil qilinadi.
3.4.-Ta’rif. N _f to’plamning maksimal intervallar bilan qoplamsidan birortasini tashlab yuborish mumkin bo’lmasa, bunday qoplama keltirilmaydigan qoplama deyiladi.

Ixtiyoriy minimal DNSh tupikli DNSh bo’ladi.

Bul formulalarini minimallashtirishning umumiy sxemasi quyidagicha:

1. 
   Barcha maksimal intervallar ajratilib qisqartirilgan DNSh tuziladi;
   

2. 
   barcha tupikli DNShlar aniqlanadi;
   

3. 
   tupikli DNShlar orasidan minimal DNSh ta’rifga ko’ra ajratib olinadi. Tupikli DNShlarni qurish algoritmini qarab chiqamiz:
   

	Аx1 , x2 , , xn  formulani qisqartirilgan DNSh shakliga keltiring;
1.	N f chinlik to’plamidagi har bir a j ( j 1,2, , K )	uchun Kij a j 1 ( i 1,2, ,t )
	bo’lgan Kij , , Ktj elementar kon’yunksiyalarni ajratamiz;
2.	quyidagicha ifodani tuzib olamiz
	K11  K12  K1t K21  K22  K2t KK1  KK 2	 KKt		(*)

3. 
   (*) ifodaga distrubutivlik va yutilish qonunini qo’llash natijasida quyidagiga ega bo’lamiz
   

• 
  ^Ki1^Ki 2^Kim
  

Har bir hosil bo’lgan K_i1  K_{i 2}  K_im DNSh f x₁ , x₂ , , x_n  funksiyaning tupikli DNSh bo’ladi.

3.5-misol. Аx, y, z  01111110  chinlik to’plami bilan berilgan formulaning barcha tupikli DNSh larini toping.
Nelson usulini qo’llab qisqartirilgan DNSh ko’rinishini topamiz. Buning uchun MKNSh ko’rinishiga keltirib olamiz:
x  y  zx  y  z 

distrubutivlik qonunini qo’llash orqali quyidagiga ega bo’lamiz:

xy  xz  xy  yz  zx  zy
K₁  xy , K₂  xz , K₃  xy , K₄  yz , K₅  zx , K₆  zy belgilash kiritib olamiz. N _f  0,0,1; 0,1,0; 0,1,1; 1,0,0; 1,0,1; 1,1,0 (*) ifodani tuzib olamiz

K₅  K₆ K₃  K₄ K₃  K₅ K₁  K₂ K₁  K₆ K₂  K₄ 

 K₅  K₃K₆ K₄  K₂K₃ K₁  K₂K₆ 

• 
  K₁K₄K₅  K₁K₂K₃K₅ K₁K₃K₄K₆  K₁K₂K₃K₆ 
  

• 
  K₂K₄K₅K₆  K₂K₃K₅K₆  K₂K₃K₄K₆ 
  

• 
  K₂ K₃K₆  K₁K₄ K₅  K₁K₂ K₃K₅  K₁K₃K₄ K₆  K₁K₂ K₃K₆  K₂K₄ K₅K₆  K₂ K₃K₆
  

Shunday qilib, Аx, y, z formula 6 ta tupikli DNSh ga ega

D₁  K₁  K₄  K₅  xy  yz  zx
D₂  K₁  K₂  K₃  K₅  xy  xz  xy  zx
D₃  K₁  K₂  K₄  K₆  xy  xy  yz  zy
D₄  K₁  K₂  K₃  K₆  xy  xz  xy  zy
D₅  K₂  K₄  K₅  K₆  xz  yz  zx  zy
D₆  K₂  K₃  K₆  xz  xy  zy
Uladan ikkitasi D₁ va D₆ lar minimal DNSh bo’ladi.
Endi minimal DNSh ni topishning implikantlar matritsasi usulini qaraymiz. f x₁ , x₂ , , x_n  Bul funksiyasi uchun f  K₁  K₂  K_t qisqartirilgan DNSh ifodasini topamiz.

Bu funksiya uchun implikantlar matritsasini tuzib olamiz, ushbu matritsaninh satrlariga

~	~	 qiymatlarini quyamiz.
K1 , K2 , , Kt elementar kon’yunksiyalar, ustunlariga N f  a1	, a p

Har bir K i		uchun
qanoatlantiruvchi		~
		^a j
aniqlaymiz.	Matrisada
katagiga +	belgisini

3.6-misol. Аx, y, keltiring.

Yuqoridagi misoldan

~

~

~

~

a1

a2

^a j

^a p

K1

K2

Kij a j 1

ni

K i

+

qiymatlar

to’plamini

ulaning

kesishish

Kt

qo’yamiz.

z  

x  y

 z



 z

formula minimal DNSh

ko’rinishiga

x

y

qisqartirilgan DNSh quyidagi ko’rinishga egaligini bilamiz:

xy  xz  xy  yz  zx  zy
Endi implikantlar matritsasini tuzib olamiz:

0,0,1

0,1,0

0,1,1

1,0,0

1,0,1

1,1,0

x

+

+

y

x

z

+

+

+

+

xy

y

z

+

+

z

+

+

x

z

+

+

y

 y

 z

Jadvaldan ko’rinib

turibdiki,

formulaikkita

minimal

DNSh

ga ega: x

,

y

z

x

xz  xy  zy .