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

128 3) симметричным, если (
????, ????) ∈ ????  (????, ????) ∈ ????;
4) антисимметричным, если (
????, ????) ∈ ???? и (????, ????) ∈ ????  ???? = ????;
5) транзитивным, если (
????, ????) ∈ ???? и (????, ????) ∈ ????  (????, ????) ∈ ????.
2. Бинарное отношение
???? на множестве ???? называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности и транзитивности.
3. Бинарное отношение
???? на множестве ???? называется отношением строгого порядка
(или полным порядком), если оно антирефлексивно и транзитивно.
4. Бинарное отношение
???? на множестве ???? называется отношением нестрогого по-
рядка (или частичным порядком), если оно рефлексивно, антисимметрично и транзитивно.
Пример выполнения задания:
Дано отношение ???? = {(????, ????)| ???? и ???? учатся в одной группе, ????, ???? ∈ ????} на множестве студентов ????. Определить, какими свойствами обладает это отношение. Является ли оно от- ношением строгого порядка, нестрогого порядка, эквивалентности?
Решение.
По определению рефлексивности для ∀???? ∈ ???? (????, ????) ∈ ????:
Если допустить, что любой студент учится с самим с собой в одной группе, то отно- шение ???? – рефлексивное.
По определению симметричности (????, ????) ∈ ????  (????, ????) ∈ ????:
Один студент учится в одной группе со вторым студентом, равно как и второй студент учится в одной группе с первым. Значит, отношение ???? – симметричное.
По определению антисимметричности (????, ????) ∈ ???? и (????, ????) ∈ ????  ???? = ????:
Если один студент учится в одной группе со вторым студентом и второй студент учится в одной группе с первым, то это не значит, что ???? и ???? – один и тот же студент. Значит, отношение ???? – неантисимметричное.
По определению транзитивности если (????, ????) ∈ ???? и (????, ????) ∈ ????  (????, ????) ∈ ????.
Если один студент учится в одной группе со вторым студентом, а второй студент – с третьим в одной группе, то первый с третьим также учатся в одной группе. Следовательно, отношение ???? – транзитивное.
Поскольку отношение ???? является рефлексивным, симметричным и транзитивным, то оно является отношением эквивалентности.
Варианты индивидуальных заданий:
1) A – множество геометрических фигур,

129
(
)


,
фигура конгруэнтна фигуре , ,
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 – множество геометрических фигур,
(
)


,
фигура имеет площадь меньше чем фигура , ,
P
x y
x
y
x y
A
=

6) A = {1, 2, 3, 4, 5, 6, 7, 8, 9},
(
)


,
четно, ,
P
x y
x
y
x y
A
=
+

7) A = N,
(
)


,
четно, ,
P
x y
x
y
x y
A
=
+

8) A – множество людей,
(
)


,
знаком с , ,
P
x y
x
y
x y
A
=

9) A – множество прямых,
(
)


,
перпендикулярна , ,
P
x y
x
y
x y
A
=

10) A = N,
(
)


,
2, ,
P
x y
xy
x y
A
=

11) A – множество точек на плоскости,
(
)


,
и равноудалены от оси ординат, ,
P
x y
x
y
x y
A
=

12) A = N,
(
)


,
(
) 7, ,
P
x y
x
y
x y
A
=
−

13) A = {1, 2, 3, 4, 5, 6, 7, 8, 9},
(
)


,
(
1) делитель (
), ,
P
x y
x
x
y
x y
A
=
+
+

14) A = N,
(
)


,
( , )
1, ,
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 – множество прямых,
(
)


,
и пересекаются, ,
P
x y
x
y
x y
A
=

18) A – множество людей,
(
)


,
отец , ,
P
x y
x
y
x y
A
=

19) A = R,

130
(
)


2 2
,
4, ,
P
x y
x
y
x y
A
=
+


20) A = {1, 2, 3, 4, 5, 6, 7, 8, 9},
(
)


