ВходБинарные отношения. Примеры бинарных отношений
Отношение, заданное на множестве, может обладать рядом свойств, а именно:
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}.
Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.
В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».
В повседневной жизни нам постоянно приходится сталкиваться с понятием «отношения». Отношения – один из способов задания взаимосвязей между элементами множества.
Унарные (одноместные) отношения отражают наличие какого-то одного признака R у элементов множества M (например, «быть красным» на множестве шаров в урне).
Бинарные (двуместные) отношения используются для определения взаимо
связей, которыми характеризуются пары элементов во множестве M .
Например, на множестве людей могут быть заданы следующие отношения: «жить в одном городе», «x работает под руководством y », «быть сыном», «быть старше» и т.д. на множестве чисел: «число a больше числа b », «число a является делителем числа b », «числа a и b дают одинаковый остаток при делении на 3».
В прямом произведении , где A - множество студентов какого-либо вуза, B - множество изучаемых предметов, можно выделить большое подмножество упорядоченных пар (a, b) , обладающих свойством: «студент a изучает предмет b ». Построенное подмножество отражает отношение «изучает», возникающее между множествами студентов и предметов. Число примеров можно продолжить
Отношения между двумя объектами являются предметом исследования экономики, географии, биологии, физики, лингвистики, математики и других наук.
Для строгого математического описания любых связей между элементами двух множеств вводится понятие бинарного отношения.
Бинарным отношением между множествами A и B называется подмножество R прямого произведения . В том случае, когда можно просто говорить об отношении R на A .
Пример 1 . Выпишите упорядоченные пары, принадлежащие бинарным отношениям R 1 и R 2 , заданными на множествах A и : , . Подмножество R 1 состоит из пар: . Подмножество .
Область определения R на есть множество всех элементов из A таких, что для некоторых элементов имеем . Иными словами область определения R есть множество всех первых координат упорядоченных пар из R .
Множество значений отношения R на есть множество всех таких, что для некоторых . Другими словами множество значений R есть множество всех вторых координат упорядоченных пар из R .
В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .
Во многих случаях удобно использовать графическое изображение бинарного отношения. Оно осуществляется двумя способами: с помощью точек на плоскости и с помощью стрелок.
В первом случае выбирают две взаимно перпендикулярные линии в качестве горизонтальной и вертикальной осей. На горизонтальной оси откладывают элементы множества A и через каждую точку проводят вертикальную линию. На вертикальной оси откладывают элементы множества B , через каждую точку проводят горизонтальную линию. Точки пересечения горизонтальных и вертикальных линий изображают элементы прямого произведения .
Пример 5 . Пусть , .
Пусть R 1 задано на перечислением упорядоченных пар: . Бинарное отношение R 2 на множестве задано с помощью правила: упорядочена пара , если a делится на b . Тогда R 2 состоит из пар: .
Бинарные отношения, из примера 2, R 1 и R 2 изображены графически на рис. 6 и рис.7.
| | |||||||||||||||||||||||||
Рис. 6 Рис. 7
Чтобы изобразить бинарное отношение с помощью стрелок, слева изображаются точками элементы множества A , справа - множества B . Для каждой пары (a, b) , содержащейся в бинарном отношении R , проводится стрелка от a к b , . Графическое изображение бинарного отношения R 1 , приведенного в примере 6, показано на рис.8.
| Рис.8 |
Бинарные отношения на конечных множествах могут быть заданы матрицами. Предположим, что задано бинарное отношение R между множествами A и B . , .
Строки матрицы нумеруются элементами множества A , а столбцы – элементами множества B . Ячейку матрицы, стоящую на пересечении i - ой строки и j - ого столбца принято обозначать через C ij , а заполняется она следующим образом:
Полученная матрица будет иметь размер .
Пример 6. Пусть задано множество . На множестве задайте списком и матрицей отношение R – «быть строго меньше».
Отношение R как множество содержит все пары элементов (a , b) из M такие, что .
Матрица отношения, построенная по вышеуказанным правилам, имеет следующий вид:
Свойства бинарных отношений:
1. Бинарное отношение R на множестве называетсярефлексивным , если для любого элемента a из M пара (a, a) принадлежит R , т.е. имеет место для любого a из M :
Отношения «жить в одном городе», «учиться в одном вузе», «быть не больше» являются рефлексивными.
2. Бинарное отношение называется антирефлексивным ,если оно не обладает свойством рефлексивности для любых a :
Например, «быть больше», «быть младше» - это антирефлексивные отношения .
3. Бинарное отношение R называется симметричным , если для любых элементов a и b из M из того, что пара (a, b) принадлежит R , , вытекает, что пара (b, a) принадлежит R , т.е.
Симметрична параллельность прямых, т.к. если // , то // . Симметрично отношение «быть равным» на любом множестве или «быть взаимнопростым на N».
Отношение R симметрично тогда и только тогда, когда R=R -1
4. Если для несовпадающих элементов верно отношение , но ложно , то отношение антисимметрично . Можно сказать иначе:
Антисимметричными являются отношения «быть больше», «быть делителем на N», «быть младше».
5. Бинарное отношение R называется транзитивным , если для любых трех элементов из того, что пары (a, b) и (b, c) принадлежат R , следует, что пара (a, c) принадлежит R :
Транзитивны отношения : «быть больше», «быть параллельным», «быть равным» и др.
6. Бинарное отношение R антитранзитивно , если оно не обладает свойством транзитивности.
Например, «быть перпендикулярным» на множестве прямых плоскости ( , , но неверно, что ).
Т.к. бинарное отношение может быть задано не только прямым перечислением пар, но и матрицей, то целесообразно выяснить, какими признаками характеризуется матрица отношения R , если оно: 1) рефлексивно, 2) антирефлексивно, 3)симметрично, 4) антисимметрично, 5) транзитивно.
Пусть R задано на , .R либо выполняется в обе стороны, либо не выполняется вообще. Таким образом, если в матрице стоит единица на пересечении i - ой строки и j - ого столбца, т.е. C ij =1, то она должна стоять и на пересечении j - ой строки и i - ого столбца, т.е. C ji =1, и наоборот, если C ji =1, то C ij =1. Таким образом, матрица симметричного отношения симметрична относительно главной диагонали.
4. R антисимметрично, если из и следует: . Это означает, что в соответствующей матрице ни для каких i , j не выполняется C ij = C ji =1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали .
5. Бинарное отношение R на непустом множестве A называется транзитивным если
Вышеприведенное условие должно выполняться для любых элементов матрицы. И, наоборот, если в матрице R имеется хотя бы один элемент C ij =1, для которого данное условие не выполняется, то R не транзитивно.
Свойства отношений:
1) рефлексивность;
2)симметричность;
3)транзитивность.
4)связанность.
Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: х Rх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.
Примерами рефлексивных отношений являются и отношение «кратно» на множестве натуральных чисел (каждое число кратно самому себе), и отношение подобия треугольников (каждый треугольник подобен самому себе), и отношение «равенства» (каждое число равно самому себе) и др.
Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.
Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.
Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно х Rх: .
Существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Примером такого отношения может служить отношение «точка х симметрична точке у относительно прямой l », заданное на множестве точек плоскости. Действительно, все точки прямой l симметричны сами себе, а точки, не лежащие на прямой l, себе не симметричны.
Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .
Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y , граф содержит стрелку, идущую от y к х (рис. 35).
Примерами симметричных отношений могут быть следующие: отношение «параллельности» отрезков, отношение «перпендикулярности» отрезков, отношение «равенства» отрезков, отношение подобия треугольников, отношение «равенства» дробей и др.
Существуют отношения, которые не обладают свойством симметричности.
Действительно, если отрезок х длиннее отрезка у , то отрезок у не может быть длиннее отрезка х . Граф этого отношения обладает особенностью: стрелка, соединяющая вершины, направлена только в одну сторону.
Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.
Кроме отношения «длиннее» на множестве отрезков существуют и другие антисимметричные отношения. Например, отношение «больше» для чисел (если х больше у , то у не может быть больше х ), отношение «больше на» и др.
Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.
Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRz xRz.
Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z , содержит стрелку, идущую от х к z.
Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а= b, b=с)(а=с).
Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b , а отрезок b перпендикулярен отрезку с , то отрезки а и с не перпендикулярны!
Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.
Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y , либо элемент y находится в отношении R с элементом х . С помощью символов это можно записать так: xy xRy или yRx.
Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y , либо y>x.
На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.
Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y , что ни число х не является делителем числа y , ни число y не является делителем числа х (числа 17 и 11 , 3 и 10 и т.д.).
Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y ». Построим граф данного отношения и сформулируем его свойства.
Про отношение равенства дробей говорят, оно является отношением эквивалентности.
Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.
Примерами отношений эквивалентности могут служить: отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными).
В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.
Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества - классы эквивалентности.
Так, мы установили, что отношению равенства на множестве
Х
={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.
Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?
Во-первых, эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {; ; }, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.
Во-вторых, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. свойства, присущие некоторому классу, рассматриваются на одном его представителе.
В-третьих, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные прямые между собой.
Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х ={3, 4, 5, 6, 7, 8, 9, 10 } задано отношение «иметь один и тот же остаток при делении на 3 ». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9 ). Во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10 ). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8 ). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х . Следовательно, отношение «иметь один и тот же остаток при делении на 3 », заданное на множестве Х , является отношением эквивалентности.
Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».
Отношение R на множестве Х называется отношением строгого порядка , если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х< y ».
Если же отношение обладает свойствами рефлексивности, антисимметричности и транзитивности, то такое оно будет являться отношением нестрогого порядка . Например, отношение «х y ».
Примерами отношения порядка могут служить: отношение «меньше» на множестве натуральных чисел, отношение «короче» на множестве отрезков. Если отношение порядка обладает еще и свойством связанности, то говорят, что оно является отношением линейного порядка . Например, отношение «меньше» на множестве натуральных чисел.
Множество Х называется упорядоченным, если на нем задано отношение порядка.
Например, множество Х= {2, 8, 12, 32 } можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х , а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.
Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.
Бинарные отношения.
Пусть 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 = М х М, Т(М) с М 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.
Решение.
В данном бинарном отношении на двух вершинах есть петли, на трех петель нет, следовательно, бинарное отношении нерефлексивно. Нет ни одной обратной дуги, следовательно, бинарное отношение антисимметрично. Бинарное отношение обладает несколькими путями длины два, но ни один из них не обладает транзитивным замыканием - Т интранзитивно.