Для отношения заданного на множестве выяснить какими свойствами
Свойства отношений:
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 и yRzxRz.
Граф транзитивного отношения с каждой парой стрелок, идущих от х к 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.
Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.
Введение в теорию множеств и комбинаторику
Практическая работа № 6. Бинарные отношения
Вопросы к работе
1. Что такое “бинарное отношение на множестве”?
2. Как можно записать бинарное отношение?
3. Какое отношение называют рефлексивным?
4. Какое отношение не является рефлексивным?
5. Какое отношение называют симметричным?
6. Какое отношение не является симметричным?
7. Какое отношение называют транзитивным?
8. Какое отношение не является транзитивным?
9. Что такое «эквивалентность на множестве»?
10.Какое отношение называют порядком?
11.Какие вы знаете еще специальные типы отношений?
Образцы решения заданий
Пример 1. Дано множество A = {1; 2; 3; 4; 5; 6} 
N. На нем задано бинарное отношение 
«больше», т. е. (x, y) 
<=> x > у. Построить граф и график этого отношения. Какими свойствами обладает это отношение?
Решение. 1) Граф указанного отношения:
2) строим график этого отношения:
3) Рефлексивность. Если бы это отношение было рефлексивным, то x > x для 
А. Например, было бы верно 2 > 2 (ложь ). Значит отношение «>» на А не является рефлексивным.
Симметричность. Если бы это отношение было симметричным на множестве А, то x > у => у > х. Например, 3 > 2 => 2 > 3(ложь). Значит, отношение « > » на А не является симметричным.
Транзитивность. Если бы это отношение было транзитивным на множестве А, то x > у, у > z => x > z. Это утверждение истинно для любых натуральных чисел, т. е. и чисел из А. Значит, отношение « > » на А является транзитивным.
Асимметричность: Ни для каких чисел A не может быть одновременно истинным 
, т. е. отношение «>» на A асимметрично. Отношение « > » на множестве A является отношением строгого порядка, т. к. оно асимметрично и транзитивно.
отношение «>» на множестве A является связным. Т. к. отношение «>» на множестве А связное и является отношением строгого порядка, то оно есть отношение строгого линейного порядка.
Пример 2. На множестве людей Земли введено бинарное отношение «быть родственником по крови». Будет ли это отношение отношением эквивалентности?
Решение. Обозначим через A множество людей Земли, а заданное отношение буквой 
. Тогда x
у <=> человек x является родственником человека у. Что бы отношение 
было отношением эквивалентности, оно должно быть рефлексивным, симметричным, транзитивным.
Рефлексивность. Если бы 
было рефлексивным, то было бы верно: 
x
x, т. е. любой человек Земли является родственником самому себе (истина), т. е. отношение 
на A рефлексивно.
Симметричность. Если бы 
было симметрично. (x
y => y
x), т. е. если бы человек x был родственником человека у, то у был бы родственником человека x (истина). Значит, отношение 
на A симметрично.
Транзитивность. Если бы 
было транзитивно на A, то если бы человек x был бы родственником человека у, а у был родственником человека z, то x был бы родственником z. Но это не обязательно. Например, человек x родственник для y по матери, а у – родственник для z по отцу. Тогда x и у могут не быть родственниками по крови. Значит, отношение 
на А не является транзитивным.
Следовательно, отношение «быть родственником по крови» на множестве людей Земли не является отношением эквивалентности.
Пример 3. Построить граф отношения «легче, чем» на множестве A = {кролик, заяц, собака, поросёнок}, если известно, что заяц тяжелее собаки, кролик легче поросёнка, а собака тяжелее поросёнка. Кто из животных самый легкий, кто – самый тяжелый.
Решение. Строим граф указанного отношения:
Итог: кролик – самый легкий, заяц – самый тяжелый.
Упражнения
1. Найдите область определения рr1
и область значений рr2
каждого из следующих отношений, заданных на множестве
А = {1; 2; 3; …,10} 
N, и укажите, какими свойствами оно обладает:
1) а
b <=> а — b = 8;
2) а
b <=> b = а2;
3) а
b <=> аb = 12;
4) а
b <=> b > а2.
2. На множестве А = {3; 5; 7; 9; 11} 
N задано отношение x > у. Выпишите все пары элементов, находящиеся в этом отношении.
3. Построить граф отношения 
:
x
у <=> x = у + 2 на множестве
{–3; –1; 1; 2; 3; 4} 
Z.
4. На множестве Y ={ у | у 
Z , –13 ≤ у ≤ –2 } задано отношение R:
xRу <=> x = 2у.
Какие из следующих записей верны:
а) (–6; –3) 
R; б) (–3; –6) 
R;
в) (–4; –2) 
R; г) (–8; 4) 
R.
5.На множестве М = {–8; –6; –4; –2; 0; 2; 4} 
Z задано отношение 
: x
у <=> число x кратно числу у. Запишите множество 
, перечислив все его элементы. Принадлежит ли 
пара (– 4;– 4)? Найдите 
(2), 
(–8), 
(0). Найдите 
-1(4), 
-1(–6), 
-1(0). Что значит отношение х
у? Найдите 
(–4), 
(–2).
6. Дано множество числовых выражений
М = {10; –2
•3; (8 – 5
)•3;
11
•2 – 15,9(16
)}. Постройте граф этого отношения «меньше, чем» на этом множестве.
7.Множество М членов семьи Смирновых состоит из отца (Ивана Михайловича), матери (Елены Андреевны) и четырёх детей: Миши, Тани, Васи и Оли. Между членами семьи существуют отношения родства, которые можно выразить словами: «быть мужем», «быть братом» и т. д.
а) укажите всевозможные отношения на множестве М;
б) запишите отношения «быть дочерью» с указанием всех его элементов и построить граф этого отношения;
в) постройте графы отношений «быть братом», «быть матерью».
8. На рис. 16 изображен граф отношения «а брат в» на множестве детей нашего двора {А; Б; В; Г; Д; Е; Ж; 3; И}. Кто из них является мальчиком? Кто девочкой? О ком нельзя по этому графу ничего сказать?
Рис. 16
9. Класс выставил на соревнования по плаванию команду мальчиков. В нее входили: Витя, Коля, Андрей и Саша. Коля проплыл дистанцию быстрее Андрея, но медленнее Саши, Андрей затратил на ту же дистанцию времени больше, чем Витя, который плавал медленнее Коли. Как распределились места на соревнованиях.(3адачу решите с помощью построения графа соответствующего бинарного отношения).
10. М – множество озер Канады. На М задано бинарное отношение «иметь одинаковый объем воды». Будет ли это отношение эквивалентностью?
9. Класс выставил на соревнования по плаванию команду мальчиков. В нее входили: Витя, Коля, Андрей и Саша. Коля проплыл дистанцию быстрее Андрея, но медленнее Саши, Андрей затратил на ту же дистанцию времени больше, чем Витя, который плавал медленнее Коли. Как распределились места на соревнованиях.(3адачу решите с помощью построения графа соответствующего бинарного отношения).
10. М – множество озер Канады. На М задано бинарное отношение «иметь одинаковый объем воды». Будет ли это отношение эквивалентностью?
Индивидуальные задания
1. На множестве N для каждого из следующих отношений найдите область определения рr1
и область значений рr2
и укажите, какими свойствами оно обладает:
1) х
у 
НОД (х; у) = 1;
2) ху 
у < 2х;
3) х
у 
х = у2;
4) х
у 
х ≤ у;
5) х
у 
у — х = 12;
6) х
у
|у — х| = 12;
7) х
у 
(х — у) : 3;
8) х
у 
х у = 30;
9) х
у 
х < у + 1;
10) х
у 
у = 2х + 1.
2. Будет ли заданное отношение эквивалентностью на указанном множестве:
1) «иметь одинаковую высоту» (на множестве гор в Европе);
2) «находиться на одинаковой высоте над уровнем моря» (для всех населенных пунктов Тибета);
3) «иметь одинаковую протяженность» (для всех рек России);
4) «иметь одинаковую загрязненность санитарной зоны предприятия» (для всех предприятий Смоленска);
5) «иметь численность населения не менее 5000 человек» (для всех населенных пунктов Подмосковья);
6) «иметь одинаковую степень риска извержения» (для всех вулканов Земли);
7) «иметь общую границу» (для всех государств Европы);
8) «иметь общие экономические интересы на Ближнем Востоке» (для всех государств – членов ООН);
9) «иметь одинаковую глубину» (для всех ущелий Кавказа);
10) «быть равноудаленными от Москвы» (на множестве городов России).
Задания для самоконтроля
1. Пусть 
и σ отношения эквивалентности на множестве М. Докажите или опровергните, что 
σ и 
σ – есть отношения эквивалентности.
2. Известно, что отношение 
– отношение эквивалентности. Дополните граф этого отношения.
Лекция 3.
п.3. Отношения на множествах. Свойства бинарных отношений.
3.1. Бинарные отношения.
Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).
В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A´B) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S´K можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.
Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.
Определение 3.1. Бинарным (или двухместным) отношением r между множествами A и B называется произвольное подмножество A´B, т. е.
.
В частности, если A=B (то есть rÍA2), то говорят, что r есть отношение на множестве A.
Элементы a и b называются компонентами (или координатами) отношения r.
Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит: r, t, j, s, w и т. д.
Определение 3.2. Областью определения бинарного отношения r называется множество Dr={a | $ b, что arb} (левая часть). Областью значений бинарного отношения r называется множество Rr={b | $ a, что arb} (правая часть).
Пример 3.1. Пусть даны два множества A={1; 3; 5; 7} и B={2; 4; 6}. Отношение зададим следующим образом t={(x; y)ÎA´B | x+y=9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере Dt={3; 5; 7} и Rt= B={2; 4; 6}.
,
Пример 3.2. Отношение равенства на множестве действительных чисел есть множество r={(x; y) | x и y – действительные числа и x равно y}. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, Dr= Rr.
,
Пример 3.3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x; y)ÎA´B | y – цена x} – отношение множеств A и B.
,
Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x; y)ÎA´B | x+y=9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.
Способы задания отношений:
1) с помощью подходящего предиката;
2) множество упорядоченных пар;
3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.
4) в виде матрицы: пусть A={a1, a2, …, an} и B={b1, b2, …, bm}, r – отношение на A´B. Матричным представлением r называется матрица M=[mij] размера n´m, определенная соотношениями
.
Кстати, матричное представление является представлением отношения в компьютере.
Пример 3.4. Пусть даны два множества A={1; 3; 5; 7}и B={2; 4; 6}. Отношение задано следующим образом t={(x; y) | x+y=9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.
Решение. 1) t={(3; 6), (5; 4), (7; 2)} — есть задание отношения как множества упорядоченных пар;
2) соответствующий ориентированный граф показан на рисунке.
3) в матричном представлении это отношение имеет вид
. ,
Пример 3.5. Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M:
,
где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.
Рассмотрим информационный обмен между устройствами mi и mj, которые находятся в отношении r, если из устройства mi поступает информация в устройство mj.
Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:
Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:
Матричное представление этого бинарного отношения имеет вид:
. ,
Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.
Введем обобщенное понятие отношения.
Определение 3.3. n-местное (n—арное) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей)
rÍA1´…´An={(a1, …, an)| a1ÎA1Ù … ÙanÎAn}
Многоместные отношения удобно задавать с помощью реляционных таблиц. Такое задание соответствует перечислению множества n-к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных. Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.
Слово «реляционная» происходит от латинского слова relation, которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).
Далее мы будем рассматривать только двухместные (бинарные) отношения, при этом опуская слово «бинарные».
Определение 3.4. Пусть rÍA´B есть отношение на A´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A´B, которое определяется следующим образом:
r-1={(b, a) | (a, b)Îr}.
Определение 3.5. Пусть r ÍA´B есть отношение на A´B, а s ÍB´C – отношение на B´C. Композицией отношений s и r называется отношение t ÍA´C,которое определяется следующим образом:
t=s◦r= {(a, c)| $ b Î B, что (a, b)Îr и (b, c)Îs}.
Пример 3.6. Пусть , и C={,, !, d, à}. И пусть отношение r на A´B и отношение s на B´C заданы в виде:
r={(1, x), (1, y), (3, x)};
s={(x, ,), (x, !), (y, d), (y, à)}.
Найти r-1 и s◦r, r◦s.
Решение. 1) По определению r-1={(x, 1), (y, 1), (x, 3)};
2) Используя определение композиции двух отношений, получаем
s◦r={(1, ,), (1, !), (1, d), (1, à), (3, ,), (3, !)},
поскольку из (1, x)Îr и (x, ,)Îs следует (1, ,)Îs◦r;
из (1, x)Îr и (x, !)Îs следует (1, !)Îs◦r;
из (1, y)Îr и (y, d)Îs следует (1, d)Îs◦r;
…
из (3, x)Îr и (x, !)Îs следует (3, !)Îs◦r.
3) r◦s=Æ.
,
Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:
1) ;
2) ;
3) — ассоциативность композиции.
Доказательство. Свойство 1 очевидно.
Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a; b) Î (s◦r)-1 Û (b; a) Î s◦r Û $ c такое, что (b; c) Î r и (c; a) Î s Û $ c такое, что (c; b) Î r-1 и (a; c) Î s-1 Û (a; b) Î r -1◦s -1.
Свойство 3 доказать самостоятельно.
■
3.2. Свойства бинарных отношений.
Рассмотрим специальные свойства бинарных отношений на множестве A.
Свойства бинарных отношений.
1. Отношение r на A´A называется рефлексивным, если (a,a) принадлежит r для всех a из A.
2. Отношение r называется антирефлексивным, если из (a,b)Îr следует a¹b.
3. Отношение r симметрично, если для a и b, принадлежащих A, из (a,b)Îr следует, что (b,a)Îr.
4. Отношение r называется антисимметричным, если для a и b из A, из принадлежности (a,b) и (b,a) отношению r следует, что a=b.
5. Отношение r транзитивно, если для a, b и c из A из того, что (a,b)Îr и (b,c)Îr, следует, что (a,c)Îr.
Пример 3.7. Пусть A={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?
Решение. 1) Это отношение рефлексивно, так как для каждого aÎA, (a; a)Îr.
2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.
3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:
Случай | (a, b)Îr | (b, a) | (b, a)Îr? |
1 | (1; 2) | (2; 1) | Да |
2 | (1; 4) | (4; 1) | Да |
3 | (2; 1) | (1; 2) | Да |
… | … | … | … |
4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.
5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.
Случай | (a, b)Îr | (b, c)Îr | (a, c) | (a, c)Îr? |
1 | (1; 2) | (2; 1) | (1; 1) | Да |
2 | (1; 2) | (2; 2) | (1; 2) | Да |
3 | (1; 2) | (2; 4) | (1; 4) | Да |
4 | (1; 4) | (4; 1) | (1; 1) | Да |
5 | (1; 4) | (4; 2) | (1; 2) | Да |
… | … | … | … | … |
,
Как по матрице представления
определить свойства бинарного отношения
1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.
.
2. Антирефлексивность: на главной диагонали все нули.
3. Симметричность: если .
4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.
.
Операция «*» выполняется по следующему правилу: , где , .
5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .
3.3 Отношение эквивалентности. Отношение частичного порядка.
Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.
Определение 3.6. Отношение r на A есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности arb часто обозначается: a ~ b.
Пример 3.8. Отношение равенства на множестве целых чисел есть отношение эквивалентности.
,
Пример 3.9. Отношение «одного роста» есть отношение эквивалентности на множеств