АЛМАТЫ ЭНЕРГЕТИКА ЖӘНЕ БАЙЛАНЫС ИНСТИТУТЫ

ЖОҒАРЫ  МАТЕМАТИКА КАФЕДРАСЫ

 

Дискрет математика

Есептеу-графикалық жұмыстарды орындауға

арналған әдістемелік нұсқаулар мен тапсырмалар

(050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері  үшін)

1 бөлім

 

            ҚҰРАСТЫРУШЫЛАР: Л.Н. Астраханцева, М.Ж.Байсалова.

         Дискрет математика. 050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері  үшін есептеу-графикалық жұмыстарды орындауға арналған әдістемелік  нұсқаулар мен тапсырмалар.

«Есептеу техникасы және бағдарламалық қамтамасыз ету» мамандығы 

бойынша оқитын барлық бөлім студенттеріне арналған есептеу графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар  «Дискрет математика»  пәнінің № 3 типтік есептеулерден тұрады.Бағдарламаның теориялық сұрақтары енгізілген. Типтік варианттың шешімі келтірілген.

 

1 Есептік-графикалық жұмыс 1. Жиындар, катынастар

         1.1 Теориялық  сұрақтар

          1 Жиындар, олардың берілу жолдары. Ішкі жиындар, булеан. Жиындарға қолданылатын қисаптар.

          2 Жиындарға қолданылатын қисаптардың қасиеттері. Жиынның бөліктеуі мен бүркеуі.

          3 Жиындардың тура көбейтіндісі. Қатынастар (унарлы, бинарлы, n-арлы). Бинарлы қатынастардың берілу жолдары. Кері қатынас, қатынастың толықтауышы, тепе-тең қатынас. Бинарлы қатынастардың композициясы.

         4 Бинарлы қатынастың матрицаларының негізгі қасиеттері (рефлексивті, симметриялы, антисимметриялы, транзитивті).

          5 Эквивалентті қатынас. Эквиваленттілік кластары, фактор-жиын.

          6 Реттік қатынас. Лексигографиктік реттілік.

          7 Функционалдық қатынас. Инъекция, сюръекция, биекция. Жиынның қуаты.

1.2 Есептік тапсырмалар

1 Берілген жиынды элементтерін тізу арқылы жазу керек

1 К е с т е

1.1                   

1.2

1.3                                    

1.4

1.5                      

1.6 

1.7                

1.8

1.9                 

1.10

1.11                                        

1.12

1.13                            

1.14

1.15          

1.16

1.17 

1.18

1.19                                    

1.20

1.21                     

1.22

1.23                  

1.24

1.25                

1.26

1.27                                         

1.28

1 кестенің жалғасы

1.29                                

1.30

 

2 Берілген жиынды жалпы қасиеті бойынша арқылы жазу керек

2 К е с т е

2.1                                            

2.2

2.3                                             

2.4

2.5                                            

2.6

2.7                                

2.8 

2.9                                                 

2.10

2.11                                                 

2.12  

2.13                                    

2.14

2.15                                      

2.16        

2.17                                               

2.18  

2.19                                       

2.20  

2.21                                     

2.22

2.23                                        

2.24   

2.25                                       

2.26  

2.27                                      

2.28  

2.29                           

2.30  

 

    3 Берілген жиындар үшін:

a) булеанын құру керек (яғни ішкі жиындардың жиынын);

ә) қандай да бір бүркеуін;

б) қандай да бір бөліктеуін;

в) қандай да бір ішкі жиындардың жиынын

табу керек.

3 К е с т е

3.1  {x,y,z}

3.2   {2,3,4}

3.3  {a,b,c}

3.4  {e,f,g}

3.5  {m,n,p}

3.6  {x,y,z,t}

3.7   {2,3,4,5}

3.8   {a,b,c,d}

3.9  {e,f,g,k}

3.10  {m,n,p,q}

3 кестенің жалғасы

3.11   {6,7,8}

3.12   {v,w,z}

3.13   {5,6,7}

3.14  {b,c,d}

3.15  {4,5,6}

3.16  {y,z}

3.17   {3,4}

3.18   {b,c}

3.19  {f,g}

3.20  {n,p}

3.21  {y,z,t}

3.22   {3,4,5}

3.23   {b,c,d}

3.24  {f,g,k}

3.25  {n,p,q}

3.26   {7,8}

3.27   {w,z}

3.28   {6,7}

3.29  {c,d}

3.30  {5,6}

 

 

