Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

137 1) любое натуральное число имеет общий остаток от деления на 7 с самим собой;
2) если одно натуральное число имеет со вторым натуральным числом общий остаток от деления на 7, то и второе число имеет с первым числом общий остаток от деления на 7;
3) если одно натуральное число имеет со вторым общий остаток от деления на 7, а второй – с третьим, то и первый со вторым также имеют общий остаток от деления на 7.
Классами эквивалентности являются:
[7] = {7, 14, 21, … } – множество чисел, имеющих в остатке 0;
[15] = {8, 15, 22, … } – множество чисел, имеющих в остатке 1;
[30] = {9, 16, 23, . . . } – множество чисел, имеющих в остатке 2;
[24] = {10, 17, 24, … } – множество чисел, имеющих в остатке 3;
[11] = {11, 18, 25, … } множество чисел, имеющих в остатке 4;
[40] = {12, 19, 26, … } множество чисел, имеющих в остатке 5;
[13] = {13, 20, 27, … } множество чисел, имеющих в остатке 6.
Фактор-множеством будет следующее разбиение множества
????
:
????
????
= {[7], [15], [30], [24], [11], [40], [13]}, а индексом разбиения: ????????????(????/????) = 7.
Варианты индивидуальных заданий:
1. A – множество людей,
(
)


,
живет в одном городе с , ,
P
x y
x
y
x y
A
=

2. A – множество геометрических фигур,
(
)


,
фигура конгруэнтна фигуре , ,
P
x y
x
y
x y
A
=

3. A – множество прямых,
(
)


,
параллельна , ,
P
x y
x
y
x y
A
=

4. A – множество точек на плоскости,
(
)


,
и равноудалены от начала координат, ,
P
x y
x
y
x y
A
=

5. A = Z,
(
)


,
и имеют одинаковый знак, ,
P
x y
x
y
x y
A
=

6. A – множество всех слов русского языка,
(
)


,
и начинаются с одной и той же буквы, ,
P
x y
x
y
x y
A
=

7. A – множество студентов учебной группы,
(
)


,
и имеют одинаковые оценки на экзамене, ,
P
x y
x
y
x y
A
=

8. A – множество сотрудников предприятия,

138
(
)


,
и одного возраста, ,
P
x y
x
y
x y
A
=

9. A – множество членов баскетбольной команды,
(
)


,
и одного роста, ,
P
x y
x
y
x y
A
=

10. A – множество книг в библиотеке,
(
)


,
и имеют переплет одного цвета, ,
P
x y
x
y
x y
A
=

11. A – множество автомобилей на парковочной стоянке,
(
)


,
и одной и той же марки, ,
P
x y
x
y
x y
A
=

12. A – множество студентов группы,
(
)


,
и учатся на одном факультете, ,
P
x y
x
y
x y
A
=

13. A – множество автобусов автомобильного парка,
(
)


,
и имеют одинаковое количество посадочных мест, ,
P
x y
x
y
x y
A
=

14. A – множество зрителей в зале кинотеатра,
(
)


,
и сидят в одном ряду, ,
P
x y
x
y
x y
A
=

15. A – множество жителей многоквартирного дома,
(
)


,
и живут в одном подъезде, ,
P
x y
x
y
x y
A
=

16. A – множество преподавателей университета,
(
)


,
и работают на одной кафедре, ,
P
x y
x
y
x y
A
=

17. A = N,
(
)


,
и имеют одинаковый остаток от деления на 7, ,
P
x y
x
y
x y
A
=

18. A = N,
(
)


,
и имеют одинаковый остаток от деления на 3, ,
P
x y
x
y
x y
A
=

19. A – множество сосудов в химической лаборатории,
(
)


,
и имеют одинаковый объем, ,
P
x y
x
y
x y
A
=

20. A – множество ваз в магазине,
(
)


,
и имеют одинаковую форму, ,
P
x y
x
y
x y
A
=

21. A – множество артистов цирка,
(
)


,
и работают в одном цирковом жанре, ,
P
x y
x
y
x y
A
=