,
1 и делитель (
), ,
P
x y
x
x
x
y
x y
A
=

+

21) A – множество людей,
(
)


,
начальник , ,
P
x y
x
y
x y
A
=

22) A = N,
(
)


,
нечетно, ,
P
x y
x
y
x y
A
=
+

23) A – множество людей,
(
)


,
состоит в браке с , ,
P
x y
x
y
x y
A
=

24) A = R,
(
)


2 2
,
4, ,
P
x y
x
y
x y
A
=
+
=

25) A = N,
(
)


,
(
) 7, ,
P
x y
x
y
x y
A
=
+

26) A = {1, 2, 3, 4, 5, 6, 7, 8, 9},
(
)


,
четно, ,
P
x y
x
y
x y
A
=
−

27) A – множество людей,
(
)


,
похож на , ,
P
x y
x
y
x y
A
=

28) A = R,
(
)


2 2
,
4, ,
P
x y
x
y
x y
A
=
+


29) A = N,
(
)


,
кратно , ,
P
x y
x
y
x y
A
=

30) A – множество людей,
(
)


,
живет в одном городе с , ,
P
x y
x
y
x y
A
=


131 3. У симметричного отношения матрица симметрична относительно главной диаго- нали.
4. У антисимметричного отношения если вне главной диагонали имеется 1, то на симметричном ей месте стоит 0.
5. В матрице транзитивного отношения для каждой пары единичных элементов, один из которых расположен в i-й строке и j-м столбце, а другой – в j-й строке и k-м столбце, обязательно существует единичный элемент, расположенный в i-й строке и k-м столбце. Наличие единичных элементов на главной диагонали не нарушает транзитивно- сти.
Пример выполнения задания:
Даны множества ???? = {????, ????, ????}, ???? = {1, 2, 3, 4} и отношения:
????
1
= {(????, 2), (????, 3), (????, 1), (????, 3)},
????
2
= {(1,2), (3,1), (2,4), (1,4)}.
Изобразите ????
1
,
????
2
графически.
Найдите (????
1
°????
2
)
−1
Проверьте с помощью матрицы ????
2
, является ли отношение ????
2
рефлексивным, антире- флексивным, симметричным, антисимметричным, транзитивным?
Решение
Графическое изображение отношения ????
1
:
По определению композиции отношений строим отношение:
????
1
°????
2
= {(????, 4), (????, 1), (????, 2), (????, 4), (????, 1)}.
По определению обратного отношения находим:
(????
1
°????
2
)
−1
= {(4, ????), (1, ????), (2, ????), (4, ????), (1, ????)}.
Построим матрицу отношения ????
2
:

132 1
2 3 4
1 2
3 4
[
0 1 0 1
0 0 0 1
1 0 0 0
0 0 0 0
]
Отношение ????
2
не рефлексивно, так как у рефлексивного отношения все элементы главной диагонали должны быть только единицами.
Отношение антирефлексивно, так как все элементы главной диагонали нули.
Матрица не симметрична относительно главной диагонали, следовательно, отноше- ние ????
2
несимметрично.
Отношение антисимметрично, так как не существует симметричных единиц относи- тельно главной диагонали.
Отношение не транзитивно. Для единиц 3-й строки и 1-го столбца, 1-й строки и 2-го столбца не существует единицы 3-й строки и 2-го столбца.
Варианты индивидуальных заданий:
1)




1 2
( ,1), ( , 2), ( ,3), ( , 2), ( ,3), ( , 4), ,
(1,1), (2,1), (2, 2), (2,3), (2, 4), (3,3), (4, 4)
P
a
a
b
c
c
c
P
=
=
2)




1 2
( ,1), ( , 2), ( ,3), ( , 4), ( ,3), ( , 2), ,
(1,1), (1, 4), (2, 2), (2,3), (3,3), (4,1), (4, 4)
P
a
a
a
a
b
c
P
=
=
3)