4 Берілген А және В жиындары үшін келесі жиындарды табу керек:

а);

ә);

б):

в)

4 К е с т е

 

A

B

 

A

B

4.1 

{a,b,d}

{b,d,e,h}

4.2

{3,4,5,6}

{2,3,6,7,8}

4.3

{d,f,g,h}

{f,g,j,k}

4.4

{7,8,9}

{3,4,5,6,7}

4.5

{r,t,y}

{t,y,u,v}

4.6

{3,4,7,8}

{7,8,9,10}

4.7

{q,w,e}

{w,e,r,t}

4.8

{2,4,6,8}

{1,2,3,4,5}

4.9

{m,n,p,q}

{p,q,u,v}

4.10 

{a,b,c,d}

{b,c,d,e,h}

4.11

{1,3,5,6}

{2,3,6,7,8}

4.12

{f,g,h}

{f,g,j,k}

4.13

{6,7,8,9}

{4,5,6,7}

4.14

{w,r,t,y}

{t,y,u,v,w}

4.15

{3,4,8}

{4,8,9,10}

4.16

{q,w,e,h}

{w,e,r,t}

4.17

{1,4,6,8}

{1,2,3,4}

4.18

{n,p,q}

{p,q,u,v}

4.19 

{b,c,d}

{c,d,e,h}

4.20

{1,3,5}

{2,3,5,7,8}

4.21

{f,g,h,e}

{e,g,j,k}

4.22

{6,7,8}

{5,6,7}

4.23

{w,r,t}

{t,y,v,w}

4.24

{3,4,7}

{4,7,9,10}

4.25

{w,e,h}

{w,r,t}

4.26

{4,6,8}

{1,2,3,4,5,6}

4.27

{n,p,q,w}

{q,u,v,w}

4.28

{1,3,5,7}

{4,5,6,7}

4.29

{e,a,I,o}

{a,j,o}

4.30

{1,3,4,6}

{1,4,9,10}

 

         5 U={0,1,2,3,4,5,6,7,8,9} универсал жиыны берілген. Берілген А және В жиындары үшін табу керек:

а);

ә) ;

б) ;

в)

 

5 К е с т е

 

A

B

 

A

B

5.1 

{1,2,3}

{4,5}

5.2

{3,4,5}

{7,8}

5.3

{7,8,9}

{1,2,3}

5.4

{7,8,9}

{3,4,5}

5.5

{4,5}

{2,3}

5.6

{4,7,8}

{9,0}

5.7

{3,4}

{6,7,8}

5.8

{2,6,8}

{1,2,3}

5.9

{3,5,7}

{1,4,6}

5.10 

{8,9,0}

{1,2,4}

5.11

{1,3,5}

{6,7,8}

5.12

{0,1,2}

{8,9}

5.13

{6,7,8}

{4,5}

5.14

{4,5,6}

{1,2}

5.15

{3,4,8}

{1,9}

5.16

{2,9,5}

{3,4}

5.17

{4,6,8}

{1,2,3}

5.18

{2,3}

{4,7,9}

5.19 

{1,5,6}

{2,3}

5.20

{1,3,5}

{2,7,8}

5.21

{6,7,9}

{5,8}

5.22

{6,7,8}

{5,9}

5.23

{2,4,6}

{3,5}

5.24

{3,4,7}

{8,9}

5.25

{5,6,0}

{1,2}

5.26

{6,8}

{2,3}

5.27

{1,3,4}

{7,8}

5.28

{1,3,5}

{6,7}

5.29

{7,8}

{4,6,9}

5.30

{3,4,6}

{1,9}

 

6 Теңдікті:

а) Эйлер-Венн диаграммасы көмегімен;

ә) жиындарға қолданылатын қисаптар анықтамасын қолдана отырып

дәлелдеу керек.

6 К е с т е

6.1 A\(BC)=(A\B)∩(A\C)

6.2 ABC= A∩C

6.3 A\(B∩C)=(A\B) (A\C)

6.4

6.5 A\(A\B)=A∩B

6.6

6.7 A\B=A\(A∩B)

6.8

6.9 A∩(B\C)=(A∩B)\(A∩C)=(A∩B)\C

6.10

6.11 (A\B)\C=(A\C)\(B\C)

6.12

6.13 AB=A(B\A)

6.14

6.15 (A∩B) (A∩B )=A

6.16

6.17 (AB)∩(AB )=A

6.18

6.19 ( AB)∩A=A∩B

6.20

6.21 (AB)\C=(A\C) (B\C)

6.22