22. A – множество жителей России,
(
)


,
и живут в одном регионе, ,
P
x y
x
y
x y
A
=

23. A – множество звезд на небе,
(
)


,
и находятся в одном созвездии, ,
P
x y
x
y
x y
A
=

24. A – множество студентов вуза,
(
)


,
и получают стипендию одинакового размера, ,
P
x y
x
y
x y
A
=

25. A – множество файлов на диске,
(
)


,
и одного типа, ,
P
x y
x
y
x y
A
=

26. A – множество иностранных гостей на олимпиаде,

139
(
)


,
и представляют одну страну, ,
P
x y
x
y
x y
A
=

27. A – множество собак в питомнике,
(
)


,
и одного окраса, ,
P
x y
x
y
x y
A
=

28. A – множество геометрических фигур,
(
)


,
фигура конгруэнтна фигуре , ,
P
x y
x
y
x y
A
=

29. A – множество прямых,
(
)


,
параллельна , ,
P
x y
x
y
x y
A
=

30. A – множество точек на плоскости,
(
)


,
и равноудалены от начала координат, ,
P
x y
x
y
x y
A
=


140 7. Элемент
???? ∈ ???? частично упорядоченного множества (????, ≤) называется максималь- ным, если не существует элемента ???? такого что ???? < ????.
8. Элемент
???? ∈ ???? частично упорядоченного множества (????, ≤) называется минималь- ным, если не существует элемента ????, такого что ???? < ????.
9.
Элемент
???? ∈ ???? частично упорядоченного множества (????, ≤) называется наиболь- шим, если ∀???? ∈ ???? ???? ≤ ????.
10. Элемент
???? ∈ ???? частично упорядоченного множества (????, ≤) называется наимень- шим, если ∀???? ∈ ???? ???? ≤ ????.
Пример выполнения задания
Отношение ???? = {(1,2), (1,3), (5,4)} на множестве {1, 2, 3, 4, 5}:
1) представить в виде графа;
2) достроить до отношения эквивалентности, представить в виде графа, указать фак- тор-множество и его индекс;
3) достроить до отношения частичного порядка, представить в виде графа, указать максимальные, минимальные элементы, а также пары несравнимых элементов;
4) достроить до отношения линейного порядка, указать наибольший и наименьший элементы;
5) достроить до отношения строгого порядка;
Решение:
1. Граф отношения
????:
2. Достроим
???? до отношения эквивалентности ????
1
добавляя минимально возможное число дуг:
????
1
= {(1,2), (1,3), (5,4), (1,1), (2,2), (3,3), (4,4), (5,5), (2,1), (3,1), 4,5), (2,3), (3,2}.
Граф отношения ????
1
:
Фактор множество:
????/????
1
= {{1,2,3}, {4,5}}; ????????????(????/????
1
) = 2.

141 3. Достроим
???? до отношения частичного порядка ????
2
:
????
2
= {(1,1), (2,2), (3,3), (4,4), (5,5), (1,2), (1,3), (5,4)}
Граф отношения ????
2
:
Минимальные элементы: 1 и 5.
Максимальные элементы: 2, 3 и 4.
4. Достроим
???? до отношения линейного порядка ????
3
:
????
3
=
{(1,1), (2,2), (3,3), (4,4), (5,5), (1,2), (1,3), (5,4), (2,3), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3)}
Граф отношения ????
3
:
Наименьший элемент: 5.
Наибольший элемент: 3.
5. Исходное отношение
???? является отношением строгого порядка, поэтому нет необ- ходимости его достраивания.
Варианты индивидуальных заданий:
№
Соотношение
№
Соотношение
1
???? = {(2,3), (3,5), (5,1)}
16
???? = {(1,2), (1,3), (3,2), (4,5)}
2
???? = {(4,5), (5,4), (4,3)}
17
???? = {(1,2), (1,5), (1,4)}
3
???? = {(3,1), (2,5), (5,4)}
18
???? = {(1,2), (2,3), (4,5), (5,3)}
4
???? = {(1,2), (3,2), (2,4)}
19
???? = {(1,2), (2,3), (2,4), (4,5)}
5
???? = {(1,2), (3,4), (4,5)}
20
???? = {(3,5), (4,2), (1,2)}
6
???? = {(2,1), (5,1), (4,2)}
21
???? = {(1,2), (4,3), (4,5)}
7
???? = {(1,2), (2,3), (3,4), (5,5)}
22
???? = {(4,3), (5,1), (1,2)}
8
???? = {(4,2), (5,2), (1,4)}
23
???? = {(2,3), (5,4), (5,1)}
9
???? = {(2,4), (3,4), (4,1)}
24
???? = {(3,4), (4,1), (1,2)}

