Sootvetstvija_funkcii_otnoshenija_lekcii

R1 R2

Рис. 1.15. Композиция отношений

Композиция отношений (или составное отношение) действует из М1 в М2 посредством R1, а затем из М2 в М3 посредством R2 (рис. 1.17).

На рис. 1.17 показаны множества М1, М2, М3, в них – области определений D(R1), D(R2), области значений Q(R1), Q(R2) отношений R1 и R2, заштрихованные в разных направлениях для R1 и R2. Области с двойной штриховкой на М1, М2, М3 представляют собой D(R1 R2), Q(R1) D(R2) и Q(R1 R2) соответственно.

В частности, если отношение R определено на множестве М, т.е. R М М, то можно получить следующую композицию отношений:

R R={(a,b) (a,с) R, (c,b) R}.

Например, если R – «быть сыном», то R R – «быть внуком». Обозначим R R=R(2). Используя это обозначение, можно опреде-

лить степень отношения R(n) для любого n N, n 1 следующим образом:

R(n) ={(a,b) (a,с) R, (c,b) R(n-1)}.

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

1)Отношение R на множестве M называется рефлексивным, если для любого a M имеет место aRa.

Матрица инцидентности рефлексивного отношения, заданного на конечном множестве М, имеет на главной диагонали одни единицы.

Примеры рефлексивного отношения:

« »,

«иметь общий делитель»,

«быть знакомым».

12

Отношение R называется антирефлексивным, если aRa не выполняется ни для одного a M. Главная диагональ матрицы инцидентности такого отношения содержит нули.

Примеры антирефлексивного отношения:

« »,

«быть моложе»,

«быть братом».

Есть отношения, которые не являются ни рефлексивными, ни антирефлексивными. Например, отношение на множестве вещественных чисел R «быть симметричным относительно оси ОХ». Очевидно, что точка плоскости симметрична сама себе тогда и только тогда, когда она лежит на оси абсцисс, и несимметрична сама себе в противном случае.

2) Отношение R называется симметричным, если из aRb следует, что bRa для любой пары (a,b) M2 (иначе говоря, для любой пары отношение R выполняется в обе стороны либо не выполняется вовсе).

Матрица инцидентности такого отношения симметрична относительно главной диагонали, т.е. cij=cji для любых j i. Примеры симметричного отношения: «=», «учиться в одной группе», «быть знакомым».

Очевидно, R – симметрично, если R=R-1.

Отношение R называется антисимметричным, если из aRb и bRa следует, что a=b.

Примеры антисимметричного отношения:

« », т.к. если a b и b a, то a=b;

« », т.к. если A B и B A, то B=A.

Есть отношения, которые не являются ни симметричными, ни антисимметричными. Примером несимметричного отношения является отношение « ».

3) Отношение R на М называется транзитивным, если из aRb и bRc следует, что aRc для любых a,b,c M.

Примеры транзитивного отношения:

« », т.к. если A B и B C, то A C;

« », т.к. если a b и b c, то a c.

«жить в одном городе».

Примеры нетранзитивных отношений R:

«быть родственниками»;

« ».

1.5.5.Виды отношений

1)Транзитивное замыкание

13

Любому отношению R, заданному на множестве М, можно поста-

вить в соответствие отношение R , которое называется транзитивным

замыканием R и определяется следующим образом: a R b, если в М существует конечная цепочка из n элементов a=a1, a2,..., an=b, в которой каждые два соседних элемента находятся в отношении R: a1Ra2, a2Ra3,..., an-1Ran,

т.е. R ={(a,b) (a,a2), (a2,a3),…, (an-1,b) R}.

Унарная операция транзитивного замыкания R может быть также

определена как бесконечное объединение: R =R R(2) R(3) … R(n) … . Например, если отношение R – «быть сыном», R(2) – «быть внуком»,

R(3) – «быть правнуком» и т.д., тогда отношение R - «быть потомком» является транзитивным замыканием отношения R – «быть сыном».

Если отношение R транзитивно, то R =R. Например, транзитивное замыкание отношения R – « » совпадает с самим отношением R.

2) Рефлексивное замыкание

Отношение Е={(а,а) а М} называется тождественным отношением. Тогда отношение

