Бинарные отношения. Примеры бинарных отношений. Бинарные отношения и их свойства. Специальные бинарные отношения Отношения их виды и свойства
Бинарные отношения.
Пусть A и B – произвольные множества.
Возьмем по одному элементу из каждого множества, a из A, b из B и
запишем их так:
Декартовым
произведением
произвольных множеств A и B (обозначается: AB)
называется множество, состоящее из всех возможных упорядоченных пар, первый
элемент которых принадлежит A, а второй принадлежит B. По определению: AB = {
Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.
AB = {
BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.
AA = A 2 = {
BB = B 2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.
Бинарным
отношением
на множестве M называется множество некоторых
упорядоченных пар элементов множества M. Если r – бинарное отношение и пара
Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.
Пример 7.
Отношение ³ на множестве целых чисел
является бинарным отношением. Это бесконечное множество упорядоченных пар вида
Пример 8.
Отношение равенства на множестве A является бинарным
отношением: I A = {
Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.
Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.
Отношением, обратным
к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = {
Композицией
бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = {
Пример 9. Пусть бинарное отношение r
задано на множестве M = {a, b, c, d}, r = {
Пусть r – бинарное отношение на множестве M. Отношение r
называется рефлексивным
, если x r x для любого x Î M. Отношение r называется симметричным
, если вместе
с каждой парой
Укажем критерии выполнения этих свойств.
Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I M Í r.
Бинарное отношение r симметрично тогда и только тогда, когда r = r ‑1 .
Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r ‑1 = I M .
Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.
Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I A обладает всеми четырьмя рассматриваемыми свойствами. Отношения r ‑1 o r и r o r ‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.
Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.
Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.
Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.
Отношение, заданное на множестве, может обладать рядом свойств, а именно:
2. Рефлексивность
Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.
Используя символы, это отношение можно записать в таком виде:
R рефлексивно на Х Û("х Î Х ) х R х
Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.
Граф рефлексивного отношения во всех вершинах имеет петли.
2. Антирефлексивность
Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.
R антирефлексивно на Х Û("х Î Х )
Пример. Отношение «прямая х перпендикулярна прямой у » на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.
Граф антирефлексивного отношения не содержит ни одной петли.
Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у » на множестве точек плоскости.
Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.
3. Симметричность
Определение . Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у , следует, что и элемент у находится в отношении R с элементом х .
R симметричнона Х Û("х , у Î Х ) х R у Þ у R х
Пример. Отношение «прямая х пересекает прямую у на множестве прямых плоскости» симметрично, т.к. если прямая х пересекает прямую у , то и прямая у обязательно будет пересекать прямую х .
Граф симметричного отношения вместе с каждой стрелкой из точки х в точку у должен содержать стрелку, соединяющую те же точки, но в обратном направлении.
4. Асимметричность
Определение . Отношение R намножестве Х называется асимметричным, если ни для каких элементов х , у из множества Х не может случиться, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х .
R асимметричнона Х Û("х , у Î Х ) х R у Þ
Пример. Отношение «х < у » асимметрично, т.к. ни для какой пары элементов х , у нельзя сказать, что одновременно х < у и у < х .
Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.
5. Антисимметричность
Определение . Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у , а у находится в отношении с х следует, что х = у.
R антисимметричнона Х Û("х , у Î Х ) х R у Ù у R х Þ х = у
Пример. Отношение «х £ у » антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.
Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.
6. Транзитивность
Определение . Отношение R намножестве Х называется транзитивным, если для любых элементов х , у , z из множества Х из того, что х находится в отношении с у , а у находится в отношении с z следует, что х находится в отношении с z.
R транзитивнона Х Û("х , у , z Î Х ) х R у Ù у R z Þ х R z
Пример. Отношение «х кратно у » транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.
Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.
7. Связность
Определение . Отношение R намножестве Х называется связным, если для любых элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .
R связнона Х Û("х , у , z Î Х ) х R у Ú у R z Ú х = у
Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .
Пример. Отношение «х < у » связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.
На графе связного отношения все вершины соединены между собой стрелками.
Пример. Проверить, какими свойствами обладает
отношение «х – делитель у », заданное на множестве
Х = {2; 3; 4; 6; 8}.
1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;
2) свойством антирефлексивности данное отношение не обладает;
3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;
4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;
5) отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;
6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.
Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.
§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы
Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:
1) рефлексивности, т.к. каждый студент является однокурсником самому себе;
2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;
3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .
Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.
Отношением эквивалентности являются также, например, отношение параллельности прямых, отношение равенства фигур. Каждое такое отношение связано с разбиением множества на классы.
Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).
Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?
Построим граф данного отношения:
Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.
Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.
В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».
Бинарным отношением Т(М) на множестве М называется подмножество М 2 = М х М, Т(М) с М 2 . Формальная запись бинарного отношения выглядит шкТ(М) = {(х, у) / (х, у) е Т с М х М}. Обратите внимание: далее мы будем рассматривать только не пустые множества Ми заданные на них непустые бинарные отношения Т(М)
Понятие «бинарное отношение» является более общим понятием, чем функция. Каждая функция представляет собой бинарное отношение, но не каждое бинарное отношение есть функция.
Например, множество пар Р = {(а, Ь), (а, с), (а, б)} является бинарным отношением на множестве {а, Ъ, с, (1), но функцией не является. И наоборот, функция Р= {(а, Ь),(Ь, с), (с1, а)} является бинарным отношением, заданным на множестве {а, Ь, с, с!}.
Мы уже сталкивались с понятием отношения при рассмотрении с (включение) и = (равенство) между множествами. Также неоднократно вами использовались отношения =, Ф, , заданные на множестве чисел - как натуральных, так и целых, рациональных, вещественных и т.д.
Определим несколько понятий относительно бинарного отношения, заданного на множестве М[ 2, 11].
Обратное отношение
Я-"= {(х, у) / (у, х) € Я). (1.14)
Дополнительное отношение
Л = {(*, У) / (х, у) й /?}. (1.15)
Тождественное отношение
и = {(х, х) / X Е М). (1.16)
Универсальное отношение
I ={(х,у)/хеМ,уеМ}. (1.17)
Рассмотрим несколько задач.
Задача 1.8
На множестве М= {а, Ь, с, с1 , е} задано бинарное отношение Т(М ) = = {{а, а ), (а , Ь ), (Ь , с), (с, ?/), (^/, б), {б, е)}. Построить отношения : обратное к Т , дополнительное к Т, тождественное бинарное отношение и и универсальное бинарное отношение /.
Решение.
Для решения этих задач нам нужны только определения.
По определению на множестве М= {а , Ь , с, б, е} обратное к ДЛ/) бинарное отношение должно содержать все обратные пары тождественное бинарное отношение Т~ = {(а , а ), (/?, я), (с, 6), (б, с), (^/, ?/), (с, б)}.
По определению на множестве М= {а, Ь, с , б, е} дополнительное к Т(М ) бинарное отношение должно содержать все пары из декартова произведения М 2 , которые не принадлежат Т(М), т.е. {(а , с), {а, Л), (а, е), (Ь, а), (Ь, Ь), (Ь, б), (Ь, е), (с, а), (с, Ь), (с, с), (с, е), {б, а), (б, Ь), (б, с), (е, а), (е, Ь), (е, с), (е, б), (е, е)}.
По определению на множестве М = {а, Ь, с, б , е} тождественное бинарное отношение и = {(а, а ), (Ь , /?), (с, с), (^/, ^/), (е, е)}.
По определению на множестве М = {а , 6, с, б, е} универсальное бинарное отношение содержит все пары из декартова произведения М 2 , т.е. / = {(а, а), (а , А), (о, с), (а,), (я, е), (Ь, а), (Ь, Ь), (Ь, с), (Ь, б), (Ь, е), (с, а), (с, Л), (с, с), (с, йО, (с, е), (б, а), (б , А), (, с), (,), (^,
Задача 1.9
На множестве М натуральных чисел от 1 до 5 построить бинарное отношение R = {(а , d) / mod(? r , Z>) = 0}, где mod - остаток от деления а на Ь.
Решение.
В соответствии с заданием на множестве натуральных чисел М строим такие пары (а , Ь), где а делится на b без остатка, т.е. mod(?, Ъ ) = = 0. Получаем R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (4, 1), (5, 1), (4, 2)}.
Существует несколько основных способов задания бинарных отношений: перечисление, графическое представление, матричное представление.
Бинарные отношения R можно задать в виде перечисления, как любое множество пар.
При графическом представлении каждый элемент х и у множества М представляется вершиной, а пара (х, у) представляется дугой изх в у.
Матричным способом бинарные отношения задаются с помощью матрицы смежности. Такой способ наиболее удобен при решении задач с помощью компьютера.
Матрица смежности S представляет собой квадратную матрицу тх/й, где т - мощность множества М, и каждый ее элемент 5(х, у) равен единице, если пара (х, у) принадлежит Т(М), и равен нулю в противном случае.
На рис. 1.3 представлено графическое и матричное представление для Т(М) = {(а , а), (а, Ъ), (b , с), (с, d), (d , d), (d, e)}.
Определяя свойства бинарных отношений, обычно выделяют рефлексивность, симметричность и транзитивность.
Бинарное отношение Т(М) называется рефлексивным тогда и только тогда, когда для каждого элемента х е М пара (х, х) принадлежит этому бинарному отношению Т(М), т.е. Vx е М, 3(х, х) е Т(М).
Рис. 1.3. Графическое (а) и матричное (б) представление множества
Классическим определением этого свойства является следующее утверждение: из того, что элемент х принадлежит множеству М, следует, что пара (х, х) принадлежит бинарному отношению Т(М), заданному на этом множестве, т.е. /хєМ-) (х, х) є Т(М).
Прямо противоположное свойство бинарных отношений называется иррефлексивностью. Бинарное отношение Т(М) называется иррефлексивным тогда и только тогда, когда для каждого элемента х из множества М пара (х, х) не принадлежит этому бинарному отношению, т.е. /х є М -> (х, х) ё Т(М).
Если бинарное отношение Т(М) не обладает ни свойством рефлексивности, ни свойством иррефлексивности, то оно является нерефлексивным.
Например, для множества М - {а, Ь, с , ^/, е} бинарное отношение Т Х (М) = {(а , а), (а, Ь), (Ь, Ь), (Ь, с), (с, с), (с, сі), (сі, сі), (сі , с), (е, е )} является рефлексивным, Т 2 (М) = {(а , Ь), (Ь , с), (с, сі), (сі, с), (сі, е )} является иррефлексивным, а Т 3 (М) = {(а , а ), (а, Ь), (Ь , с), (с, сі), (сі , ?/), (?/, с)} является нерефлексивным.
Если во множестве М содержится хотя бы один элемент х, то правильная классификация не представляет сложности. Обратите внимание: для однозначности решения задачи классификации свойство рефлексивности следует определять только для непустых множеств!
В соответствии с этим бинарное отношение на пустом множестве является нерефлексивным, так же как нерефлексивным будет пустое бинарное отношение.
Бинарное отношение Т(М) называется симметричным тогда и только тогда, когда для каждой пары различных элементов (х, у), принадлежащей бинарному отношению Т(М), обратная пара (у, х) также принадлежит этому бинарному отношению, т.е. /(х, у) є Т(М), 3(у, х) є Т(М). Свойство симметричности мы определяем только для множеств, содержащих хотя бы два различных элемента, и непустых бинарных отношений.
Классическим определением свойства симметричности является следующее утверждение: из того, что пара (х, у) принадлежит Т(М), следует, что обратная пара (у, х) также принадлежит Т(М), т.е. /(х, у) є Т(М) -> (у, х) є Т(М). В этом случае еслих = у, то свойство симметричности плавно переходит в рефлексивность.
Прямо противоположное свойство бинарных отношений называется антисимметричностью. Бинарное отношение Т(М) называется антисимметричным тогда и только тогда, когда для каждой пары различных элементов х и у пара (у, х) не принадлежит этому бинарному отношению, т.е. /(х, у) є Т(М), (у, х) і Т(М).
Классическим определением антисимметричности можно считать следующее . Из того, что в антисимметричном бинарном отношении Т(М) для любой пары (х, у) обратная пара (у, х) также принадлежит Т(М), следует, что х = у, т.е. ((х, у) е Т(М), (у , х) е Т(М )) -> -> х = у.
Если бинарное отношение Т(М ) не обладает ни свойством симметричности, ни свойством антисимметричности, то оно является несимметричным.
В случае когда Мили Т(М) пусты или М содержит единственный элемент х, наше бинарное отношение одновременно является как симметричным, так и антисимметричным. Для однозначности решения задачи классификации множество М должно содержать хотя бы два различных элемента х и у. Тогда бинарные отношения на пустом множестве, так же как на множествах с одним элементом, являются несимметричными.
М - {а, Ь, с, ^/, е}. Бинарное отношение Г, = {(а , а), (а, Ь ), (Ь , а ), (с, с1), (с /, с), (е , с), (с, е)} является симметричным, Т 2 = {(а, а), (а, Ь), (с, с1), (е , с), (с, Ь ), (Ь , е )} является антисимметричным, Т 3 = {(а, а ), (а , Ь ), (6, я), (с, с1), (е , с), (с, я)} - несимметричным. Обратите внимание: петля (а , я) никак не влияет на симметричность и антисимметричность.
Свойство транзитивности определяется на трех различных элементах х, у и I множества М. Бинарное отношение Т(М) называется транзитивным тогда и только тогда, когда для каждых двух пар различных элементов (х, у) и (у, О, принадлежащих бинарному отношению Т(М), пара (х, ?) также принадлежит этому бинарному отношению, т.е. (/(х, у) е Т(М), /(у, I) е Т(М)), 3(х, I) е Т(М). Таким образом, между элементами х и ^ существует транзитивное замыкание («транзит»), которое «спрямляет» путь длины два (х, у) и (у, z)?
Классическое определение свойства транзитивности формулируется следующим образом: из того, что в транзитивном бинарном отношении Т(М) существует пара (х, у) и пара (у, I), следует, что пара (х, I) также принадлежит этому бинарному отношению, т.е. ((х, у) е Т(М ), (у, I) е Т(М)) -э (х, I) е Т(М ).
Бинарное отношение Т(М) называется интранзитивным тогда и только тогда, когда для каждых двух пар элементов (х, у) и (у, ?), принадлежащих бинарному отношению Т(М), пара (х, не принадлежит этому бинарному отношению, т.е. (/(х, у) е Т(М), /(у, I) е Т{М)), (х, I) ? Т(М). Таким образом, в интранзитивном бинарном отношении ни один имеющийся путь длины два не обладает транзитивным замыканием!
Классическое определение свойства интранзитивности формулируется следующим образом: из того, что в транзитивном бинарном отношении Т(М) существует пара (х, у) и пара (у, I), следует, что пара (х, I) не принадлежит этому бинарному отношению, т.е. ((*, у) е Т(М), (у, I) е Т(М)) -э (х, I) ? Т(М).
Если бинарное отношение Т(М) не обладает ни свойством транзитивности, ни свойством интранзитивности, то оно является нетранзитивным.
Например, рассмотрим множество М - {а , Ь, с, б, е}. Бинарное отношение Т х = {(а , а), (а , Ь ), (а , с), (Ь , с), (с, с), (е , с)} является транзитивным, Т 2 = {(я, я), (я, 6), (6, с), (с, 1), (?, 0} является интранзитив-ным, Т 3 = {(а , я), (я, 6), (6, с), (^/, с), (я, с), (е , ?/)} - нетранзитивным.
Задача 1.10
На множестве М х - {а, Ь, с, б, е} построить бинарное отношение Я с заданными свойствами : нерефлексивности , антисимметричности и нетранзитивности.
Решение.
Правильных решений этой задачи целое множество! Построим одно из них. В нашем бинарном отношении на некоторых вершинах, но не на всех, должны быть петли; не должно быть ни одной обратной дуги; должны быть хотя бы два пути длины 2, из них хотя бы один не иметь транзитивного замыкания. Таким образом, получаем Я = {(а, а), (Ь , Ь ), (а , Ь ), (Ь , с), (с, б), (б, е), (а, с), (с, е)}.
Задача 1.11
Определить свойства бинарного отношения Т, заданного на множестве М 2 = {а, Ь, с, б, е}, представленного ранее на рис. 1.3.
Решение.
В данном бинарном отношении на двух вершинах есть петли, на трех петель нет, следовательно, бинарное отношении нерефлексивно. Нет ни одной обратной дуги, следовательно, бинарное отношение антисимметрично. Бинарное отношение обладает несколькими путями длины два, но ни один из них не обладает транзитивным замыканием - Т интранзитивно.
Элементы множества, как правило, находятся в каком-либо отношении друг относительно друга. Эти отношения можно задать в виде неполных предложений -- предикатов, например, «меньше, чем...», «больше, чем...», «эквивалентно», «конгруэнтно» и т. п.
Тот факт, что некоторый элемент находится в каком-либо отношении к элементу того же множества x j , математически записывают как XiRxj, где R -- символ отношения.
Отношение из двух элементов множества X называют бинарным. Бинарные отношения множеств X и Y представляют собой некоторое множество упорядоченных пар (х, у), образованных декартовым произведением X х Y. В общем случае можно говорить не только о множестве упорядоченных пар, но и о множестве упорядоченных троек, четверок элементов и т. д., т. е. о парных отношениях, получаемых в результате декартова произведения , где п -- размерность n -строчек.
Рассмотрим основные виды отношений -- отношения эквивалентности, порядка и доминирования.
Некоторые элементы множеств можно считать эквивалентными в том случае, когда любой из этих элементов при определенных условиях можно заменить другим, т. е. данные элементы находятся вот-ношении эквивалентности. Примерами отношений эквивалентности являются отношения параллельности на множестве прямых какой-либо плоскости; подобия на множестве треугольников; принадлежности к одной функциональной группе микросхем или к одному классу типоразмеров и т. д.
Термин «отношение эквивалентности» будем применять при выполнении следующих условий:
1) каждый элемент эквивалентен самому себе;
2) высказывание, что два элемента являются эквивалентными, не требует уточнения того, какой из элементов рассматривается первым, а какой вторым;
3) два элемента, эквивалентные третьему, эквивалентны между собой.
Введем для обозначения эквивалентности символ ~, тогда рассмотренные условия можно записать следующим образом:
1) х ~ х (рефлективность);
2) х ~ уу ~ х (симметричность);
3) х ~ у и у ~ z х ~ z (транзитивность).
Следовательно, отношение R называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пусть некоторому элементу х X эквивалентно некоторое подмножество элементов А X, тогда это подмножество образует класс эквивалентности, эквивалентный х. Очевидно, что все элементы одного и того же класса эквивалентности эквивалентны между собой (свойство транзитивности). Тогда всякий элемент хХ может находиться в одном и только одном классе эквивалентности, т. е. в этом случае множество X разбивается на некоторое непересекающееся подмножество классов эквивалентности , где J -- некоторое множество индексов.
Таким образом, каждому отношению эквивалентности на множестве X соответствует некоторое разбиение множества X на классы.
Часто сталкиваются с отношениями, которые определяют некоторый порядок расположения элементов множества. Например, в процессе автоматизированного конструирования требуется вводить множество одних исходных данных раньше или позже, чем множество других. При этом может оказаться, что элементы одного множества больше или меньше элементов другого и т. д. Во всех этих случаях можно расположить элементы множества X или группы элементов в некотором порядке (например, в виде убывающей или возрастающей последовательности), т. е. ввести отношение порядка на множестве X.
Различают отношения строгого порядка, для которых применяют символы и отношения нестрогого порядка, где используют символы. Эти отношения характеризуются следующими свойствами:
для отношения строгого порядка:
х
х<У, а У<х -- взаимоисключаются (несимметричность);
x<у и у
для отношения нестрогого порядка:
х X -- истинно (рефлексивность);
ху и ух х = у -- (антисимметричность);
х у и у z xу z -- (транзитивность).
Множество X называют упорядоченным, если любые два элемента х и у этого множества сравнимы, т. е. если для них выполняется одно из условий: х < у, х = у, у < х.
Упорядоченное множество называют кортежем. В общем случае кортеж -- это последовательность элементов, т. е. совокупность элементов, в которой каждый элемент занимает вполне определенное место. Элементы упорядоченного множества называются компонентами кортежа. Примерами кортежа может служить упорядоченная последовательность чисел арифметической или геометрической прогрессий, последовательность технологических операций при изготовлении какого-либо радиоэлектронного изделия, упорядоченная последовательность установочных позиций печатной платы для закрепления конструктивных элементов.
Во всех этих множествах место каждого элемента вполне определено и не может произвольно изменяться.
При обработке конструкторской информации на ЭВМ часто используют отношения доминирования. Говорят, что хX доминирует над уX, т. е. х>>у, если элемент х в чем-либо превосходит (имеет приоритет) элемент у того же множества. Например, под х можно понимать один из списков данных, который должен поступить на обработку первым. При анализе нескольких конструкций РЭА какой-либо из них должен быть отдан приоритет, так как эта конструкция обладает лучшими, с нашей точки зрения, свойствами, чем другие, т. е. конструкция х доминирует над конструкцией у.
Свойство транзитивности при этом не имеет места. Действительно, если, например, конструкцию х по каким-либо одним параметрам предпочли конструкции у, а конструкцию у по каким-либо другим параметрам предпочли конструкции z, то отсюда еще не следует, что конструкции х должно быть отдано предпочтение по сравнению с конструкцией г.
Отображение множеств. Одним из основных понятий теории множеств является понятие отображения. Если заданы два непустых множества X и Y, то закон, согласно которому каждому элементу xX ставится в соответствие элемента, называют однозначным отображением X в Y или функцией, определенной на X и принимающей значение на Y.
На практике приходится иметь дело и с многозначными отображениями множества X на множестве Y, которые определяют закон, согласно которому каждому элементу хX ставится в соответствие некоторое подмножество , называемое образом элементов. Возможны случаи, когда Гх = 0.
Пусть задано некоторое подмножество АX. Для любого хА образом х является подмножество . Совокупность всех элементов Y, являющихся образами для всех х в А, назовем образом множества А и будем обозначать ГА. В этом случае
Само понятие «отношение», конечно, вам знакомо. Мы часто его употребляем в речи. Например, мы можем сказать, что я в хороших отношениях со всеми студентами моей группы.
В жизни мы постоянно находимся в различных отношениях и вступаем в различные отношения. С членами своей семьи мы находимся в отношении родства, со школьными товарищами - в отношении дружбы, с руководителями учреждения, где мы учимся или работаем, - в отношении подчинения и т.д. В этом смысле отношение - это определенный характер связи .
В параграфе 2.2 мы говорили об отношениях, которые существуют между математическими объектами. Так, элемент по отношению к множеству находится в отношении принадлежности, два множества могут находиться в отношении включения или равенства.
Сейчас мы рассмотрим отношения, которые могут существовать между элементами множеств. Итак, мы сказали, что отношение, установленное между элементами множеств в рассмотренном примере, называется бинарными.
По существу в примере мы составили сначала декартово произведение заданных множеств, т.е. множество всех пар элементов этих множеств, так, что первый элемент пары принадлежит первому множеству, а второй - второму. Затем мы из множества этих пар выбрали подмножество тех пар, которые показывают, на каком же факультете учится каждый из студентов.
Определение 2.8. Бинарным отношением между множествами Ли В называется любое подмножество декартова произведения Ах В.
Бинарные отношения обычно обозначают буквами греческого алфавита: р («ро»), а («сигма»), |/ («пси») и др.
Если р - некоторое бинарное отношение между множествами А и В, то согласно определению бинарного отношения мы можем записать, что р с с Л х В.
Если пара (а, b ) принадлежит бинарному отношению р, т.е. (а, b ) е р, то говорят, что элемент а находится в отношении р с элементом b , и пишут арб. Так, в приведенном выше примере рассмотрено отношение «учиться на факультете». Тогда можно сказать, что Петр находится в данном отношении с факультетом математики.
Для некоторых отношений в математике существуют определенные знаки. Например,
В связи с тем что бинарное отношение - это множество пар, то, как любое множество, его можно задать либо перечислением этих пар, либо указанием характеристического свойства для выделения из декартова произведения пар, принадлежащих данному отношению.
Пример 2.6
Пусть заданы два числовых множества: А = {1, 3,5} и В = {2, 8, 10}. Зададим бинарное отношение о между этими множествами перечислением: а = {(1, 2), (5, 10)}. Это же отношение мы может задать и характеристическим свойством: бинарное отношение образуют пары чисел, такие что число из первого множества в два раза меньше числа из второго множества.
Пример 2.7
Рассмотрим множество студентов вашей академической группы. Установим в этом множестве отношение «быть другом». Для любой пары студентов академической группы можно сказать, находятся они в данном отношении или нет. Может даже случиться так, что это бинарное отношение будет образовывать пустое множество. В каком случае это будет?
В последнем примере нужно обратить внимание на то, что мы устанавливали отношение не между элементами двух множеств, а между элементами одного множества. Это также возможно и не противоречит определению бинарного отношения. Только в этом случае вместо декартова произведения двух множеств нужно рассмотреть декартов квадрат множества.
Бинарное отношение, заданное на множестве, может иметь разные свойства. Рассмотрим их.
1. Свойство рефлексивности.
Определение 2.9. рефлексивным , если для любого а е Л пара (а> а) е р.
Отношение «
2. Свойство симметричности.
Определение 2.10. Говорят, что бинарное отношение р, заданное на множестве Л, является симметричным , если для любых элементов а и b из Л из того, что пара (а , b ) находится в отношении р, следует, что пара (b , а) находится в отношении р.
Например, отношение равенства, заданное на множестве действительных чисел, симметрично, так как если число k равно числу п } то и число п равно числу k. Симметричным является и отношение «быть другом».
С другой стороны, отношение упорядоченности по величине (
3. Свойство антисимметричности.
Определение 2.11. Говорят, что бинарное отношение р, заданное на множестве Л, является антисимметричным у если для любых элементов а и b из Л из того, что пары (я, /;) и (/;, а) находятся в отношении р, следует, что а = Ь.
Например, отношение упорядоченности по величине на множестве действительных чисел антисимметрично. Ведь если известно, что для чисел х и у выполнено х и у то это означает, что х - у. А вот отношение параллельности прямых не является антисимметричным, так как если прямая / параллельна прямой t и прямая t параллельна прямой /, то это не означает, что прямые / и t совпадают. Они могут быть различны.
4. Свойство транзитивности.
Определение 2.12. Говорят, что бинарное отношение р, заданное на множестве Л, является транзитивным у если для любых элементов а , b и с из Л из того, что пары (я, b ) и (/?, с) находятся в отношении р, следует, что пара (а, с) также находится в отношении р.
Свойством транзитивности обладают отношения упорядоченности по величине, параллельности, отношение «быть родственником».
Отношение перпендикулярности прямых не является транзитивным (покажите это с помощью рисунка). Также по существу не является транзитивным и отношение «быть другом» (хотя и есть присказка, в которой выражено желание о транзитивности этого отношения: «Друг моего друга - мой друг»).
Мы рассмотрели только основные свойства бинарных отношений, которые определяют два широко используемых типа отношений.
Отношением эквивалентности (или эквивалентностью) называется бинарное отношение, которое обладает свойствами рефлексивности, симметричности и транзитивности.
Отношением упорядоченности (или упорядоченностью) называется бинарное отношение, которое обладает свойствами рефлексивности, антисимметричности и транзитивности.
Например, отношение «быть одноклассником» является эквивалентностью, так как оно обладает свойством рефлексивности, симметричности и транзитивности. Отношение «быть не выше ростом» на множестве людей является отношением упорядоченности.
Отношения эквивалентности и упорядоченности имеют очень важное значение в различных областях математики, а эквивалентность используется при выполнении классификаций различных объектов. Для того чтобы это понять, обратимся сначала к такому математическому понятию, как разбиение множества.
Определение 2.13. Разбиением множества/! называется представление этого множества в виде объединения непересекающихся подмножеств, которые называются классами разбиения.
Чтобы проверить, что мы имеем дело с разбиением множества, нужно проверить два условия:
- объединение полученных при разбиении подмножеств является исходным множеством;
- пересечение любых двух различных подмножеств является пустым множеством.
При выполнении классификации классами разбиения являются так называемые классы эквивалентности. Как же строятся эти классы?
Пусть на множестве А введено некоторое отношение эквивалентности р. Возьмем любой элемент а из А и все элементы из А, которые находятся с а в отношении р. Все эти элементы и будут образовывать класс эквивалентности элемента а. Понятно, что и сам элемент а попадет в этот класс. Действительно, если р - отношение эквивалентности, то оно обладает свойством рефлексивности, т.е. (а } а) е р, а это и означает, что сам элемент а входит в класс эквивалентности, который он образует.
Можно доказать, что классы эквивалентности различных элементов множества либо совпадают, либо не пересекаются. В связи с этим можно предположить, что эти классы могут рассматриваться в качестве классов разбиения.
Действительно, существует теорема, которая говорит о том, что если на множестве задано отношение эквивалентности, то множество всех классов эквивалентности, содержащих элементы этого множества, является разбиением этого множества.
С другой стороны, можно доказать, что если есть некоторое разбиение множества и на этом множестве задано бинарное отношение так, что пара элементов множества находится в этом отношении только при условии, что они оба принадлежат одному классу разбиения, то это бинарное отношение будет эквивалентностью.
Можно попробовать доказать каждое из этих утверждений самостоятельно или разобрать доказательство, которое приведено в работе .
При использовании классов эквивалентности мы разбиваем множество на подмножества, в каждое из которых входят своего рода «одинаковые» элементы. Например, множество всех положительных дробей можно разбить на классы эквивалентности таким образом: 1) взять каждую несокра-
тимую дробь (например, -); 2) в каждый класс эквивалентности соответ-
2 4 6 8 ч т
ствующеи дроби отнести все равные ей дроби - = - = - = 1аким
образом, мы разобьем все положительные дроби на соответствующие классы эквивалентности. Каждый такой класс является положительным рациональным числом.
- В Большой советской энциклопедии говорится, что «отношение - эмоционально-волевая установка личности на что-либо, т.е. выражение ее позиции; мысленное сопоставление различных объектов или сторон данного объекта». В толковом словаре Д. Н. Ушакова«отношение - взаимное общение, связь между людьми, обществами, странами и т.п., образующаяся из общения на какой-нибудь почве».
