Реферат: Свойства бинарных отношений
Пусть R – отношение на множестве M, RÍM´M. Тогда:
1) R – рефлексивно, если ("aÎM) a R a;
2) R – антирефлексивно, если ни для какого aÎM не выполняется a R a;
3) R – симметрично, если a R b ® b R a;
4) R – антисимметрично, если a R b и b R a влекут a=b, т.е. ни для каких различающихся элементов a и b (а¹b) не выполняется одно-временно a R b и b R a;
5) R – транзитивно, если a R b и b R с ® a R с.
Пример 1.Какими признаками характеризуется матрица отношения R, если R соответственно: рефлексивно, антирефлексивно, симметрично, антисимметрично, транзитивно.
Пусть R задано на M, RÍM´M.
1) R – рефлексивно. Главная диагональ матрицы рефлексивного отношения содержит только единицы: =1;
2) R – антирефлексивно. Главная диагональ матрицы антирефлек-сивного отношения должна содержать только нули: =0;
3) R – симметрично. В матрице симметричного отношения=, т.е. матрица симметрична относительно главной диагонали;
4) R – антисимметрично. В матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали и не лежащие на главной диагонали;
5) R – транзитивно. В матрице такого отношения должно выпол-няться следующее условие: если в i-й строке стоит единица, например, в j-й координате (столбце) строки, т.е. =1, то всем единицам в j-й строке должны соответствовать единицы i-й строке в тех же k-х координатах, т.е. =1 (и, может быть, еще и в других координатах).
Пример 2.Пусть бинарное отношение R на M задано в виде диаграммы, состоящей из узлов и стрелок так, что узлам взаимно однозначно соответствуют элементы множества M, а стрелкам, соединяющим, пару a и b в направлении от a к b, – наличие отношения a R b. Определить графические особенности диаграммы в зависимости от характера свойств отношения R.
1) R – рефлексивною. Соответствующая диаграмма рефлексивного отношения должна содержать петли во всех узлах.
2) R – антирефлексивно. Диаграмма антирефлексивного отношения не должна содержать ни одной петли.
3) R – симметрично. В диаграмме симметричного отношения для каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая эти узлы в обратном направлении.
4) R – антисимметрично. В диаграмме антисимметричного отноше-ния не существует двух различных узлов, связанных парой (разно-направленных) стрелок.
5) R – транзитивно. В диаграмме транзитивного отношения для любых двух стрелок таких, что одна направлена от a к b, а другая – от b к c, существует стрелка, соединяющая a и c в направлении от a к c.
Пример 3.Каковы свойства отношений, заданных:
1. На множестве натуральных чисел N:
а) R1 – “быть не больше £”;
б) R2 – “быть делителем”;
в) R3 – “быть равным”.
2. На множестве точек действительной плоскости ´
а) R4 – “находиться на одинаковом расстоянии от начала координат”;
б) R5 – “быть симметричным относительно оси X”.
3. На системе множеств b(M):
а) R6 – “пересекаться с” (иметь непустое пересечение);
б) R7 – “являться строгим включением Ì”.
4. На множестве людей:
а) R8 – “быть сыном”;
б) R9 – “жить в одном городе”;
в) R10 – “быть братом”.
5. На множестве элементов структуры (рис. 2.2):
а) R11 – “быть непосредственно связанным с”;
б) R12 – “быть начальником”.
1. На множестве N:
а) R1={(a, b): a£b}:
· рефлексивно, не антирефлексивно, так как выполняется а£а для всех аÎM, например 2£2;
· не симметрично, так как 2£3, но неверно, что 3£2;
· антисимметрично, поскольку если a£b, a b£а, то a=b;
· транзитивно, так как если а£b, a b£с, то a£c, например 2£3, 3£4 и 2£4;
б) R2={(a, b): a – делитель b}:
· рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a=1 для всех aÎN;
· не симметрично, антисимметрично, например 2 – делитель 4, но 4 не является делителем 2;
· транзитивно, так как если b/aÎN и c/bÎN, то с/a=b/a × c/bÎN, например, если 6/3=2ÎN и 18/6=3ÎN, то 18/3=18/6 × 6/3=6ÎN;
в) R3={(a, b): a=b}:
· рефлексивно, не антирефлексивно, поскольку a=a для всех aÎN;
· симметрично, так как если a=b, то b=a;
· антисимметрично, так как если a R3 b и b R3 a, то а=b;
· транзитивно, так как если а=b и b=c, то а=с.
2. На множестве точек действительной плоскости ´
а) R4={((x1, y1), (x2, y2)): (x1)2+(y1)2=(x2)2+(y2)2}:
· рефлексивно, не антирефлексивно, так как x2+y2=x2+y2 для любых точек (x, y) действительной плоскости ´
· симметрично, не антисимметрично, так как, например, для точек (2, 3) и (–2, 3) имеет место 22+32=(–2)2+32, но (2, 3)¹(–2, 3);
· транзитивно, поскольку если (x1, y1) и (x2, y2) находятся на одина-ковом расстоянии от начала координат, а также – (x2, y2) и (x3, y3), то и (x1, y1) и (x3, y3) находятся на одинаковом расстоянии от начала координат;
б) R5={((x1, y1), (x2, y2)): x1=x2, y1= –y2}:
· не рефлексивно, так как для точек плоскости (x, y), не находящихся на оси X, т.е. для точек с координатами y¹0, не выполняется (x, y) R5 (x, y);
· не антирефлексивно, так как точка плоскости симметрична самой себе, если она лежит на оси X, т.е. для точек (x, y) с координатами y=0 имеет место (x, y) R5 (x, y);
· симметрично, например (2, 3) R5 (2, –3) и (2, –3) R5 (2, –3);
· не антисимметрично, поскольку имеет место, например, (2, 3) R5 (2, –3) и (2, –3) R5 (2, 3), но (2, –3)¹(2, 3);
· не транзитивно, так как, например, (2, 3) R5 (2, –3) и (2, –3) R5 (2, 3), но не выполняется (2, 3) R5 (2, 3).
3. На системе множеств b(M):
а) R6={(A, B): AÇB¹Æ, A,BÎb(M)}:
· не рефлексивно, поскольку для ÆÎb(M) имеет место ÆÇÆ=Æ;
· не антирефлексивно, так как для AÎb(M), если A не пусто, т.е. A¹Æ, то AÇA=Æ, т.е. отношение выполняется;
· симметрично, так как если A пересекается с B, то и B – с A;
· не антисимметрично, поскольку A R6B и B R6A для A¹B;
· не транзитивно, например {a} R6 {a, b} и {a, b} R6 {b}, но {a} R6 {b} не выполняется;
б) R7={(A, B): AÌB}:
· не рефлексивно, антирефлексивно, так как ни для каких AÎb(M) не выполняется AÌA;
· не симметрично, поскольку из AÌB не следует BÌA;
· антисимметрично, так как ни для каких А, В таких, что A¹B, не выполняется одновременно AÌB и BÌA;
· транзитивно, так как для любых A,B,CÎb(M) из AÌB и BÌC следует AÌC.
4.На множестве людей:
а) R8={(a, b): a – сын b}:
· не рефлексивно, антирефлексивно, так как ни для каких a не выполняется: а – сын а;
· не симметрично, антисимметрично, поскольку ни для каких a¹b не выполняется: а – сын b и b – сын а;
· не транзитивно, так как если: а – сын b и b – сын с, то а – не сын с;
б) R9={(a, b): a живет в одном городе с b}:
· рефлексивно, не антирефлексивно, так как a R9a для всех а;
· симметрично, поскольку для любых а, b, если a R9b, то b R9a;
· не антисимметрично, так как имеет место a R9b и b R9a для а¹b;
· транзитивно, поскольку для всех a, b, c, если a R9b и b R9с, то а R9с;
в) R10={(a, b): a – брат b}:
· не рефлексивно, антирефлексивно из-за очевидного отсутствия a R10a для всех а;
· не симметрично, так как в общем случае между братом а и сестрой b имеет место a R10b, но не b R10a;
· не антисимметрично, так как если а и b – братья, то a R10 b и b R10a, но a¹b;
· транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).
5. На множестве элементов структуры (см. рис. 2.2):
а) R11={(a, b): a – непосредственно связан с b}:
· не рефлексивно, антирефлексивно, если в конкретной интер-претации a R11a не имеет смысла;
· симметрично, не антисимметрично, поскольку для всех a¹b, если выполняется a R11b, то b R11a;
· не транзитивно, так как при a R11b и b R11с не выполняется а R11с (а и с связаны, но опосредованно);
б) R12={(a, b): a – начальник b}:
· не рефлексивно, антирефлексивно (см. R11};
· не симметрично, антисимметрично, так как для всех a¹b не выполняется одновременно a R12 b, то b R12a;
· транзитивно, так как если а – начальник b и b – начальник с, то а – начальник с.
Вопросы для самопроверки и упражнения:
1. Составить матрицы отношений, заданных в примере 3, определив произвольно множество M, RÍM´M таким образом, чтобы по матрице можно было бы судить о свойствах отношения, и назвать эти свойства.
2. Какими свойствами характеризуются следующие отношения на M={1, 2, 3, …, 9}:
а) R1={(a, b): (a–b) – четное};
б) R2={(a, b): (a+b) – четное};
в) R3={(a, b): (a+1) – делитель (a+b)};
г) R4={(a, b): a – делитель (a+b), а¹1}.