R* = R E

называется рефлексивным замыканием.

Если отношение R транзитивно и рефлексивно, то R*=R.

3) Отношение эквивалентности

Отношение R называется отношением эквивалентности (или просто эквивалентностью), если оно является рефлексивным, симметричным, транзитивным. Обозначается отношение эквивалентности « ».

Примеры отношения эквивалентности:

отношение равенства «=»;

отношение «иметь один и тот же остаток при делении на 3»;

отношение на множестве матриц «иметь один и тот же ранг»;

отношение «иметь один и тот же доход».

Отношение эквивалентности позволяет разбить множество М на классы. А именно, выберем элемент a1 М и образуем класс С1 М, который содержит в себе все элементы, эквивалентные элементу a1 (например, все натуральные числа, дающие при делении на 3 остаток 1). Далее выберем элемент a2 С1 и образуем класс С2 М, который содержит все элемен-

14

ты, эквивалентные элементу а2 и т.д. В результате получим систему классов (подмножеств) С1,С2,…, возможно бесконечную, такую, что:

1) любой элемент а из множества М содержится только в одном классе Сi, т.е. Сi = M, Сi Сj = ;

2)любые два элемента из одного класса эквивалентны;

3)любые два элемента из разных классов не являются эквива-

лентными.

Построенное разбиение, т.е. система классов, называется систе-

мой классов эквивалентности по отношению R или фактор - множе-

ством множества М по отношению эквивалентности R. Обозначается

M R .

Например, если отношение эквивалентности – это отношение равенства на множестве N, то в этом случае класс эквивалентности содержит один элемент, а количество классов бесконечно; если отношение эквивалентности – это отношение «иметь один и тот же остаток при делении на 3», то имеем три класса эквивалентности по остаткам 0,1,2.

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

Часто приходится сталкиваться с отношениями, которые определяют некоторый порядок расположения элементов множества. Так мы рассматриваем понятия «раньше» и «позже» в случаях, когда элементами множества являются состояния динамической системы; отношения «<» или «>», если элементами множества являются числа.

Различают отношения строгого порядка и нестрогого порядка. От-

ношение R на М называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно. Например, отношение « », заданное на множестве N.

Отношение R называется отношением строгого порядка, если оно антирефлексивное, несимметричное и транзитивное. Например, отношение «<», заданное на множестве N.

Элементы a и b называются сравнимыми по отношению R, если выполняется либо aRb, либо bRa.

Множество М, на котором задано отношение R, называется полностью упорядоченным, если любые два элемента этого множества сравнимы, в этом случае отношение R называется отношением линейного порядка. В противном случае, множество М называется частично упорядочен-

ным.

Пример.

Отношения « », « » - отношения нестрогого порядка. Отношения «<», «>» - отношения строгого порядка. Если эти отношения рассмотреть на множестве вещественных чисел R, то они полностью упоря-

15

дочивают данное множество. Введем отношение « » на множестве Rn следующим образом: (a1, a2,…, an) ( b1, b2,…, bn) тогда и только тогда, когда ak bk, k=1,2,…,n. Это отношение определяет частичный порядок на множестве Rn, т.к., например, для n=4 элементы (1,5,3,6) и (5,7,6,10) сравнимы по отношению R, а элементы (1,5,3,6) и (5,4,6,3) несравнимы.

Отношение подчиненности на предприятии задает строгий частичный порядок. В нем несравнимыми являются, например, сотрудники разных отделов.

Отношение предшествования букв в алфавите – отношение строгого порядка.

Пусть А – конечный алфавит, в котором порядок букв зафиксирован (например, алфавит русского языка). Введем на этом множестве отношение предшествования (обозначается « ») следующим образом: ai aj, если ai предшествует aj в алфавите А.

Лексикографическое упорядочение слов.

На основе предшествования букв строится отношение строгого порядка - отношение предшествования слов. Пусть даны слова 1 =

(a11,…,a1m) и 2 = (a21,…,a2m). Тогда слово 1 2, если либо 1= a1j d,2= а2j e, где ,d,e – некоторые слова (возможно, пустые) и a1j а2j ; либо2= 1 , причем - не пустое слово.

Например: стол стул, т.к. о у; стол столб.

16