6.23 A\(B\C)=(A\B) (A∩C)

6.24

6.25 A\(BC)=(A\B)\C

6.26 A(B∩C)=(AB)∩(AC)

6.27 (A\B)C=(AC)\B

6.28 (AB)∩A=(A∩B) A=A

6.29 (A\B)C=(AC)                            

6.30

 

 

7 А={a,b,c}, В={1,2,3,4} жиындары және   қатынастары берілген. Табу керек:

a) қатынастар матрицасын;

ә) қатынастар матрицасын графиктік түрде кескіндеу керек;

б) ;

в)  қатынасы рефлексивті, симметриялы, антисимметриялы, транзитивті болатындығын тексеру керек.

 

7 К е с т е

 

7.1

7.2

7.3

7.4

7.5

7.6

7.7

7.8

7.9

7.10

7.11

7.12

7.13

7.14

7.15

7.16

7.17

7.18

7.19

7.20

7.21

7.22

7.23

 

 

7 кестенің жалғасы

7.24

7.25

7.26

7.27

7.28

7.29

7.30

8  қатынасы  жиынында эквиваленттілік қатынасы болатындығын дәлелдеу керек. Эквиваленттілік класы мен фактор-жиынды құру керек.

 

8 К е с т е

 

8.1

8.2

8.3

8.4

8.5

8.6

8.7

8.8

8.9

8.10

8.11

8.12

8.13

8.14

8.15

8.16

8.17

8.18

8.19

8.20

8.21

8.22

8.23

 

8 кестенің жалғасы

8.24

8.25

8.26

8.27

8.28

8.29

8.30

 

9  және  қатынастары берілген:

а) осы қатынастар функциялар болатындығын дәлелдеу керек;

б) композицияларын табу керек;

в) қатынастардың қасиеттерін анықтау керек (инъективтілік, сюръек-тивтілік, биективтілік).

9 К е с т е

9.1

9.2

9.3

9.4

9.5

9.6

9.7

9.8

9.9

9.10

9.11

9.12

9.13

9.14

9.15

9.16

9.17

9.18

9.19

9.20

9  кестенің жалғасы

9.21

9.22

9.23

9.24

9.25

9.26

9.27

9.28

9.29 

9.30

 

1.3 Типтік варианттың шешуі

1 жиынын элементтерін тізу арқылы жазу керек.

Шешуі:

.

2  жиынын жалпы қасиеті бойынша арқылы

жазу керек.

Шешуі:

.

3 Берілген  жиыны үшін:

a) булеанын құру керек (яғни ішкі жиындардың жиынын);

ә) қандай да бір бүркеуін;

б) қандай да бір бөліктеуін;

в) қандай да бір ішкі жиындардың жиынын (бүркеу де, бөліктеу де емес)

табу керек.

Шешуі:

а)  жиыны үш элементтен тұрғандықтан, оның булеаны P    элементтен тұрады:   P  .

ә) мысалы,  -  бүркеуі;

б) мысалы,   немесе - бөліктеуі;

в) мысалы,  - бүркеу де, бөліктеу де емес.

 

4 Берілген  және  жиындары үшін келесі жиындарды табу керек:

а);

ә);

б):

в).

Шешуі:

а) ;

ә) ;

б) ;

в) .

 

5 U={0,1,2,3,4,5,6,7,8,9} универсал жиыны берілген. Берілген  және   жиындары үшін табу керек:

а);

ә) ;

б) ;

в) .

Шешуі:

а)  ;

ә) ;

б)

;

в)

.

6   теңдікті:

а) Эйлера-Венн диаграммасы көмегімен;

ә) жиындарға қолданылатын қисаптар анықтамасын қолдана отырып

дәлелдеу керек.

Шешуі:

а)

              

                        1 Сурет                                                      2 Сурет

                                                                                                                   

                                                                                           

                                                                                     

Сонымен, екі суретте де   және   жиындары кескінделген, екеуі де бір фигураны береді  ( тормен белгіленген);

б) Егер , онда ( және ) ( және ) .

Егер , онда (және ) ( және ), дәлелдеу керегі де осы.

7 ,  және ,  қатынастары берілген:

а)  және  қатынастарының матрицасын құру керек;

б) қатынастарды графиктік түрде бейнелеу керек;

в)  табу керек;

г)  қатынасы рефлексивті, симметриялы, антисимметриялы, транзитивті бола ма, жоқ па анықтау керек.  

         Шешуі:

а)  –   қатынасының матрицасы, мұндағы

Сонымен,  , .