1 2
( ,1), ( , 2), ( , 4), ( ,3), ( , 2), ( , 4) ,
(2,1), (3,1), (3, 2), (4,1), (4,3)
P
a
a
a
c
c
c
P
=
=
4)




1 2
( ,1), ( , 2), ( , 2), ( , 4), ( , 2), ( ,3) ,
(1,1), (1, 2), (2, 2), (3,3), (4, 4), (4,3)
P
a
a
b
b
c
c
P
=
=
5)




1 2
( ,1), ( , 4), ( , 2), ( ,3), ( ,1), ( , 4) ,
(1,1), (1, 4), (2,1), (3, 4), (4,3), (4,1)
P
a
a
b
b
c
c
P
=
=
6)




1 2
( ,1), ( , 2), ( , 4), ( ,1), ( , 4), ( ,3) ,
(1,1), (2, 4), (2,1), (3,3), (4, 2), (4,1)
P
a
a
a
b
b
c
P
=
=
7)




1 2
( ,1), ( ,3), ( ,1), ( , 4), ( , 2), ( ,3) ,
(1,3), (1, 4), (2, 2), (3,3), (4,3), (4, 4)
P
a
b
b
b
c
c
P
=
=
8)




1 2
( ,1), ( ,3), ( ,1), ( , 4), ( ,3), ( , 2) ,
(1,1), (1, 2), (1, 4), (2,1), (2, 2), (2,3), (3,3), (3, 2), (3, 4), (4,3), (4, 4), (4,1)
P
a
b
c
c
c
c
P
=
=

133 9)




1 2
( ,1), ( , 2), ( , 4), ( ,3), ( ,1), ( , 4) ,
(1,3), (1, 2), (2,3), (3, 2), (3, 4), (4,1)
P
a
a
a
b
c
c
P
=
=
10)




1 2
( ,1), ( , 2), ( , 2), ( ,3), ( ,1), ( , 4) ,
(1,1), (1, 2), (2, 2), (3,3), (4,1), (4, 4)
P
a
a
b
b
c
c
P
=
=
11)




1 2
( , 2), ( , 4), ( ,3), ( ,1), ( , 2) ,
(1,1), (1,3), (2, 4), (3,1), (3, 4).(4,3), (4, 2)
P
a
a
b
c
c
P
=
=
12)




1 2
( ,1), ( ,3), ( ,1), ( , 2), ( ,3), ( , 4) ,
(1,1), (2, 2), (2,3), (2, 4), (3, 2), (3,3), (3, 4), (4, 2), (4,3), (4, 4)
P
b
b
c
c
c
c
P
=
=
13)




1 2
( ,1), ( , 2), ( , 4), ( , 2), ( , 4), ( ,3) ,
(1,1), (2, 2), (2, 4), (3,3), (4, 4), (4, 2)
P
a
a
a
b
b
c
P
=
=
14)




1 2
( , 2), ( ,3), ( , 4), ( ,1), ( ,3), ( , 4) ,
(1, 4), (2,3), (2,1), (3, 4), (4, 2)
P
a
a
a
c
c
c
P
=
=
15)




1 2
( ,1), ( , 2), ( ,3), ( , 4), ( ,3), ( , 4) ,
(1,1), (1, 4), (2,1), (2, 2), (2, 4), (3,3)
P
a
a
b
b
c
c
P
=
=
16)




1 2
( , 2), ( ,3), ( , 4), ( ,1), ( , 2), ( , 4) ,
(1,1), (1,3), (1, 4), (2, 2), (2,3), (3, 2), (3,3), (4,3), (4, 4)
P
a
a
a
b
b
b
P
=
=
17)




1 2
( ,3), ( , 4), ( ,3), ( ,1), ( , 2), ( , 2) ,
(1,1), (1,3), (2, 4), (3,1), (3,3), (4, 2)
P
a
b
b
b
b
c
P
=
=
18)