142
№
Соотношение
№
Соотношение
10
???? = {(5,4), (4,3), (5,3), (2,1)}
25
???? = {(2,1), (1,5), (5,4)}
11
???? = {(3,4), (1,5), (5,2)}
26
???? = {(4,2), (3,1), (1,5)}
12
???? = {(5,2), (2,4), (4,3), (1,1)}
27
???? = {(2,3), (4,5), (5,1)}
13
???? = {(4,3), (3,1), (1,2)}
28
???? = {(3,2), (4,5), (5,1)}
14
???? = {(2,3), (4,5), (3,4), (1,1)}
29
???? = {(2,3), (4,3), (3,5)}
15
???? = {(4,1), (5,3), (2,3)}
30
???? = {(1,3), (3,4), (1,4), (2,5)}
1.8. Исследование функций
Методические указания к выполнению задания
Задание. Для заданной функции:
1) найти область определения и область значений функции;
2) изобразить функцию графически;
3) выяснить, является ли она отображением, сюръективной, инъективной, биективной функцией, биекцией;
4) найти образы и прообразы множеств;
5) выяснить, является ли обратное отношение функцией.
При выполнении задания необходимо пользоваться следующим понятиями:
1. Бинарное отношение
R
на множествах
A
и
B
является функцией для единственное
,
R
x
y B

 

 такое, что
( )
,
x y
R

2. Функция
????: ???? → ???? – отображение, если ее область определения совпадает с ????.
3.
Функция
????: ???? → ???? – сюръективная функция, если ее область значений совпадает с
????.
4.
Функция
????: ???? → ???? – инъективная функция, если любому элементу из области зна- чений соответствует единственный элемент из области определения.
5.
Функция
????: ???? → ???? – биективная функция, если она сюръективна и инъективна.
6.
Функция
????: ???? → ???? – биекция, если она биективное отображение.

143
Пример выполнения задания
Дано:
???? = {(????, 2), (????, 1), (????, 5), (????, 4)}
???? = {????, ????, ????, ????}
???? = {1,2,3,4,5}
???? = {????, ????}
???? = {2,4}
Для функции ????: ???? → ????:
1) найти область определения и область значений функции;
2) изобразить функцию графически;
3) выяснить, является ли она отображением, сюръективной, инъективной, биективной функцией, биекцией;
4) найти образ множества
????: ????(????), прообраз множества ????: ????
−1
(????)
5) выяснить, является ли обратное отношение функцией.
Решение:
1. Графическая интерпретация функции:
2. Область определения и область значений функции:
????
????
= {????, ????, ????, ????};
????
????
= {1,2,4,5}.
3. Функция является отображением, так как
????
????
= ????.
4. Функция не является сюръективной, так как
????
????
≠ ????.
А
В
a
b
c
d
2 3
4 5
1