б)

     

                   3 Сурет                                                      4 Сурет

 

Атап өтелік, қатынасты графиктік түрде кескіндеудің басқа да түрлері бар. Мысалы,   қатынасын 5 суреттегідей салуға болады, ал  қатынасын –6 суреттегідей;

         

                           

 

                               5 Сурет                                                      6 Сурет

 

в)  болғандықтан,  , .

,  және

 болғандықтан, -ге толықтауыш келесі қатынас болады .

 және  табылып,  орындалғандықтан, мұндағы , онда

;

г)  қатынасының қасиеттерін оның матрицасы  бойынша анықтаған қолайлы. Бұл матрицаның бас диагоналінде бірлерден де басқа сандар  тұрғандықтан,  - рефлексивті емес,  болғандықтан, ол симметриялы емес. Бас диагоналдан басқа жердегі барлық элементтер нөлден өзге  болғандықтан,  антисимметриялы емес, мысалы, , бірақ , онда  транзитивті емес.

 

8  қатынасы  жиынында эквиваленттілік қатынасы болатындығын дәлелдеу керек. эквиваленттілік класы мен фактор-жиынды құру керек.

         Шешуі:

егер  қатынасы рефлексивті, симметриялы, транзитивті болса, онда ол эквиваленттілік қатынасы болады.  қатынасының  матрицасын құрайық және ол арқылы қатынастың қасиеттерін анықтайық.

. Бұл матрицаның бас диагоналында бірлер тұрғандықтан,  - рефлексивті;  орындалғандықтан, қатынас симметриялы.   құрайық, оның матрицасы

.  қатынасы рефлексивті болу үшін  орындалуы керек немесе егер , онда .  және   қатынастарын, олардың матрицаларын  салыстырсақ,   және  орындалатындығын көреміз. Бұл - рефлексивті болатындығын көрсетеді.

          элементінің эквиваленттілік класы деп  жиыны аталады. Барлық эквиваленттілік кластарының жиыны  -ге қатысты  жиынының фактор-жиыны деп аталады.  жиыны  жиынының бөлікшесі болып табылады.

 жиынының әрбір элементі үшін эквиваленттілік класын құрамыз:

,

,

,

.

Сонымен, .  жиынының -ға қатысты фактор-жиыны: .

9  және  қатынастары берілген:

а) осы қатынастардың функциялар болатындығын дәлелдеу керек;

б)  композицияларын табу керек;

в) қатынастардың қасиеттерін анықтау керек (инъективтілік, сюръек-тивтілік, биективтілік).

Шешуі:

а) егер  немесе кез келген  үшін  орындалатын жалғыз  табылса, онда  қатынасы функция болады.

Біздің жағдайда  және  функция болып табылады, себебі  кез келген  нақты саны үшін ,   сандары табылады және жалғыз болады;

б) ,

.

в) берілген функцияларды инъективтілікке тексереміз. Егер  немесе  орындалса, онда  функциясы инъективті деп аталады.  функциясы үшін инъективтілік шарты орындалмайды, себебі -тің екі мәні сәйкес келетін жалғыз  табылмайды: , бірақ  және  , яғни .

Функция  инъективті, себебі кез келген нақты    үшін  орындалады.

Енді функцияны сюръективтілікке тексереміз.

Егер кез келген  үшін  орындалатын  табылса немесе  қатынасының мәндерінің жиыны  -мен беттессе , онда  функциясы сюръективті деп аталады.

Функция ,  сюръективті емес, себебі мәндерінің жиыны .

Функция ,  сюръективті, себебі .

Егер функция инъективті де, сюръективті де болса, ол биективті деп аталады. Сондықтан   биективті емес функция,  - биективті.

 

 

Әдебиеттер тізімі

1. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.

2.     Москинова Г.И. Дискретная математика. Математика для менеджера

в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.

3.     Новиков Ф.А. Дискретная математика для программистов: Учебник

для вузов. 2-е изд.  – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).

4.     Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. –

М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.

5.     Шапорев С.Д. Дискретная математика. Курс лекций и практических

занятий. – СПб.: БХВ-Петербург, 2006.

6.     Яблонский С.В. Введение в дискретную математику. – М. «Высшая

школа», 2001.

      

 

 

Мазмұны

 

1 Есептік-графикалық жұмыс 3. Аналитикалық геометрия, квадраттық формалар

1.1 Теориялық сұрақтар

1.2 Есептік тапсырмалар

1.3 Типтік варианттың шешуі

Әдебиеттер тізімі