Отношение порядка. Отношение эквивалентности. (Лекция 8)

1. Отношение порядка. Отношение эквивалентности

1

2. Свойства отношений

• Определение 1
Пусть
P A2 . P называют
а) рефлексивным, если
x A ( x, x) P ,
б) антирефлексивным, если x A ( x, x) P
в) симметричным, если
x, y A ( x, y ) P ( y, x) P
г) антисимметричным, если x, y A
д) транзитивным, если x, y, z A
е) линейным, если
,
,
( x, y) P ( y, x) P ( x y)
( x, y) P ( y, z) P ( x, z) P
x, y A x y ( x, y ) P ( y, x) P
2

3. Пример

A {2;3;4;6;8}, P {( x, y) | x y}
P {( 2;2), (3;3), (4;4), (6;6), (8;8), (4;2), (6;2), (6;3), (8;2), (8;4), (8;4)}
да
А) Рефлексивность Б) Антирефлексивность -
нет
В) Симметричность -
нет
Г) антисимметричность -
да
Д) транзитивность -
да
Е) линейность -
нет
3

4. Отношение порядка

Определение 2
• Антисимметричное, транзитивное отношение называют
отношением порядка. При этом рефлексивное отношение
порядка называют отношением нестрогого порядка
,
антирефлексивное отношение порядка называют отношением
строгого порядка
.
• Линейное отношение порядка называют отношением
линейного порядка. Отношение порядка, не обладающее
свойством линейности, называют отношением частичного
порядка.
4

5. Примеры

1) Естественный порядок на R 2
А) антисимметричность
Б) транзитивность
В) линейность
P {( x, y ) | x y}
Q {( x, y ) | x y}
x y y x x y
x y y x x y
x y y z x z
x y y z x z
x, y R x y x y y x x, y R x y x y y x
Г) рефлексивность
Д) антирефлексивность
x R x x
x R x x
P {( x, y ) | x y} -Отношение нестрогого линейного порядка
Q {( x, y ) | x y} -Отношение строгого линейного порядка
5

6. Примеры

2) Рассмотрим множество всех подмножеств множества A,
Обозначение B(A).
Рассмотрим S B(A)
B(A),
S {( X ; Y ) | X Y }
X Y Y X ( X Y )
А) антисимметричность
X , Y Β( A)
Б) транзитивность
X , Y , Z Β( A)
В) рефлексивность
X Y Y Z X Z
X Β ( A) X X
Г) линейность
Отношение нестрогого частичного порядка, так как отношение
не линейно.
Например, A={1,2,3}, B(A)={ ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
{1,2} и {1,3} - несравнимые элементы
6

7. Примеры

3) P={(x,y)| x старше y}, P A2 , где A – студенты одного института
А) антисимметричность
Если x – старше y, y – старше x , то x=y (верно)
Б) транзитивность
Если x – старше y, y – старше z , то x старше z (верно)
В) антирефлексивность
Г) линейность
Для любого x неверно, что x старше x
Существуют несравнимые элементы (студенты одного возраста)
P- отношение частичного строгого порядка
7

8. Примеры

2
4) P={(x,y)| x не младше y}, P A , где A – студенты одного института
В) рефлексивность
Если x – не младше y, y – не младше x , то x,y - одного
возраста, но не обязательно x=y
Если x – не младше y, y – не младше z , то
x не младше z (верно)
Для любого x x не младше x
Г) линейность
Любые студенты сравнимы в этом смысле
А) антисимметричность
Б) транзитивность
P- не является отношением порядка
8

9. Отношение эквивалентности

• Определение 3
Рефлексивное, симметричное, транзитивное отношение называют отношением
эквивалентности.
Обозначение
• Примеры
На множестве студентов, обучающихся на одной специальности одного вуза
P {( x, y ) | x однокурсник y}
задано отношение
1) Рефлексивность
Для любого x - x однокурсник x
2) Симметричность
Если x – однокурсник y, то y – однокурсник x
3) Транзитивность
Если x – однокурсник y, y – однокурсник z,
то x – однокурсник z
x y x однокурсник y
9

10. Отношение эквивалентности

На множестве натуральных чисел задано отношение
Q {( x, y) | x y 5}
1) Рефлексивность
2) Симметричность
x N x x 0 5
x, y N x y 5 y x 5
3) Транзитивность x, y, z N x y 5 y z 5 ( x y) ( y z) x z 5
x y
10

11. Классы эквивалентности

• Определение 4. Система множеств Ai , i I называется
разбиением множества A , если
• а) Ai (i I ) A ,
• б) i , j I A A A A .
i
j
i
j
• Определение 5. Пусть P A - отношение
эквивалентности на A. Классом эквивалентности,
порожденным элементом a A называют множество
2
a x A x ~ a
11

12. Классы эквивалентности

• Теорема. Если P -отношение
эквивалентности на A , то множество
классов эквивалентности образуют
разбиение A .
12

13. Пример

P ( x, y ) N ( x y ) 3 .
2
Перечислите все классы эквивалентности для данного
отношения
a x N x a(mod 3) .
0,1, 2
13