Материал: Prak_alg
21
r
определяет
разбиение
множества
C
на
классы
эквивалентности
отно
-
сительно
этого
отношения
.
Совокупность
классов
эквивалентности
элементов
множества
C
по
отношению
эквивалентности
r
называется
фактор
-
множеством
множества
C
по
отношению
r
и
обозначается
r
/
C
.
Рефлексивное
,
антисимметричное
и
транзитивное
отношение
назы
-
вается
отношением
частичного
порядка
на
множестве
C
и
вместо
записи
( )
r
Î
y
x
,
для
данного
отношения
часто
используют
запись
y
x
£
.
Отноше
-
ние
частичного
порядка
на
множестве
C
,
для
которого
любые
два
элемен
-
та
сравнимы
,
т
.
е
.
для
любых
C
Î
y
x
,
выполнено
либо
y
x
£
,
либо
x
y
£
,
называется
отношением
линейного
порядка
.
Множество
C
с
заданным
на
нем
частичным
(
линейным
)
порядком
называется
частично
(
линейно
)
упо
-
рядоченным
.
Пусть
C
–
непустое
конечное
множество
,
на
котором
задано
отноше
-
ние
частичного
порядка
.
Запишем
y
x
<
,
если
y
x
£
и
y
x
¹
.
Говорят
,
что
элемент
y
покрывает
элемент
x
,
если
y
x
<
,
и
не
существует
такого
элемен
-
та
u
,
что
y
u
x
<
<
.
Для
y
x
<
можно
записать
y
x
x
x
x
n
=
<
<
<
=
...
2
1
,
где
1
+
i
x
покрывает
i
x
.
Частично
упорядоченные
множества
можно
изображать
с
помощью
так
называемых
диаграмм
Хассе
.
На
диаграмме
Хассе
элементы
частично
упорядоченного
множества
изображаются
точками
на
плоскости
,
и
если
элемент
y
покрывает
элемент
x
,
то
точки
x
и
y
соединяются
отрезком
,
причем
точку
,
соответствующую
x
,
располагают
ниже
y
.
Пример
1
.
Доказать
,
что
бинарное
отношение
на
множестве
целых
чисел
( )
{
}
y
x
y
x
=
´
Î
=
:
,
Z
Z
r
является
отношением
эквивалентности
,
и
построить
соответствующее
ему
фактор
-
множество
r
/
Z
.
Решение
.
Проверку
рефлексивности
,
симметричности
и
транзитив
-
ности
данного
бинарного
отношения
выполните
самостоятельно
.
Постро
-
им
классы
эквивалентности
для
данного
отношения
эквивалентности
.
Класс
эквивалентности
,
порожденный
любым
элементом
Z
Î
x
,
имеет
вид
[ ]
{
} {
} { }
x
y
x
y
y
x
y
x
=
=
Î
=
»
Î
=
:
:
Z
Z
.
Таким
образом
,
для
данного
отношения
эквивалентности
класс
экви
-
валентности
,
порожденный
элементом
Z
Î
x
,
состоит
только
из
этого
эле
-
мента
,
x
и
фактор
-
множество
r
/
Z
имеет
вид
{ }
{
}
Z
Z
Î
=
x
x
:
/
r
.
22
Пример
2
.
Пусть
m
–
некоторое
натуральное
число
.
Проверить
,
яв
-
ляется
ли
отношением
эквивалентности
следующее
бинарное
отношение
на
множестве
целых
чисел
:
( )
{
}
m
на
делится
y
x
y
x
-
´
Î
=
:
,
Z
Z
r
.
Построить
фактор
-
множество
r
/
Z
.
Решение
.
Проверим
три
основных
свойства
для
отношения
эквива
-
лентности
.
1.
Рефлексивность
.
Для
произвольного
Z
Î
x
разность
( )
r
Î
Þ
×
=
=
-
x
x
m
x
x
,
0
0
.
2.
Симметричность
.
Пусть
( )
( )
.
,
,
r
r
Î
Þ
×
-
=
-
Î
$
Þ
×
=
-
Î
$
Þ
Î
x
y
m
k
x
y
k
m
k
y
x
k
y
x
Z
Z
3.
Транзитивность
.
Пусть
( )
( )
Þ
×
=
-
×
=
-
Z
Î
$
Þ
Î
Î
m
n
z
y
,
m
k
y
x
n
,
k
z
,
y
,
y
,
x
r
r
(
)
(
)
( )
r
Î
Þ
×
=
-
Z
Î
+
=
$
Þ
×
+
=
-
Z
Î
$
Þ
z
,
x
m
r
z
x
m
k
r
m
n
k
z
x
n
,
k
.
Итак
,
исследуемое
бинарное
отношение
является
отношением
экви
-
валентности
.
Построение
классов
эквивалентности
начнем
с
класса
экви
-
валентности
,
порожденного
Z
Î
0
[ ]
{
} {
}
=
-
Î
=
»
Î
=
m
на
делится
y
y
y
y
0
:
0
:
0
Z
Z
{
} {
}
=
×
-
=
Î
$
Î
=
×
=
-
Î
$
Î
=
m
k
y
k
y
m
k
y
k
y
Z
Z
Z
Z
:
0
:
{
}
,...
,
,...,
3
,
3
,
2
,
2
,
,
,
0
km
km
m
m
m
m
m
m
-
-
-
-
=
.
Если
1
=
m
,
то
данный
класс
эквивалентности
[ ]
Z
=
0
,
других
клас
-
сов
эквивалентности
просто
не
существует
,
и
[ ]
{ }
0
/
=
r
Z
.
Если
1
>
m
,
то
существуют
элементы
,
не
попавшие
в
построенный
класс
,
например
,
эле
-
мент
1.
Построим
класс
эквивалентности
,
порожденный
1
[ ]
{
} {
}
=
-
Î
=
»
Î
=
m
на
делится
y
y
y
y
1
:
1
:
1
Z
Z
{
} {
}
=
×
-
=
Î
$
Î
=
×
=
-
Î
$
Î
=
m
k
y
k
y
m
k
y
k
y
1
:
1
:
Z
Z
Z
Z
{
}
,...
1
,
1
,...,
3
1
,
3
1
,
2
1
,
2
1
,
1
,
1
,
1
km
km
m
m
m
m
m
m
+
-
+
-
+
-
+
-
=
.
При
2
=
m
построенные
два
класса
эквивалентности
при
объедине
-
нии
дают
все
множество
,
Ζ
и
поэтому
построение
классов
эквивалентно
-
сти
закончено
,
в
противном
случае
существует
элемент
,
например
3,
не
попавший
ни
в
один
из
этих
классов
эквивалентности
,
и
нужно
перейти
к
построению
класса
эквивалентности
,
порожденного
2.
Продолжая
данный
процесс
,
при
любом
m
мы
построим
классы
эквивалентности
[ ] [ ] [
]
1
,...,
1
,
0
-
m
,
которые
не
пересекаются
и
при
объединении
дают
все
множество
Z
.
Та
-
ким
образом
,
{
}
{
}
1
,...,
2
,
1
:
,...
,
,...,
,
,
/
-
=
+
-
+
-
=
m
n
km
n
km
n
m
n
m
n
n
r
Z
.
23
Пример
3
.
На
плоскости
R
выбрана
некоторая
декартова
прямоуголь
-
ная
система
координат
.
На
R
заданы
три
отношения
эквивалентности
:
(
) (
)
(
)
{
}
Z
R
R
Î
-
=
´
Î
=
2
2
1
1
2
1
2
1
1
,
:
,
,
,
b
a
b
a
b
b
a
a
r
;
(
) (
)
(
)
{
}
Z
Z
R
R
Î
-
Î
-
´
Î
=
2
2
1
1
2
1
2
1
2
,
:
,
,
,
b
a
b
a
b
b
a
a
r
;
(
) (
)
(
)
{
}
Z
R
R
Î
-
+
-
´
Î
=
2
2
1
1
2
1
2
1
3
:
,
,
,
b
a
b
a
b
b
a
a
r
.
Найдите
фактор
-
множества
для
данных
отношений
эквивалентности
.
Решение
.
Построим
фактор
-
множество
для
отношения
1
r
.
Класс
экви
-
валентности
,
порожденный
произвольным
элементом
(
)
R
Î
2
1
,
a
a
,
имеет
вид
(
)
[
]
( )
(
) ( )
(
)
{
} ( )
{
}
=
Î
-
=
Î
=
Î
Î
=
Z
R
R
y
a
a
x
y
x
y
x
a
a
y
x
a
a
2
1
1
2
1
2
1
,
:
,
,
,
,
:
,
,
r
( )
{
}
=
=
-
=
Î
$
Î
=
k
y
a
a
x
k
y
x
2
1
,
:
,
Z
R
( )
{
}
=
-
=
=
Î
$
Î
=
k
a
y
a
x
k
y
x
2
1
,
:
,
Z
R
(
)
{
}
Z
R
Î
Î
-
=
k
k
a
a
:
,
2
1
.
Таким
образом
,
в
класс
эквивалентности
,
порожденный
элементом
(
)
R
Î
2
1
,
a
a
1
0
,
2
1
<
£
Î
a
R
a
,
попадают
вместе
с
элементом
(
)
R
Î
2
1
,
a
a
элементы
,
у
которых
первая
координата
равна
1
a
,
а
вторая
координата
от
-
личается
от
2
a
на
целое
число
.
Классы
эквивалентности
,
порожденные
элементами
с
1
0
,
2
1
<
£
Î
a
R
a
,
не
пересекаются
и
в
объединении
дают
все
множество
R
.
Следовательно
,
фактор
-
множество
1
/
r
R
можно
запи
-
сать
в
виде
(
)
[
)
{
}
1
,
0
,
:
}
:
,
{
/
1
Î
Î
Î
+
=
b
a
b
a
r
R
k
k
Z
R
.
Фактор
-
множество
для
отношений
3
2
,
r
r
постройте
самостоятельно
.
Пример
4
.
Придумайте
минимальное
(
по
числу
элементов
)
отноше
-
ние
эквивалентности
r
на
множестве
{
}
5
,
4
,
3
,
2
,
1
=
A
так
,
чтобы
( )
r
Î
2
,
1
и
( )
r
Î
3
,
2
.
Решение
.
Отношение
эквивалентности
рефлексивно
,
поэтому
дан
-
ному
отношению
обязательно
должны
принадлежать
пары
1,1 ,
( )
2
,
2
,
3,3 ,
( )
4
,
4
,
( )
5
,
5 .
Отношение
эквивалентности
симметрично
,
поэтому
на
-
ряду
с
парами
( )
2
,
1 ,
( )
3
,
2
данному
отношению
обязаны
принадлежать
пары
( )
1
,
2 ,
( )
2
,
3
.
В
силу
транзитивности
отношения
r
ему
обязана
принадле
-
жать
вместе
с
парами
( )
2
,
3
,
( )
1
,
2
пара
( )
1
,
3 (
и
,
следовательно
,
( )
3
,
1 ).
Таким
образом
,
минимальное
отношение
эквивалентности
,
которое
мы
можем
построить
,
имеет
вид
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
{
}
3
1
1
3
2
3
3
2
1
2
2
1
5
5
4
4
3
3
2
2
1
1
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
=
r
.
Пример
5
.
Докажите
,
что
{ } { } { } {
}
{
}
7
6
4
3
5
2
1
,
,
,
,
,
,
=
M
–
разбиение
мно
-
жества
{
}
7
6
5
4
3
2
1
,
,
,
,
,
,
=
A
и
перечислите
все
элементы
отношения
эквива
-
лентности
r
,
соответствующего
разбиению
M
.
24
Решение
.
M
является
разбиением
множества
A
,
поскольку
множе
-
ства
,
являющиеся
элементами
множества
M
,
не
пересекаются
и
при
объе
-
динении
дают
все
множество
A
.
Отношение
эквивалентности
,
соответст
-
вующее
данному
разбиению
,
строится
по
правилу
( )
r
Î
y
x
,
тогда
и
только
тогда
,
когда
x
и
y
принадлежат
одному
подмножеству
разбиения
,
т
.
е
.
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
þ
ý
ü
î
í
ì
=
3
,
3
,
6
,
7
,
7
,
6
,
4
,
7
,
7
,
4
,
4
,
6
,
6
,
4
,
7
,
7
,
6
,
6
,
4
,
4
,
2
,
5
,
5
,
2
,
5
,
5
,
2
,
2
,
1
,
1
r
.
Пример
6.
Покажите
,
что
объединение
двух
отношений
эквивалент
-
ности
может
не
являться
отношением
эквивалентности
.
Решение
.
На
множестве
{
}
5
,
4
,
3
,
2
,
1
=
A
рассмотрим
два
отношения
эквивалентности
( ) ( ) ( ) ( ) ( ) ( )( )
{
}
1
,
2
2
,
1
,
5
,
5
,
4
,
4
,
3
,
3
,
2
,
2
,
1
,
1
1
=
r
;
( ) ( ) ( ) ( ) ( ) ( )( )
{
}
3
,
2
2
,
3
,
5
,
5
,
4
,
4
,
3
,
3
,
2
,
2
,
1
,
1
1
=
r
.
Объединение
данных
отношений
эквивалентности
( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( )
{
}
3
,
2
,
2
,
3
,
1
,
2
2
,
1
,
5
,
5
,
4
,
4
,
3
,
3
,
2
,
2
,
1
,
1
2
1
=
È
r
r
не
является
отношением
эквивалентности
,
так
как
для
него
не
вы
-
полнено
свойство
транзитивности
1
2
3,2
,
(
r
r
1
2
2,1
,
r
r
а
( )
2
1
1
,
3
r
r
È
Ï
)
.
Пример
7
.
Докажите
,
что
отношение
( )
{
}
y
x
R
R
y
x
£
´
Î
=
:
,
r
явля
-
ется
отношением
порядка
на
множестве
R
,
является
ли
это
отношение
от
-
ношением
линейного
порядка
.
Решение
.
Для
доказательства
проверим
три
свойства
данного
отно
-
шения
:
рефлексивность
,
антисимметричность
,
транзитивность
.
1.
Рефлексивность
.
( )
r
Î
Þ
=
Î
"
x
x
x
x
R
x
,
.
2.
Антисимметричность
.
Пусть
( )
r
Î
y
x
,
и
( )
y
x
x
y
y
x
x
y
=
Þ
î
í
ì
£
£
Þ
Î
r
,
.
3.
Транзитивность
.
Пусть
( )
r
Î
y
x
,
и
( )
( )
r
r
Î
Þ
£
Þ
î
í
ì
£
£
Þ
Î
z
x
z
x
z
y
y
x
z
y
,
,
.
Данное
отношение
является
отношением
линейного
порядка
,
так
как
для
любых
R
y
x
Î
,
выполнено
либо
y
x
£
,
либо
x
y
£
.
Пример
8
.
Покажите
,
что
композиция
двух
отношений
частичного
порядка
может
не
являться
отношением
частичного
порядка
.
25
Решение
.
На
множестве
{
}
5
,
4
,
3
,
2
,
1
=
A
рассмотрим
два
отношения
частичного
порядка
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
{
}
3
,
1
,
3
,
2
,
2
,
1
,
5
,
5
,
4
,
4
,
3
,
3
,
2
,
2
,
1
,
1
1
=
r
;
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
{
}
2
,
1
,
2
,
5
,
5
,
1
,
5
,
5
,
4
,
4
,
3
,
3
,
2
,
2
,
1
,
1
2
=
r
.
Однако
композиция
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
{
}
2
,
1
,
2
,
5
,
5
,
1
,
3
,
2
,
2
,
1
,
3
,
1
,
5
,
5
,
4
,
4
,
3
,
3
,
2
,
2
,
1
,
1
1
2
=
r
r
o
не
является
отношением
частичного
порядка
,
так
как
для
него
нарушено
свойство
транзитивности
(
( )
1
2
2
,
5
r
r
o
Î
,
( )
1
2
3
,
2
r
r
o
Î
,
( )
1
2
3
,
5
r
r
o
Ï
).
Пример
9.
Для
следующих
двух
отношений
частичного
порядка
по
-
строить
диаграммы
Хассе
.
1.
{
}
3
,
2
,
1
=
A
,
( )
( ) ( )
{
}
y
x
y
x
Í
´
Î
=
:
,
1
A
R
A
R
r
.
2.
{
}
30
,
15
,
10
,
6
,
5
,
3
,
2
,
1
=
A
,
( )
{
}
x
на
делится
y
y
x
:
,
2
A
A
´
Î
=
r
.
Решение
.
ЗАДАЧИ
И
УПРАЖНЕНИЯ
1.
Докажите
,
что
каждое
из
следующих
отношений
является
отноше
-
нием
эквивалентности
,
и
найдите
классы
эквивалентности
:
1)
( )
( ) ( )
{
}
y
x
y
x
=
´
Î
=
:
,
A
R
A
R
r
,
{
}
3
,
2
,
1
=
A
;
2)
( ) ( )
(
)
{
}
c
b
d
a
d
c
b
a
+
=
+
´
Î
=
:
,
,
,
2
2
N
N
r
;
3)
( )
{
}
;
:
,
2
2
y
x
R
R
y
x
=
´
Î
=
r
4)
( )
( ) ( )
{
}
множество
конечное
y
x
y
x
-
+
´
Î
=
:
,
A
R
A
R
r
,
A
"
.
2.
На
множестве
N
задано
бинарное
отношение
по
следующему
правилу
:
( )
r
Î
y
x
,
тогда
и
только
тогда
,
когда
последняя
цифра
в
десятич
-
ной
записи
числа
x
совпадает
с
последней
цифрой
в
десятичной
записи
{1,2,3}
{1,3}
{1}
{2}
{2,3}
{3}
{1,2}
30
10
2
1
15
6
5
3
1
2
.