Некоммерческое акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра высшей математики

 

 

 

ДИСКРЕТНАЯ МАТЕМАТИКА

 Методические указания к расчетно-графической работе

для студентов специальностей

5В070400 – Вычислительная техника и программное обеспечение,

5В070300 – Информационные системы всех форм обучения

1-часть

 

Алматы 2012       

          СОСТАВИТЕЛИ:  Астраханцева  Л.Н., Байсалова  М.Ж.  Дискретная математика. Методические указания к расчетно-графическим работам для  студентов  специальности 5В070400 – Вычислительная техника и  программное обеспечение, 5В070300 – Информационные системы всех форм обучения. 1-часть -Алматы: АУЭС, 2012.- 23 стр.

 

Настоящие методические указания  к расчетно-графическим работам для студентов специальности 5В070400 – Вычислительная техника и  программное обеспечение, 5В070300 – Информационные системы всех форм обучения составлены в соответствии с программой дисциплины «Дискретная   математика» по разделу «Множества, отношения». Содержатся варианты заданий, приведены необходимые теоретические сведения. Типовые задачи даются с подробными решениями.

Ил. 10, табл. 10, библиогр. – 11 назв.

 

Рецензент: доцент кафедры ЭПП Башкиров М.В.

 

Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2012 г.

 

ã   НАО «Алматинский университет энергетики и связи»,  2012 г.

                                                                      

Введение 

   Дисциплина «Дискретная математика» посвящена той области математики, которая используется при решении задач на компьютере в терминах аппаратных средств и программного обеспечения с привлечением организации символов и манипуляции данными. 

   В результате изучения дисциплины студенты должны овладеть основными методами  формализации рассуждений,  получить  навыки моделирования  для использования их в программировании, при решении задач в области искусственного интеллекта, при доказательстве правильности программ, при построении математических моделей.

 

   1  Расчетно-графическая работа 1. Множества, отношения

 

   Цель изучения разделов «Множества, отношения» обусловлена необходимостью получения знаний для изучения курса «Алгоритмы и структуры данных», «Теория языков и автоматов» и других не менее важных дисциплин.

 

1.1           Расчётные  задания

 

1 Данное множество задать:

  а) перечислением элементов;

  б) общим свойством.

 

Т а б л и ц а 1

№

а)

б)

1.1

                                            

1.2

                                    

1.3

                                             

1.4

                                

1.5

                                              

1.6

                                                 

1.7

                                    

1.8

                                      

1.9

                                               

1.10

                       

 

 

продолжение таблицы 1

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.29

 

 

1.30

 

 

 

2 Пусть U={1,2,3,4,5,6,7,8,9,10} - универсальное множество. Для данных множеств А, В, С найти

а);

б);

в);

г);

д);

е) ;

ж) ;

з) .

 

Т а б л и ц а 2

№

A

B

C

2.1

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

{4,5,6,7,8,9,10}

{2,4,6,8,10}

2.2

{2,3,4,5,6,7,8}

{5,6,7,8,9,10}

{1,3,5,7,9}

2.3

{3,4,5,6,7,8,9}

{6,7,8,9,10}

{1,2,4,6,8,9}

2.4

{6,7,8,9,10}

{1,2,4,6,8,9}

{3,4,5,6,7,8,9}

2.5

{4,5,6,7,8,9,10}

{2,4,6,8,10}

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

2.6

{1,3,5,7,9}

{2,3,4,5,6,7,8}

{5,6,7,8,9,10}

2.7

{1,2,3,5,7,9,10}

{3,4,5,6,7,8}

{2,4,6,7,8,9}

2.8

{6,7,8,9,10}

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

{3,4,5,6,7,8}

2.9

{1,3,5,7,8,9}

{2,4,6,8,10}

{7,8,9,1,2,3}

2.10

{2,4,6,7,8,9}

{1,3,5,6,7,8}

{8,9,10,1,2,3}

2.11

{2,4,6,8,10}

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

{4,5,6,7,8,9,10}

2.12

{1,3,5,7,9}

{2,3,4,5,6,7,8}

{5,6,7,8,9,10}

2.13

{1,2,4,6,8,9}

{3,4,5,6,7,8,9}

{6,7,8,9,10}

2.14

{3,4,5,6,7,8,9}

{6,7,8,9,10}

{1,2,4,6,8,9}

2.15

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

{4,5,6,7,8,9,10}

