![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть 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:
а) R 1 – “быть не больше £”;
б) R 2 – “быть делителем”;
в) R 3 – “быть равным”.
2. На множестве точек действительной плоскости ´
а) R 4 – “находиться на одинаковом расстоянии от начала координат”;
б) R 5 – “быть симметричным относительно оси X ”.
3. На системе множеств b(M):
а) R 6 – “пересекаться с” (иметь непустое пересечение);
б) R 7 – “являться строгим включением Ì”.
4. На множестве людей:
а) R 8 – “быть сыном”;
б) R 9 – “жить в одном городе”;
в) R 10 – “быть братом”.
5. На множестве элементов структуры (рис. 2.2):
а) R 11 – “быть непосредственно связанным с”;
б) R 12 – “быть начальником”.
1. На множестве N:
а) R 1={(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;
б) R 2={(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;
в) R 3={(a, b): a = b }:
· рефлексивно, не антирефлексивно, поскольку a = a для всех a Î N;
· симметрично, так как если a = b, то b = a;
· антисимметрично, так как если a R 3 b и b R 3 a, то а = b;
· транзитивно, так как если а = b и b = c, то а = с.
2. На множестве точек действительной плоскости ´
а) R 4={((x 1, y 1), (x 2, y 2)): (x 1)2+(y 1)2=(x 2)2+(y 2)2}:
· рефлексивно, не антирефлексивно, так как x 2+ y 2= x 2+ y 2 для любых точек (x, y) действительной плоскости ´
· симметрично, не антисимметрично, так как, например, для точек (2, 3) и (–2, 3) имеет место 22+32=(–2)2+32, но (2, 3)¹(–2, 3);
· транзитивно, поскольку если (x 1, y 1) и (x 2, y 2) находятся на одина-ковом расстоянии от начала координат, а также – (x 2, y 2) и (x 3, y 3), то и (x 1, y 1) и (x 3, y 3) находятся на одинаковом расстоянии от начала координат;
б) R 5={((x 1, y 1), (x 2, y 2)): x 1= x 2, y 1= – y 2}:
· не рефлексивно, так как для точек плоскости (x, y), не находящихся на оси X, т.е. для точек с координатами y ¹0, не выполняется (x, y) R 5 (x, y);
· не антирефлексивно, так как точка плоскости симметрична самой себе, если она лежит на оси X, т.е. для точек (x, y) с координатами y =0 имеет место (x, y) R 5 (x, y);
· симметрично, например (2, 3) R 5 (2, –3) и (2, –3) R 5 (2, –3);
· не антисимметрично, поскольку имеет место, например, (2, 3) R 5 (2, –3) и (2, –3) R5 (2, 3), но (2, –3)¹(2, 3);
· не транзитивно, так как, например, (2, 3) R 5 (2, –3) и (2, –3) R 5 (2, 3), но не выполняется (2, 3) R 5 (2, 3).
3. На системе множеств b(M):
а) R 6={(A, B): A Ç B ¹Æ, A, B Îb(M)}:
· не рефлексивно, поскольку для ÆÎb(M) имеет место ÆÇÆ=Æ;
· не антирефлексивно, так как для A Îb(M), если A не пусто, т.е. A ¹Æ, то A Ç A =Æ, т.е. отношение выполняется;
· симметрично, так как если A пересекается с B, то и B – с A;
· не антисимметрично, поскольку A R 6 B и B R 6 A для A ¹ B;
· не транзитивно, например { a } R 6 { a, b } и { a, b } R 6 { b }, но { a } R 6 { b } не выполняется;
б) R 7={(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. На множестве людей:
а) R 8={(a, b): a – сын b }:
· не рефлексивно, антирефлексивно, так как ни для каких a не выполняется: а – сын а;
· не симметрично, антисимметрично, поскольку ни для каких a ¹ b не выполняется: а – сын b и b – сын а;
· не транзитивно, так как если: а – сын b и b – сын с, то а – не сын с;
б) R 9={(a, b): a живет в одном городе с b }:
· рефлексивно, не антирефлексивно, так как a R 9 a для всех а;
· симметрично, поскольку для любых а, b, если a R 9 b, то b R 9 a;
· не антисимметрично, так как имеет место a R 9 b и b R 9 a для а ¹ b;
· транзитивно, поскольку для всех a, b, c, если a R 9 b и b R 9 с, то а R 9 с;
в) R 10={(a, b): a – брат b }:
· не рефлексивно, антирефлексивно из-за очевидного отсутствия a R 10 a для всех а;
· не симметрично, так как в общем случае между братом а и сестрой b имеет место a R 10 b, но не b R 10 a;
· не антисимметрично, так как если а и b – братья, то a R 10 b и b R 10 a, но a ¹ b;
· транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).
5. На множестве элементов структуры (см. рис. 2.2):
а) R 11={(a, b): a – непосредственно связан с b }:
· не рефлексивно, антирефлексивно, если в конкретной интер-претации a R 11 a не имеет смысла;
· симметрично, не антисимметрично, поскольку для всех a ¹ b, если выполняется a R 11 b, то b R 11 a;
· не транзитивно, так как при a R 11 b и b R 11 с не выполняется а R 11 с (а и с связаны, но опосредованно);
б) R 12={(a, b): a – начальник b }:
· не рефлексивно, антирефлексивно (см. R 11};
· не симметрично, антисимметрично, так как для всех a ¹ b не выполняется одновременно a R 12 b, то b R 12 a;
· транзитивно, так как если а – начальник b и b – начальник с, то а – начальник с.
Вопросы для самопроверки и упражнения:
1. Составить матрицы отношений, заданных в примере 3, определив произвольно множество M, R Í M ´ M таким образом, чтобы по матрице можно было бы судить о свойствах отношения, и назвать эти свойства.
2. Какими свойствами характеризуются следующие отношения на M ={1, 2, 3, …, 9}:
а) R 1={(a, b): (a – b) – четное};
б) R 2={(a, b): (a + b) – четное};
в) R 3={(a, b): (a +1) – делитель (a + b)};
г) R 4={(a, b): a – делитель (a + b), а ¹1}.
Дата публикования: 2015-03-29; Прочитано: 2715 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!