144 5. Функция является инъективной, так как каждому образу (элементу из
????
????
) соответ- ствует единственный прообраз (элемент из ????
????
).
6. Функция не является биективной, так как функция не сюръективна.
7. Функция не является биекцией, так как функция не является биективной.
8. Образ множества
????: ????(????) = {1,2}.
9. Прообраз множества
????: – ????
−1
(????) = {????, ????}.
Варианты индивидуальных заданий:
№
????
????
????
????
????
1
{????, ????, ????, ????, ????}
{1,2,3}
{(????, 2), (????, 3), (????, 1), (????, 2), (????, 1)}
{????, ????} {2,3}
2
{????, ????, ????, ????}
{1,2,3,4}
{(????, 4), (????, 3), (????, 2), (????, 1)}
{????, ????} {1,3}
3
{????, ????, ????, ????}
{1,2,3,4,5}
{(????, 3), (????, 5), (????, 4), (????, 1)}
{????, ????} {1,4}
4
{????, ????, ????, ????, ????}
{1,2,3,4}
{(????, 1), (????, 2), (????, 4), (????, 3)}
{????, ????} {1,2}
5
{????, ????, ????, ????, ????}
{1,2,3}
{(????, 2), (????, 1), (????, 3), (????, 3)}
{????, ????} {3,1}
6
{????, ????, ????, ????}
{1,2,3,4}
{(????, 1), (????, 4), (????, 1), (????, 2)}
{????, ????} {1,2}
7
{????, ????, ????, ????, ????} {1,2,3,4,5}
{(????, 5), (????, 3), (????, 1), (????, 2)}
{????, ????} {1,3}
8
{????, ????, ????, ????}
{1,2,3,4}
{(????, 3), (????, 4), (????, 3), (????, 1)}
{????, ????} {1,3}
9
{????, ????, ????}
{1,2,3,4,5}
{(????, 2), (????, 1), (????, 5)}
{????, ????} {3,4}
10
{????, ????, ????}
{1,2,3}
{(????, 1), (????, 3), (????, 1)}
{????, ????} {2,3}
11
{????, ????, ????, ????}
{1,2,3,4,5}
{(????, 2), (????, 1), (????, 5), (????, 5)}
{????, ????} {1,2}
12
{????, ????, ????, ????, ????}
{1,2,3,4}
{(????, 1), (????, 3), (????, 2), (????, 2)}
{????, ????} {1,2}
13
{????, ????, ????, ????}
{1,2,3}
{(????, 1), (????, 1), (????, 3), (????, 2)}
{????, ????} {1,3}
14
{????, ????, ????, ????}
{1,2,3,4}
{(????, 4), (????, 3), (????, 2), (????, 4)}
{????, ????} {3,4}
15
{????, ????, ????, ????}
{1,2,3,4}
{(????, 4), (????, 4), (????, 2)}
{????, ????} {2,4}
16
{????, ????, ????, ????, ????}
{1,2,3}
{(????, 2), (????, 1), (????, 3), (????, 2)}
{????, ????} {1,3}
17
{????, ????, ????, ????}
{1,2,3,4}
{(????, 3), (????, 2), (????, 2), (????, 1)}
{????, ????} {2,4}
18
{????, ????, ????, ????}
{1,2,3,4}
{(????, 3), (????, 3), (????, 1), (????, 4)}
{????, ????} {2,3}
19
{????, ????, ????}
{1,2,3,4,5}
{(????, 2), (????, 5), (????, 4)}
{????, ????} {2,5}
20
{????, ????, ????, ????}
{1,2,3,4}
{(????, 1), (????, 3), (????, 2)}
{????, ????} {3,4}
21
{????, ????, ????, ????}
{1,2,3}
{(????, 3), (????, 3), (????, 1), (????, 2)}
{????, ????} {1,3}
22
{????, ????, ????, ????}
{1,2,3}
{(????, 2), (????, 3), (????, 2), (????, 1)}
{????, ????} {2,3}
23
{????, ????, ????, ????}
{1,2,3,4}
{(????, 3), (????, 4), (????, 1), (????, 2)}
{????, ????} {2,4}
24
{????, ????, ????}
{1,2,3,4}
{(????, 3), (????, 1), (????, 2)}
{????, ????} {4,2}
25
{????, ????, ????, ????, ????}
{1,2,3}
{(????, 2), (????, 1), (????, 3), (????, 3)}
{????, ????} {2,3}
26
{????, ????, ????, ????}
{1,2,3,4}
{(????, 2), (????, 3), (????, 1)}
{????, ????} {1,4}