АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ
КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ
Дискретная математика
Методические указания и задания
к выполнению расчетно-графических работ
(для студентов очной формы обучения специальности
050704 – Вычислительная техника и программное обеспечение)
Часть 1
СОСТАВИТЕЛИ: Л.Н. Астраханцева, Л.Н.Ким, М.Ж.Байсалова.
Алгебра и геометрия. Методические указания и задания к выполнению расчетно-графической работы для студентов очной формы обучения специальности 050704 – Вычислительная техника и программное обеспечение.
Методические указания и задания к расчетно-графической работе содержат типовой расчет №3 дисциплины «Алгебра и геометрия» для студентов очной формы обучения специальности 050704 – Вычислительная техника и программное обеспечение. Приведены основные теоретические вопросы программы. Дано решение типового варианта.
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
1.23
|
1.24
|
1.25
|
1.26
|
1.27
|
1.28
|
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.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\(B |
6.2 A |
6.3 A\(B∩C)=(A\B)
|
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 A |
6.14 |
6.15 (A∩B) |
6.16 |
6.17 (A |
6.18 |
6.19 ( A |
6.20 |
6.21 (A |
6.22 |
6.23 A\(B\C)=(A\B)
|
6.24 |
6.25 A\(B |
6.26 A |
6.27 (A\B) |
6.28 (A |
6.29
(A\B) |
6.30
|
7 Даны множества А={a,b,c,d}, В={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 Типовой расчёт 1. Множества, отношения
1.1 Теоретические вопросы
1.2 Расчётные задания
1.3 Решение типового варианта
Список литературы