Измени отношения к вещам, которые тебя беспокоют, и ты будешь от них в безопасности.
Марк Аврелий
Глава 4. Отношения
Отношения, определение и способы задания отношений,основные операции над отношениями, свойства специальных отношений, разбиение множеств, отношение эквивалентности, отношение порядка, отношение квазипорядка, частичного порядка и доминирования
ЦЕЛИ
Освоив эту главу, студенты должны:
· знать способы задания отношений;
· знать основные свойства отношений;
· уметь решать задачи на доказательство тождеств с отношениями;
· знать понятия отношения рефлексивности, симметричности, трназитивности и эквивалентности;
· уметь выполнять разбиение множеств;
· иметь понятие об отношении порядка.
4.1. Основные понятия отношений
Отношение определяет в какой связи любые объекты в природе находятся между собой. На формальном языке отношение — это пара множеств, причем упорядоченная, первая компонента которой является подмножеством квадрата второй компоненты.
В отличие от понятия множества, понятие отношения является определенным понятием. Запись j = < Ф, М > - называется отношением, если ФÍМ2, т.е. ФÍМ х М, где j — отношение; Ф — график отношения; М — область задания отношения, представляющая из себя неупорядоченное множество. Отношение такого типа называется бинарным. Если ФÍМk, то отношение называется k-арным.
Отношение j с областью задания М называется отношением на множестве М.
Пусть имеем элемент графика, представлдяющий собой пару < a, b >ÎФ. Тогда говорят, что если пара < a, b >ÎФ, то существует отношение a j b, в котором элементы a и b находятся в некоторой связи. Другими словами, элемент a находится в отношении j к элементу b. Если a и b - элементы множества М (a, bÎM), то a j b будет являться истинным или ложным высказыванием.
Рассмотрим некоторые примеры отношений.
1) Пусть дана область задания отношения М = { 1, 2, 3, 4 } и график отношения Ф = { < 1, 1 >, < 1, 2 >, < 2, 2 >, < 3, 2 > }. Тогда можно получить М2 = М × М = { < 1, 1 >, < 1, 2 >, < 1, 3 >, < 1, 4 >, < 2, 1 >, < 2, 2 >,..., < 4, 4 > }. На рис. 4.1 точками изображено отношение j = < Ф, М >.
Рис. 4.1. Пример задания отношения на множестве М
Отметим, что отношение часто задают рисунками, изображая на координатной плоскости график определяемого отношения. Причем в отношение входят соответствующие точки графика.
Отношение также может быть задано в виде графа (рис. 4.2).
Рис. 4.2. Пример задания отношения в виде графа
Существует еще один способ задания отношений через высказывательные формы.
Например, запись х j y ® x < y означает, что j есть «отношение меньше» между элементами x и y.
Тогда высказывание «5 j 3» является ложным отношением, а высказывание 3 j 4 является истинным отношением.
Важным в отношениях является понятие диагонали j = <DМ, M> на множестве М. Это такое отношение, когда все точки графика находятся на диагонали. Например, пусть в отношении j = < DМ, М >, М = { 1, 2, 3, 4 } и график отношения DМ = {< 1, 1 >, < 2, 2 >, < 3, 3 >, < 4, 4 >}. На рис. 4.3 показано графическое представление такого отношения.
Рис. 4.3. Пример отношения
4.2. Основные свойства отношений
Отношение j = <Ф, М> называется полным отношением, если Ф = М2, т.е. ("x,yÎM)(x j y). Другими словами, для любых элементов x, y, принадлежащих множеству М, истинно высказывание, что элементы x, y находятся в отношении j.
Отношение j = < Ф, М > называется пустым, если график Ф является пустым множеством. То есть j = < Æ, М >. Другими словами, имеется область задания отношения, на котором не задан график отношения.
Отношение j = < Ф, М > называется отношением равенства, если Ф = DМ. В теоретико-множественном плане можно записать, ("x,yÎM)(x j y ® x = y). Например задано j = < Ф, М >, М = { 1, 2, 3 }, Ф = {<1, 1>, <2, 2>, <3, 3>}. Данное отношение является отношением равенства.
Отношение j = < Ф, М > называется отношением неравенства, если Ф = М2\DМ, т.е. ("x,yÎM)(x j y ® x ¹ y). Например задано j = < Ф, М >, М = { 1, 2, 3 }, Ф = {< 1, 2 >, < 2, 3 >, < 3, 1 > }. Данное отношение является отношением неравенства. Отношения «5 > 3» и «3 < 10» также являются примерами отношения неравенства.
4.3. Операции над отношениями
На отношения переносятся основные операции над множествами, но они могут выполняться только на одной и той же области задания.
Объединением отношений j1 и j2 на множестве М называется отношение j3:
j1Èj2 = j3, j1 = < Ф1, М >, j2 = < Ф2, М >.
j3 = < Ф1ÈФ2, М >,
<a, b> Î Ф1 È Ф2 ® <a, b> Î Ф1 Ú <a, b> Î Ф2 & a, bÎ M.
Например, пусть имеем два отношения: j1 = < Ф1, М >, j2 = < Ф2, М >,
М = { 2, 3, 4 }, Ф1 = { <2, 1>, <2, 2>, <2, 4> },
Ф2 = { < 2, 1 >, < 2, 3 >, < 4, 4 > }.
Тогда объединение этих отношений j3 = < Ф3, М >, Ф3 = Ф1È Ф2 = { <2,1>, <2,2>, <2,4>, <2,3>, <4,4> }.
Отметим, что для операции объединения над отношениями справедлива следующая запись:
x (j1Èj2) y ® x j1 y Ú x j2 y.
Пересечением отношений j1 и j2 на множестве М называется отношение j3, для которого:
j1Çj2 = j3, j1 = < Ф1, М >, j2 = < Ф2, М >,
j3 = < Ф1ÇФ2, М >,
<a, b> Î Ф1 Ç Ф2 ® <a, b> Î Ф1 & <a, b> Î Ф2 & a, bÎ M.
Например, пусть имеем два отношения: j1 = < Ф1, М >, j2 = < Ф2, М >, M = {1, 2}, j1 = <{<1, 1>, <1, 2>}, {1, 2}>, j2 = < {< 1, 2 >, < 2, 2 >}, { 1, 2 }>,
Тогда пересечение этих отношений j3 = <Ф3, М> = <{< 1, 2 >}, {1, 2}>.
Отметим, что для операции пересечения над отношениями справедлива следующая запись:
x (j1Çj2) y ® x j1 y & x j2 y.
Операции объединения и пересечения также, как и для множеств применимы для любого числа отношений.
Отношение j3 называется разностью отношений j1 и j2, если
j1 = <Ф1, М>, j2 = <Ф2, М>, j3 = j1\j2 = <Ф1\Ф2, М>,
<a, b> Î Ф1 \ Ф2 ® <a, b> Î Ф1 & <a, b> Ï Ф2 & a, bÎ M.
Например, пусть имеем два отношения: j1 = <Ф1, М>, j2 = <Ф2, М>, M = {1, 2, 3}, Ф1 = {<1, 2>, <2, 2>, <3, 3>}, Ф2 = {<1, 1>, <2, 2>, <3, 3>}. Тогда Ф3 = Ф1\Ф2 = {<1, 2>}. Разность этих отношений j3 = <Ф3, М> = < {<1, 2>}, {1, 2, 3}>.
Отметим, что для операции разности над отношениями справедлива следующая запись:
x (j1\j2) y ® x j1 y & x 
y.
Над отношения выполняются также операции инверсии и композиции.
Если j = < Ф, М >, то инверсия j-1 = < Ф-1, М >.
Для того, чтобы найти инверсию отношения, необходимо проинвертировать элементы его графика на множестве М. Отметим, что для операции инверсии над отношениями справедлива следующая запись:
х j-1 у ® у j х.
Например, для отношения j = <Ф, М>, М = {1, 2, 3}, Ф = {<1, 1>, <1, 2>, <1, 3>}, инверсия j-1 = <Ф-1, М> и Ф-1 = {<1, 1>, <2, 1>, <3, 1>}.
Композицией двух отношений является новое отношение, у которого компонируют графики отношений.
j1 = <Ф1, M>, j2 = <Ф2, M>.
j1•j2 = <Ф1•Ф2, М>
Например, j1 = <Ф1, M>, j2 = <Ф2, M>, М = {1, 2, 3}, Ф1 = {<1, 1>, <1, 2>, <1, 3>, <3, 3> }, Ф2 = {<1, 1>, <2, 3>, <3, 1>, <3, 2>}. Тогда композиция графиков этих отношений равна Ф1•Ф2={<1, 1>,<1, 3>,<1, 2>, <3, 2>, <3, 1>}.
Отметим, что все операции над отношениями могут выполняться только на одной и той же области задания, и в результате выполнения операций снова получается отношение с той же самой областью задания.
Введем операцию, меняющую область задания отношений.
Пусть j = < Ф, М > и $АÍМ, тогда сужением отношения j на множестве А называется новое отношение
j1 = < ФÇА2, А >
Например, j = < Ф, М >, М = { 1, 2, 3 }, Ф = {< 1, 1 >, < 1, 2 >, <1, 3> }, A = {1, 2}. Тогда j1 = <{< 1, 1 >, < 1, 2 >}, {1, 2}>.
4.4. Основные свойства специальных отношений
Отношение j = < Ф, М > называется отношением рефлексивности, если
("хÎМ)(х j х).
Другими словами, если для любого элемента хÎМ истинно высказывание х j х, то j - отношение рефлексивности. Это отношение является унарной операцией, т.е. операцией над одним элементом. Примерами отношения рефлексивности являются отношение равенства и отношение параллельности (x = x, x || x). Очевидно, что отношение перпендикулярности между прямыми х и у не является отношением рефлексивности. Отношение j рефлексивно тогда и только тогда, когда D М Í Ф, т.е. когда все точки диагонали принадлежат графику отношений.
Отношение j = < Ф, М > называется отношением антирефлексивности, если
("хÎМ)Ø(х j х),
т.е. D М Ç Ф = Æ.
Например, выражения x > x, x ¹ x, x ^ x являются отношениями антирефлексивности.
Отношение j = < Ф, М > называют отношением симметричности, если
("х,уÎМ)(х j у ® у j х).
Отношение симметричности является бинарной операцией. Например, выражения х=у, хïêу являются отношением симметричности.
Для графика отношения симметричности справедливо Ф = Ф-1. Например, a = b ® b = a, a ïêb ® b ïê a.
Отношение j = < Ф, М >, Ф Í МхМ называется отношением антисимметричности, если