{2,4,6,8,10}

2.16

{5,6,7,8,9,10}

{1,3,5,7,9}

{2,3,4,5,6,7,8}

2.17

{2,4,6,7,8,9}

{1,2,3,5,7,9,10}

{3,4,5,6,7,8}

2.18

{3,4,5,6,7,8}

{6,7,8,9,10}

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

2.19

{7,8,9,1,2,3}

{1,3,5,7,8,9}

{2,4,6,8,10}

2.20

{8,9,10,1,2,3}

{2,4,6,7,8,9}

{1,3,5,6,7,8}

2.21

{4,5,6,7,8,9,10}

{2,4,6,8,10}

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

2.22

{5,6,7,8,9,10}

{1,3,5,7,9}

{2,3,4,5,6,7,8}

2.23

{6,7,8,9,10}

{1,2,4,6,8,9}

{3,4,5,6,7,8,9}

2.24

{1,2,4,6,8,9}

{3,4,5,6,7,8,9}

{6,7,8,9,10}

2,25

{2,4,6,8,10}

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

{4,5,6,7,8,9,10}

2.26

{2,3,4,5,6,7,8}

{5,6,7,8,9,10}

{1,3,5,7,9}

2.27

{3,4,5,6,7,8}

{2,4,6,7,8,9}

{1,2,3,5,7,9,10}

2.28

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

{3,4,5,6,7,8}

{6,7,8,9,10}

2.29

{2,4,6,8,10}

{7,8,9,1,2,3}

{1,3,5,7,8,9}

2.30

{1,3,5,6,7,8}

{8,9,10,1,2,3}

{2,4,6,7,8,9}

          

3 Для данных множеств А  и  В найти

а);

б);

в);

г) булеан множества А (т.е. множество всех подмножеств);

д) какое-нибудь покрытие множества A;

е) какое-нибудь разбиение множества A;

ж) произвольное множество подмножеств А ( ни булеан, ни покрытие, ни разбиение).

 

Т а б л и ц а  3

№

A

B

№

A

B

3.1 

{1,2,3}

{4,5}

3.2

{3,4,5}

{7,8}

3.3

{7,8,9}

{1,2,3}

3.4

{7,8,9}

{3,4,5}

3.5

{4,5,8}

{2,3,5}

3.6

{4,7,8}

{9,0}

3.7

{3,4,9}

{6,7,8}

3.8

{2,6,8}

{1,2,3}

3.9

{3,5,7}

{1,4,6}

3.10 

{8,9,0}

{1,2,4}

3.11

{1,3,5}

{6,7,8}

3.12

{0,1,2}

{8,9}

3.13

{6,7,8}

{4,5}

3.14

{4,5,6}

{1,2}

3.15

{3,4,8}

{1,9}

3.16

{2,9,5}

{3,4}

3.17

{4,6,8}

{1,2,3}

3.18

{1,2,3}

{4,7,9}

3.19 

{1,5,6}

{2,3}

3.20

{1,3,5}

{2,7,8}

3.21

{6,7,9}

{5,8}

3.22

{6,7,8}

{5,9}

3.23

{2,4,6}

{3,5}

3.24

{3,4,7}

{8,9}

3.25

{5,6,0}

{1,2}

3.26

{5,6,8}

{2,3,7}

3.27

{1,3,4}

{7,8}

3.28

{1,3,5}

{6,7}

3.29

{2,7,8}

{4,6,9}

3.30

{3,4,6}

{1,9}

 

4 Доказать тождество с помощью диаграмм Эйлера-Венна.

Т а б л и ц а  4

4.1

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

4.2

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

4.3

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

4.4

4.5

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

4.6

4.7

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

4.8

4.9

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

4.10

4.11

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

4.12

4.13

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

4.14

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

4.15

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

4.16

4.17

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

4.18

4.19

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

4.20

4.21

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

4.22

4.23

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

4.24

4.25

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

4.26

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

4.27

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

4.28

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

4.29

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

4.30

(В \ А) \ С = (В \ С) \ (А \ С)

 

5 Пусть [P] и [Q] матрицы некоторых бинарных отношений. Найти  [PQ],  [PQ],  [PQ],  [P],  [] . Проверить выполнение включений PQ и  Q P

 

Т а б л и ц а 5

№

[P]

[Q]

№

[P]

[Q]

5.1 

5.2

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10 

5.11

5.12

5.13

5.14