1 2
( ,3), ( , 4), ( ,3), ( ,1), ( , 2), ( , 4) ,
(1, 2), (1,3), (1, 4), (2,3), (4,3), (4, 2)
P
a
b
b
c
c
c
P
=
=
19)




1 2
( ,1), ( , 2), ( ,3), ( ,1), ( ,3), ( , 4) ,
(1,1), (1, 2), (1,3), (2, 2), (2,3), (3,3), (3, 4), (4,1), (4, 4)
P
a
b
b
c
c
c
P
=
=
20)




1 2
( , 2), ( , 4), ( ,3), ( ,1), ( , 2), ( ,3) ,
(1,1), (1, 4), (2,3), (3,3), (4,1), (4,3), (4, 4)
P
a
a
a
c
c
c
P
=
=
21)




1 2
( , 2), ( , 4), ( ,1), ( , 2), ( , 4), ( , 2), ( , 4) ,
(1,1), (1,3), (2, 2), (2, 4), (3,3), (3, 2), (4,1), (4,3), (4, 4)
P
a
a
b
b
b
c
c
P
=
=
22)




1 2
( ,3), ( , 4), ( ,1), ( , 4), ( , 2), ( , 4) ,
(1,1), (2, 2), (2,3), (2, 4), (3,3), (3, 4), (4, 2), (4, 4)
P
a
a
b
b
c
c
P
=
=

134 23)




1 2
( , 2), ( ,3), ( , 4), ( ,1), ( , 2), ( ,3), ( , 4) ,
(1,1), (1, 4), (2, 2), (2,1), (2, 4), (3,3), (3, 2), (3, 4), (4,3), (4, 4)
P
a
a
a
b
c
c
c
P
=
=
24)




1 2
( ,3), ( ,1), ( , 2), ( , 4), ( ,1), ( , 2), ( , 4) ,
(1,1), (1, 2), (1, 4), (2, 2), (2, 4), (3,3), (3, 2), (3, 4), (4, 4)
P
a
b
b
b
c
c
c
P
=
=
25)




1 2
( , 2), ( ,3), ( , 4), ( ,3), ( ,1), ( , 4) ,
(1,1), (1, 4), (2, 2), (2,3), (2, 4), (3, 4), (4, 2)
P
a
a
a
b
c
c
P
=
=
26)




1 2
( , 4), ( ,1), ( ,3), ( , 4), ( , 2) ,
(1, 4), (2,1), (2,3), (3,3), (3, 4), (4, 4), (4,1)
P
a
b
c
c
c
P
=
=
27)




1 2
( ,1), ( , 2), ( , 4), ( ,3), ( ,1), ( , 4) ,
(1,1), (1, 2), (2, 2), (3,3), (3, 4), (4, 4)
P
b
b
b
c
c
c
P
=
=
28)




1 2
( ,1), ( , 2), ( , 2), ( ,3), ( ,1), ( , 4) ,
(1,1), (1, 2), (2,1), (3,1), (1,3), (4, 4)
P
a
a
c
c
c
c
P
=
=
29)




1 2
( ,1), ( , 2), ( ,3), ( ,1), ( , 2) ,
(1,1), (1,3), (2, 2), (2, 4), (3,1), (3, 2), (3,3), (3, 4).(4,3), (4, 2)
P
a
a
a
c
c
P
=
=
30)




1 2
( ,1), ( ,3), ( ,1), ( , 2), ( ,3), ( , 4) ,
(1,1), (2,3), (3,3), (3, 4), (4, 2), (4, 4)
P
a
b
c
c
c
c
P
=
=
1.5. Построение бинарного отношения, обладающего заданными свойствами
Задание. Постройте бинарное отношение, обладающее следующими свойствами, или докажите, что такого не существует:
Варианты индивидуальных заданий:
№ вар
Рефлек- сивность
Антиреф- лексив- ность
Симмет- ричность
Антисим- мет-рич- ность
Транзи-тив- ность
1
+
–
–
–
–
2
–
+
–
–
–
3
–
–
–
–
–
4
+
–
–
–
+
5
–
+
–
–
+
6
–
–
–
–
+
7
+
–
+
–
–
8
–
+
+
–
–
9
–
–
+
–
–

