Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 26 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

Свой ст ва би ек тив ной функ ции f:
а) (f
-1
o f) = e
х
;
б) (f o f
-1
) = e
х
.
1.1.6 Спе ци аль ные би нар ные от но ше ния
А. От но ше ние эк ви ва лент но сти
1) От но ше ние r на мно же ст ве X на зы ва ет ся реф лек сив ным, ес ли
для лю бого эле мен та x Î X вы пол ня ет ся xrx.
2) От но ше ние r на мно же ст ве X на зы ва ет ся сим мет рич ным, ес ли
для лю бых x, y Î X, из xry сле ду ет yrx.
3) От но ше ние r на мно же ст ве X на зы ва ет ся тран зи тив ным, ес ли
для лю бых x, y, z Î X, из xry и yrz сле ду ет xrz.
4) Реф лек сив ное, сим мет рич ное и тран зи тив ное ото бра же ние на
мно жестве X на зы ва ет ся от но ше ни ем эк ви ва лент но сти на мно же ст ве X.
При мер: а) от но ше ние ра вен ст ва на мно же ст ве це лых чи сел есть
отно шение эк ви ва лент но сти;
б) от но ше ние по до бия на мно же ст ве тре уголь ни ков есть отно -
шение эк ви ва лент но сти;
в) от но ше ние x y на мно же ст ве дей ст ви тель ных чи сел не реф лек -
сив но, не сим мет рич но, но тран зи тив но;
г) от но ше ние при над леж но сти к груп пе сту ден тов на мно же ст ве
сту ден тов ин сти ту та — от но ше ние эк ви ва лент но сти.
Итак, пусть r — от но ше ние эк ви ва лент но сти на мно же ст ве X .
5) Клас сом эк ви ва лент но сти, по ро ж дён ным эле мен том x, на зы ва -
ет ся под мно же ст во мно же ст ва X, со стоя щее из тех эле мен тов y Î X, для
ко то рых xry, и обо зна ча ет ся [ x ]: [ x ] = {y | y Î X и xry}.
При мер: для от но ше ния при над леж но сти к груп пе сту ден тов
клас сом эк ви ва лент но сти яв ля ет ся мно же ст во сту ден тов этой груп пы.
26
     Свойства биективной функции f:
     а) (f -1 o f) = eх;
     б) (f o f -1) = eх.

     1.1.6 Специальные бинарные отношения

     А. Отношение эквивалентности
      1) Отношение r на множестве X называется рефлексивным, если
для любого элемента x Î X выполняется xrx.


      2) Отношение r на множестве X называется симметричным, если
для любых x, y Î X, из xry следует yrx.


      3) Отношение r на множестве X называется транзитивным, если
для любых x, y, z Î X, из xry и yrz следует xrz.


    4) Рефлексивное, симметричное и транзитивное отображение на
множестве X называется отношением эквивалентности на множестве X.

      Пример: а) отношение равенства на множестве целых чисел есть
отношение эквивалентности;
      б) отношение подобия на множестве треугольников есть отно-
шение эквивалентности;
      в) отношение x y на множестве действительных чисел не рефлек-
сивно, не симметрично, но транзитивно;
      г) отношение принадлежности к группе студентов на множестве
студентов института — отношение эквивалентности.
      Итак, пусть r — отношение эквивалентности на множестве X.


      5) Классом эквивалентности, порождённым элементом x, называ-
ется подмножество множества X, состоящее из тех элементов y Î X, для
которых xry, и обозначается [ x ]: [ x ] = {y | y Î X и xry}.
      Пример: для отношения принадлежности к группе студентов
классом эквивалентности является множество студентов этой группы.
26

Страницы