5.15

5.16

5.17

5.18

5.19 

5.20

5.21

5.22

5.23

5.24

5.25

5.26

5.27

5.28

5.29

5.30

 

6 Для данных множеств А={a,b,c} и В={1,2,3,4} и отношений  

a) построить матрицы отношений  и ;

б) изобразить отношения графически;

в) найти  ;  ;  ;

г) проверить для отношения  выполнение свойств рефлексивности, симметричности, антисимметричности, транзитивности.

 

Т а б л и ц а 6

№

6.1

6.2

6.3

6.4

6.5

6.6

6.7

6.8

6.9

6.10

6.11

6.12

6.13

6.14

6.15

6.16

6.17

продолжение таблицы 6

6.18

6.19

6.20

6.21

6.22

6.23

6.24

6.25

6.26

6.27

6.28

6.29

6.30

 

7 Доказать, что отношение   является отношением порядка  на множестве A={a,d,c,d,e} или A={a,d,c,d}. Какой это порядок (частичный нестрогий, строгий, линейный)? Построить диаграмму Хассе для упорядоченного множества .

 

Т а б л и ц а  7

№

Р

№

Р

7.1

 {(a,a),(b,b),(c,c),(d,d),(a,c),(b,c)}

7.2

{(a,c),(b,c),(b,d),(c,d),(a,d)}

7.3

{(a,a),(b,b),(c,c),(d,d),(a,c),(b,c),(c,d),

(a,d),(b,d)}

7.4

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(a,c),

(a,e), (d,b),(e,b)}

7.5

 {(a,a),(b,b),(c,c),(d,d),(a,b),(a,c),(b,c),

 (b,d),(c,d),(a,d)}

7.6

{(a,a),(b,b),(c,c),(d,d),(e,e),(c,a),(c,b),

(c,e),(d,a),(d,b),(d,e),(e,a),(e,b)}

7.7

{(a,a),(b,b),(c,c),(d,d),(e,e),(d,a),(d,b),

(d,c),(e,a),(e,b),(e,c),(e,d)}

7.8

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(a,c),

(e,d), (e,c)}

7.9

{(a,b),(c,a),(c,b,),(d,a),(d,b),(e,a),(e,b)}

7.10

{(a,b),(a,c),(b,c),(b,d),(c,d),(a,d)}

 

продолжение таблицы 7

7.11

{(a,b),(c,b),(d,a),(d,b),(d,c),(d,e)}

7.12

{(c,a),(c,b),(c,e),(d,a),(d,b),(d,e),(e,a),

(e,b)}

7.13

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(c,b),

 (d,a),(d,b),(d,c),(d,e)}

7.14

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(c,a),

(c,b), (d,a),(d,b),(e,a),(e,b)}

7.15

{(a,b),(a,c),(a,e),(d,b),(e,b)}

7.16

{(a,b),(c,b),(a,c),(e,d,),(e,c),(e,b)}

7.17

 {(a,a),(b,b),(c,c),(d,d),(a,c),(b,c)}

7.18

{(a,c),(b,c),(b,d),(c,d),(a,d)}

7.19

{(a,a),(b,b),(c,c),(d,d),(a,c),(b,c),(c,d),

(a,d),(b,d)}

7.20

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(a,c),

(a,e), (d,b),(e,b)}

7.21

 {(a,a),(b,b),(c,c),(d,d),(a,b),(a,c),(b,c),

 (b,d),(c,d),(a,d)}

7.22

{(a,a),(b,b),(c,c),(d,d),(e,e),(c,a),(c,b),

(c,e),(d,a),(d,b),(d,e),(e,a),(e,b)}

7.23

{(a,a),(b,b),(c,c),(d,d),(e,e),(d,a),(d,b),

(d,c),(e,a),(e,b),(e,c),(e,d)}

7.24

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(a,c),

(e,d), (e,c)}

7.25

{(a,b),(c,a),(c,b,),(d,a),(d,b),(e,a),(e,b)}

7.26

{(a,b),(a,c),(b,c),(b,d),(c,d),(a,d)}

7.27

{(a,b),(c,b),(d,a),(d,b),(d,c),(d,e)}

7.28

{(c,a),(c,b),(c,e),(d,a),(d,b),(d,e),(e,a),

(e,b)}

7.29

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(c,b),

 (d,a),(d,b),(d,c),(d,e)}

7.30

{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(c,a),

(c,b),(d,a),(d,b),(e,a),(e,b)}

 

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

8.13

8.14

8.15

8.16

8.17

8.18

8.19

8.20

8.21

8.22

8.23

8.24

8.25

8.26

8.27

8.28

8.29

8.30

 

9 Для данного разбиения множества А={1,2,3,4,5,6} построить соответствующее отношение эквивалентности. Почему оно является отношением эквивалентности? Записать классы эквивалентности и фактор – множество.

 

Т а б л и ц а  9

№

Разбиение А

№

Разбиение А

9.1

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

9.2

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

9.3

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

9.4

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

9.5

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

9.6

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

9.7

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

9.8

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

9.9

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

9.10

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

9.11

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

9.12

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

9.13

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

9.14

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

9.15

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

9.16

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

9.17

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

9.18

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

9.19

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

9.20

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

 

продолжение таблицы 9

9.21

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

9.22

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

9.23

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

9.24

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

9.25

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

9.26

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

9.27

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

9.28

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

9.29

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

9.30

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

 

 

10 Даны два отношения  и . Доказать, что эти отношения являются функциями. Найти композиции . Какими свойствами обладают эти отношения (инъективность, сюръективность, биективность)?

 

Т а б л и ц а 10

10.1

10.2

10.3

 

10.4

10.5

10.6

10.7

10.8

10.9

10.10

10.11

10.12

10.13

10.14

10.15

10.16

10.17

10.18

10.19

10.20

10.21

10.22

 

 

продолжение таблицы 10

10.23

10.24

10.25

10.26

10.27

10.28

10.29

10.30

 

1.2           Решение типового варианта

 

1а) Множество задать перечислением элементов.

Решение:

так как N={1,2,3,4,…}, то А={1,2,3}.

 

1б) Множество  задать общим свойством.

Решение:

.

 

2 Пусть U={1,2,3,4,5,6,7,8,9,10} - универсальное множество. Для данных множеств А={1,2,3,8,9,10}, В={1,3,5,6,7,8}, С={2,4,6,7,8,9} найти

а);

б);

в);

г);

д);

е) ;

ж) ;

и) .

Решение:

а) ;

б);

в); г); д); е);

ж) ;

и) .

 

3 Для данных множеств А={3,4,5}  и  В={6,7,9} найти

а);

б);

в) ;

г) булеан множества А (т.е. множество всех подмножеств);

д) какое-нибудь покрытие множества A;

е) какое-нибудь разбиение множества A;

ж) произвольное множество подмножеств А ( ни булеан, ни покрытие, ни разбиение).

Решение:

a) =

;

б); в);

г) так как  состоит из трёх элементов, то булеан P   имеет  элементов:   P  ;

д) например,  - покрытие ;

е) например, - разбиение ;

ж) например,  - ни булеан, ни разбиение, ни покрытие.

 

4 Доказать тождество  с помощью диаграмм Эйлера-Венна.

Решение:

изобразим диаграммами Эйлера-Венна левую и правую части отдельно.

         Левая часть:

                      

                      

Рисунок 1- Диаграмма Эйлера-Венна для левой части

 

         Правая часть:

                                

 

Рисунок 2- Диаграмма Эйлера-Венна для правой части

 

На последних рисунках левой и правой частей отмечена одна и та же область, что доказывает тождество.

5 Пусть [P] = и [Q] =  матрицы некоторых бинарных отношений. Найти  [PQ], [PQ], [PQ], [P], [] . Проверить выполнение включений PQ и Q P.

Решение:

если [P] = , [Q] = , то [PQ] == [P]+[Q], где элементы матриц складываются по правилам: 0+0=0, 1+0 = 0+1 = 1+1 =1; [PQ] = == [P]*[Q], т.е. соответствующие элементы перемножаются по обычным правилам: = = = 0, = 1; [PQ]= - обычное умножение матриц, но элементы матриц [P] и [Q] складываются и умножаются по выше приведённым правилам; [P-1]=[P]T, где P-1 отношение, обратное к  P; - дополнение Р и её матрица [] равна матрице отношения Р, в которой нули заменены единицами и единицы нулями; если PQ, то  .

          В нашем случае

[PQ]= =;

[PQ] = = =;

[PQ]= = ;

[P]== ;

[]=;    т.к., например, не , то P не Q; т.к., например, не , то Q не  P .

                  

6 Для данных множеств А={a,b,c,d} и В={1,2,3,4} и отношений

 и , ,  

a) построить матрицы отношений  и ;

б) изобразить отношения графически;

в) найти ;  ;  ;

г) проверить для отношения  выполнение свойств рефлексивности, симметричности, антисимметричности, транзитивности.

         Решение:

а) по определению - матрица отношения , если

Таким образом,  , .

б) Графическое изображение  и  приведено на рисунках 3 и 4.

     

            Рисунок 3- График                      Рисунок 4- График

 

Заметим, что существуют другие способы графического изображения отношений. Например, отношение  можно изобразить как на рисунке 5, а отношение  – как на рисунке 6 (т.е. ориентированным графом).

 

                           

 

           Рисунок  5 - Граф                                        Рисунок 6 - Граф 

 

в) Так как , то  , . Поскольку ,  и

, то дополнением  к  будет отношение

.

Поскольку по определению P1P2 = {(a,c)| aA, cC и bB, что (a,b) P1 и (b,c)P2}, где , , то             

.

г) Свойства отношения  проще определить по его матрице . Так как на главной диагонали этой матрицы не все единицы, то отношение  не рефлексивное; так как , то оно не симметричное. Поскольку все элементы вне главной диагонали матрицы  являются нулями, то  антисимметричное; так как, например, , но , то  не транзитивное.

 

7 Доказать, что отношение   является отношением порядка  на множестве A={a,d,c,d,e}. Какой это порядок (частичный нестрогий, строгий, линейный)? Построить диаграмму Хассе для упорядоченного множества .

Решение:

заметим, что терминология и классификация отношений порядка различны почти в каждом учебнике. Мы придерживаемся тех, которые указаны в ниже приведенной схеме (см. рисунок 7).  На рисунке 7 отношение   . Сокращения ч.у.м., л.у.м., в.у.м. приняты для обозначений частично, линейно и вполне упорядоченных множеств. Кроме того, если А конечно, то л.у.м. будет  и в.у.м.

Проверим для нашего отношения  выполнение свойств рефлексивнос- ти, симметричности, антисимметричности и транзитивности. Это, как выяснилось выше, легче всего определить по матрице отношения.

 

 

 

Рисунок 7- Классификация отношений порядка

 

 - матрица данного отношения.

Так как на главной диагонали этой матрицы не единицы, то  не рефлексивно; ,

значит,  не симметрично;

 ,

вне главной диагонали этой матрицы все нули, поэтому  антисимметрично; для транзитивности отношения  надо, чтобы  или, если , , то .

Найдём

=. Видим, что  , что доказывает транзитивность .

Итак, не рефлексивно, антисимметрично и транзитивно, поэтому оно является отношением строгого порядка. Так как элементы  и ,  и ,  и  не сравнимы, то - не линейный порядок. Если порядок, определённый на конечном множестве, не линейный, то он и не полный.

Пусть - упорядоченное множество. Если А конечно, то  можно изобразить в виде схемы (диаграммы Хассе), на которой, если , то  и  изображаются точками, соединёнными линией,  ниже .

Построим диаграмму Хассе, причём, в силу транзитивности отношения порядка не нужно, например, соединять линией элементы и , так как если  и , то .

 

Рисунок 8- Диаграмма Хассе

 

Заметим, что в случае рефлексивности , т.е. когда  является частичным или нестрогим порядком, на диаграмме Хассе в каждой вершине появятся петли.

 

8 Доказать, что отношение   является отношением эквивалентности на множестве . Построить классы эквивалентности и фактор-множество.

         Решение:

отношение  является  отношением эквивалентности, если оно рефлексивно, симметрично, транзитивно. Построим матрицу отношения  и по ней определим его свойства.

.

Так как эта матрица содержит единицы на главной диагонали, то - рефлексивно; так как , то оно симметрично.

Найдём  .

Итак, , что доказывает транзитивность .

          - рефлексивно, симметрично, транзитивно, поэтому оно является отношением эквивалентности.

         Классом эквивалентности элемента  называется множество . Множество всех классов эквивалентности  называется фактор-множеством множества  по отношению . Множество  является разбиением множества .

Построим классы эквивалентности для каждого элемента множества :

,

,

,

.

Таким образом, . Фактор-множеством множества  по отношению  будет: .

9 Для данного разбиения {{1,3},{2,4,5},{6}} множества А={1,2,3,4,5,6} построить соответствующее отношение эквивалентности. Почему оно является отношением эквивалентности? Записать классы эквивалентности и фактор – множество.