135
№ вар
Рефлек- сивность
Антиреф- лексив- ность
Симмет- ричность
Антисим- мет-рич- ность
Транзи-тив- ность
10
+
–
+
–
+
11
–
+
+
–
+
12
–
–
+
–
+
13
+
–
–
+
–
14
–
+
–
+
–
15
–
–
–
+
–
16
+
–
–
+
+
17
–
+
–
+
+
18
–
–
–
+
+
19
+
–
+
+
–
20
–
+
+
+
–
21
–
–
+
+
–
22
+
–
+
+
+
23
–
+
+
+
+
24
–
–
+
+
+
25
+
–
+
–
–
26
–
+
+
–
–
27
–
–
+
–
–
28
+
–
+
–
+
29
–
+
+
–
+
30
–
–
+
–
+
1.6. Исследование отношения эквивалентности
Методические указания к выполнению задания
Задание. Докажите, что бинарное отношение P является отношением эквивалентно- сти, определите классы эквивалентности, фактор-множество, индекс фактор-множества
(мощность).
При выполнении задания необходимо пользоваться следующим понятиями:
1. Бинарное отношение
???? на множестве ???? называется отношением эквивалентно- сти, если оно обладает свойствами рефлексивности, симметричности и транзитивности.
2. Разбиением множества
???? называется такая совокупность непустых подмножеств
1 2
, ,...,
n
A A
A
множества
????, которая удовлетворяет следующим условиям:
1 2
;
n
A A
A
A
=
для
, ,
i
j
A
A
i
j i j
n
= 
 


136
Каждое из подмножеств
1 2
, ,...,
n
A A
A
разбиения называется классом эквивалентности.
3.
Если на множестве
???? задано отношение эквивалентности ????, то оно порождает раз- биение этого множества на классы эквивалентности, такое, что:
− любые два элемента одного класса находятся в отношении;
− любые два элемента разных классов не находятся в отношении ????.
4. Фактор-множеством называется множество всех классов эквивалентности по дан- ному отношению
R
на множестве
???? , обозначается ????/???? . Мощность фактор-множества называется индексом разбиения множества ????, обозначается ????????????(????/????).
Примеры выполнения задания
Пример 1. Рассмотрим отношение равенства площадей треугольников на множестве треугольников ????:
(
)


,
, ,
x
y
R
x y
S
S
x y
T
=
=

Доказать, что отношение является отношением эквивалентности, определить классы эквивалентности, фактор-множество, индекс фактор-множества (мощность).
Решение
Докажем, что отношение
R
является отношением эквивалентности:
1) для
x
x
x T S
S
 
=
 R рефлексивно;
2)
x
y
y
x
S
S
S
S
=

=
 R симметрично;
3) и S
x
y
y
z
x
z
S
S
S
S
S
=
=  =
 R транзитивно.
Все три условия выполняются, значит,
R
– отношение эквивалентности. Следова- тельно, оно разбивает множество
T
на классы эквивалентности.
Каждый класс
,
1,..., ,
i
T i =

– это множество всех треугольников с одинаковой площа- дью. Очевидно, что элементов в каждом классе и самих классов эквивалентности бесконеч- ное число.
Совокупность классов


1 2
,
,
,
,
m
T T
T
– это фактор-множество множества
T
по от- ношению
R
(т.е. по отношению равенства площадей треугольников).
Пример 2. Рассмотрим отношение «иметь общий остаток от деления на 7» на множестве ????. Доказать, что отношение является отношением эквивалентности, определить классы эквивалентности, фактор-множество, индекс фактор-множества (мощность).
Решение
Отношение является отношением эквивалентности, так как: