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

3 . 7 - m i s o l . N _А2 {(0,0,0),(0,0,1),(1,0,1),(1,1,1),(1,1,0),(0,1,0)} to‘plamga mos
А₂ (x₁ , x₂ , x₃ ) formulaning MKNShni 0 ga teng bo’lgan qiymatlaridan foydalanib yozamiz:
А₂ (x₁ , x₂ , x₃ )  (x₁  x₂  x₃ )(x₁  x₂  x₃ ) .

Algoritmning 2-va 3-qadamlarini bajaramiz:

(x₁  x₂  x₃ )(x₁  x₂  x₃ )  x₁ x₁  x₁ x₂  x₁ x₃  x₁ x₂  x₂ x₂

• 
  x₂ x₃  x₁ x₃  x₂ x₃  x₃ x₃  x₁ x₂  x₁ x₃  x₁ x₂  x₂ x₃  x₁ x₃  x₂ x₃ . Qisqartirilgan DNSh quyidagi ko‘rinishda bo‘ladi:
  

D_s ( f₂ )x₁ x₂  x₁ x₃  x₁ x₂  x₂ x₃  x₁ x₃  x₂ x₃ .

3 . 8 - m i s o l . Quyidagi formula berilgan bo‘lsin:
А₁ (x₁ , x₂ , x₃ )  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃ .

Bu formulaga

N_А1 {(0,0,0),(0,1,1),(0,1,0),(1,0,1),(1,1,0),(1,1,1)}
to‘plam mos keladi. Formulaning MKNSh ko‘rinishi
f₁ (x₁ , x₂ , x₃ )  (x₁  x₂  x₃ )(x₁  x₂  x₃ ) _.

Algoritmning 2-va 3-qadamlarini bajaramiz:

(x₁  x₂  x₃ )(x₁  x₂  x₃ )  x₁ x₁  x₁ x₂  x₁ x₃  x₁ x₂ 

• 
  x₂ x₂  x₂ x₃  x₁ x₃  x₂ x₃  x₃ x₃ 
  

 x₁  x₁ x₂  x₁ x₃  x₁ x₂  x₂  x₂ x₃  x₁ x₃  x₂ x₃ 

 x₁  x₁ x₃  x₂  x₂ x₃  x₁ x₃  x₂ x₃ 

• 
  x₁  x₂  x₁ x₃  x₂ x₃  x₁  x₂ .
  

Demak, formulaning qisqartirilgan DNSh quyidagicha bo‘ladi:

D_s ( f₁ )  x₁  x₂ .

Bajarish uchun laboratoriya topshiriqlari.

1. 
   Mak-Klaski usuli bilan minimal DNSh ko’rinishiga keltiring:
   

14.(o’rin) Аx, y,z,u  1011011100111011;

	x	y	z	u	Аx, y,z,u ;
1	0	0	0	0	1
2	0	0	0	1	0
3	0	0	1	0	1
4	0	0	1	1	1
5	0	1	0	0	0
6	0	1	0	1	1
7	0	1	1	0	1
8	0	1	1	1	1
9	1	0	0	0	0
10	1	0	0	1	0
11	1	0	1	0	1
12	1	0	1	1	1
13	1	1	0	0	1
14	1	1	0	1	0
15	1	1	1	0	1
16	1	1	1	1	1

.Qisqartirilgan DNSHga keltirish uchun quyidagi qadamlarni bajaramiz:

1.funksiyani birga teng bo’lgan qiymatini aniqlaymiz.

0	0	0	0
0	0	1	0
0	0	1	1
0	1	0	1
0	1	1	0
0	1	1	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	1	0
1	1	1	1

2.1- qadamdagi qiymatlarni 1lar soni ishtirokiga ko’ra o’sish tartibda saralaymiz.

0	0	0	0
0	0	1	0
0	0	1	1
0	1	0	1
0	1	1	0
0	1	1	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	1	0
1	1	1	1

3.Oddiy birlashtirish qoidasini qo’llaymiz va qavslarda birlashtirilgan satr nomerlarini qo’yamiz.

0	0	-	0	(1,2)
0	0	1	-	(2,3)
0	-	1	0	(2,5)
0	-	1	1	(3,6)
-	0	1	1	(3,8)
0	1	-	1	(4,6)
0	1	1	-	(5,6)
-	1	1	1	(6,11)
1	0	1	-	(7,8)
1	-	1	0	(7,10)
1	-	1	1	(8,11)
1	1	-	0	(9,10)
1	1	1	-	(10,11)

4.3-qadam natijalarni “-” belgi joylashuviga qarab saralaymiz.

-	0	1	1
-	1	1	1
0	-	1	0
0	-	1	1
1	-	1	0
1	-	1	1
0	0	-	0
0	1	-	1
1	1	-	0
0	0	1	-
0	1	1	-
1	0	1	-
1	1	1	-

5.4- qadam natijalarini .Oddiy birlashtirish qoidasini qo’llaymiz va qavslarda birlashtirilgan satr nomerlarini qo’yamiz.

-	-	1	1	(1,2)
0	-	1	-	(3,4)
-	-	1	0	(3,5)
-	-	1	1	(4,6)
1	-	1	-	(5,6)
0	-	1	-	(10,11)
-	0	1	-	(10,12)
1	-	1	-	(12,13)
0	0	-	0
0	1	-	1
1	1	-	0

6.5-qadam natijalardagi bir xil ifodalarni tashlab yuboramiz.

-	0	1	-
0	0	-	0
0	1	-	1
1	1	-	0

7.hosil bo’lgan 6-natijadagi ifodalarga e.klarni yozib dizyunksiya amali bn birlashtiramiz.

DNSH = ;

3. 
   Minimal DNSh ko’rinishiga keltiring:
   

14. 
    f x, y, z, u  0010110101110111
    

Foydalanilgan adabiyotlar

1. 
   Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012
   

2. 
   Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. - М.: Наука. -1969.
   

3. 
   Яблонский С. В. Введение в дискретную математику. – М.: Наука, 1986.
   

4. 
   Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физ.-мат. литература, 1995.
   

5. 
   E. Urunbayev, N. Abdullayeva, Sh. Daliyev, I.Rabbimov. Diskret matematika va matematik mantiq fanidan amaliy mashg’ulotlar. O’quv qo’llanma. SamDU nashriyoti,
   

2019 y., 201 b.

6. 
   Э. Урунбаев. Дискретная математика (УМК), Самарканд, Университет, 2019.
   

Internet saytlar:

1. 
   http://dimacs.rutgers.edu/
   

2. 
   http://epubs.siam.org/sam-bin/dbq/toclist/SIDMA
   

3. 
   http://www.vsppub.com/journals/jn-DisMatApp.html
   

.