Решение:

пусть A= - разбиение множества А, где ()- подмножества А. Тогда  - отношение эквивалентности, соответствующее этому разбиению.

Таким образом, в нашем случае

 ={(1,1),(1,3),(3,1),(3,3),(2,2)(2,4),(2,5),(4,2),(4,4)(4,5),(5,2),(5,4),(5,5),(6,6)} - отношение эквивалентности, соответствующее данному разбиению. Чтобы убедиться в том, что это отношение эквивалентности, найдём его матрицу:

 .

По матрице определяем, что  рефлексивно (на главной диагонали все нули), симметрично (), транзитивно (). Поэтому  - отношение эквивалентности. Классы эквивалентности: [1]=[3]={1,3}, [2]=[4]=[5]={2,4,5}, [6]={6}. Фактор-множеством  по отношению  будет данное разбиение  = ={{1,3},{2,4,5},{6}}.

 

10 Даны два отношения  и :

а) доказать, что эти отношения являются функциями;

б) найти композиции ;

в) какими свойствами обладают отношения (инъективность, сюръек-тивность, биективность).

Решение:

а) отношение  является функцией, если  или для любого  существует единственный , что .

В нашем случае  и  являются функциями, так как для любого действительного числа , числа   и   существуют и будут единственными.

б) , ;

в) проверим данные функции на инъективность. Функция  

называется инъективной, если  или .

Для функции  условие инъективности не

выполняется, т.к. существуют пары значений  (), которым соответствует одно , например, , но  и  , т.е. .

Функция  инъективна, так как для любых действительных    выполняется .

Проверим функции на сюръективность. Функция  называется сюръективной, если для любого  существует , что  или область значений отношения  совпадает с .

Функция ,  не сюръективна, так как область значений .

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

Функция называется биективной, если она и  инъективна, и сюръективна, поэтому  не биективная функция,  - биективная.

Заметим, что свойства инъективности, сюръективности и  биективности легко определить по графикам функций. Запишем данные функциональные отношения как обычно записывают функции: ; . Графики этих функций изображены на рисунках 9 и 10.

                        

 

            Рисунок  9 - График                        Рисунок 10 - График 

 

1.3 Контрольные вопросы

 

          1 Множества, их способы задания. Подмножества, булеан. Операции над множествами.

          2 Свойства операции над множествами. Разбиения и покрытия множеств.

          3 Прямое произведение множеств. Отношения (унарные, бинарные, n-арные). Способы задания бинарных отношений. Обратное отношение, дополнение отношения, тождественное отношение. Композиция бинарных отношений.

         4 Основные свойства матриц бинарных отношений. Свойства бинарных отношений (рефлексивность, симметричность, антисимметричность, транзитивность).

          5 Отношение эквивалентности. Классы эквивалентности, фактор-множество.

          6 Отношение порядка. Лексикографический порядок.

          7 Функциональные отношения. Инъекция, сюръекция, биекция. Понятие о мощности множеств.

 

Список литературы

  1. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.
  2. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.
  3. Новиков Ф.А. Дискретная математика для программистов.Учебник для вузов. 2-е изд.  – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).
  4. Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.
  5. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.
  6. Яблонский С.В. Введение в дискретную математику. – М.: «Высшая школа», 2001.
  7. Палий И.А. Дискретная математика. Курс лекций. – М.: Эксмо, 2008. – 352с. – (Техническое образование).
  8. Плотников А.Д. Дискретная математика. Учебное пособие. – 2-е изд., - М.: Новое знание, 2006. – 304 с.
  9. Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. – М.: Айрис – пресс, 2007. – 176 с. – (Высшее образование).
  10.  Данилов В.Г. и др. Дискретная математика. Учебное пособие для вузов. – М.: Горячая линия - Телеком, 2008. – 136 с.
  11.  Астраханцева Л.Н. Дискретная математика. Учебное пособие. – Алматы: АУЭС, 2011. – 78 с.  

 

Содержание

 

Введение                                                                                               3 

1       Расчетно-графическая работа 1. Множества, отношения             3

1.1  Расчётные задания                                                                               3

1.2 Решение типового варианта                                                               13

1.3 Контрольные вопросы                                                                        23

Список литературы                                                                                   24

  

                                                                              Сводный план  2012 г., поз. 179