Свойства бинарных отношений

Пусть 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 ₁ – “быть не больше £”;

б) R ₂ – “быть делителем”;

в) R ₃ – “быть равным”.

2. На множестве точек действительной плоскости ´

а) R ₄ – “находиться на одинаковом расстоянии от начала координат”;

б) R ₅ – “быть симметричным относительно оси X ”.

3. На системе множеств b(M):

а) R ₆ – “пересекаться с” (иметь непустое пересечение);

б) R ₇ – “являться строгим включением Ì”.

4. На множестве людей:

а) R ₈ – “быть сыном”;

б) R ₉ – “жить в одном городе”;

в) R ₁₀ – “быть братом”.

5. На множестве элементов структуры (рис. 2.2):

а) R ₁₁ – “быть непосредственно связанным с”;

б) R ₁₂ – “быть начальником”.

1. На множестве N:

а) R ₁={(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 ₂={(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 ₃={(a, b): a = b }:

· рефлексивно, не антирефлексивно, поскольку a = a для всех a Î N;

· симметрично, так как если a = b, то b = a;

· антисимметрично, так как если a R ₃ b и b R ₃ a, то а = b;

· транзитивно, так как если а = b и b = c, то а = с.

2. На множестве точек действительной плоскости ´

а) R ₄={((x ₁, y ₁), (x ₂, y ₂)): (x ₁)²+(y ₁)²=(x ₂)²+(y ₂)²}:

· рефлексивно, не антирефлексивно, так как x ²+ y ²= x ²+ y ² для любых точек (x, y) действительной плоскости ´

· симметрично, не антисимметрично, так как, например, для точек (2, 3) и (–2, 3) имеет место 2²+3²=(–2)²+3², но (2, 3)¹(–2, 3);

· транзитивно, поскольку если (x ₁, y ₁) и (x ₂, y ₂) находятся на одина-ковом расстоянии от начала координат, а также – (x ₂, y ₂) и (x ₃, y ₃), то и (x ₁, y ₁) и (x ₃, y ₃) находятся на одинаковом расстоянии от начала координат;

б) R ₅={((x ₁, y ₁), (x ₂, y ₂)): x ₁= x ₂, y ₁= – y ₂}:

· не рефлексивно, так как для точек плоскости (x, y), не находящихся на оси X, т.е. для точек с координатами y ¹0, не выполняется (x, y) R ₅ (x, y);

· не антирефлексивно, так как точка плоскости симметрична самой себе, если она лежит на оси X, т.е. для точек (x, y) с координатами y =0 имеет место (x, y) R ₅ (x, y);

· симметрично, например (2, 3) R ₅ (2, –3) и (2, –3) R ₅ (2, –3);

· не антисимметрично, поскольку имеет место, например, (2, 3) R ₅ (2, –3) и (2, –3) R₅ (2, 3), но (2, –3)¹(2, 3);

· не транзитивно, так как, например, (2, 3) R ₅ (2, –3) и (2, –3) R ₅ (2, 3), но не выполняется (2, 3) R ₅ (2, 3).

3. На системе множеств b(M):

а) R ₆={(A, B): A Ç B ¹Æ, A, B Îb(M)}:

· не рефлексивно, поскольку для ÆÎb(M) имеет место ÆÇÆ=Æ;

· не антирефлексивно, так как для A Îb(M), если A не пусто, т.е. A ¹Æ, то A Ç A =Æ, т.е. отношение выполняется;

· симметрично, так как если A пересекается с B, то и B – с A;

· не антисимметрично, поскольку A R ₆ B и B R ₆ A для A ¹ B;

· не транзитивно, например { a } R ₆ { a, b } и { a, b } R ₆ { b }, но { a } R ₆ { b } не выполняется;

б) R ₇={(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 ₈={(a, b): a – сын b }:

· не рефлексивно, антирефлексивно, так как ни для каких a не выполняется: а – сын а;

· не симметрично, антисимметрично, поскольку ни для каких a ¹ b не выполняется: а – сын b и b – сын а;

· не транзитивно, так как если: а – сын b и b – сын с, то а – не сын с;

б) R ₉={(a, b): a живет в одном городе с b }:

· рефлексивно, не антирефлексивно, так как a R ₉ a для всех а;

· симметрично, поскольку для любых а, b, если a R ₉ b, то b R ₉ a;

· не антисимметрично, так как имеет место a R ₉ b и b R ₉ a для а ¹ b;

· транзитивно, поскольку для всех a, b, c, если a R ₉ b и b R ₉ с, то а R ₉ с;

в) R ₁₀={(a, b): a – брат b }:

· не рефлексивно, антирефлексивно из-за очевидного отсутствия a R ₁₀ a для всех а;

· не симметрично, так как в общем случае между братом а и сестрой b имеет место a R ₁₀ b, но не b R ₁₀ a;

· не антисимметрично, так как если а и b – братья, то a R ₁₀ b и b R ₁₀ a, но a ¹ b;

· транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

5. На множестве элементов структуры (см. рис. 2.2):

а) R ₁₁={(a, b): a – непосредственно связан с b }:

· не рефлексивно, антирефлексивно, если в конкретной интер-претации a R ₁₁ a не имеет смысла;

· симметрично, не антисимметрично, поскольку для всех a ¹ b, если выполняется a R ₁₁ b, то b R ₁₁ a;

· не транзитивно, так как при a R ₁₁ b и b R ₁₁ с не выполняется а R ₁₁ с (а и с связаны, но опосредованно);

б) R ₁₂={(a, b): a – начальник b }:

· не рефлексивно, антирефлексивно (см. R ₁₁};

· не симметрично, антисимметрично, так как для всех a ¹ b не выполняется одновременно a R ₁₂ b, то b R ₁₂ a;

· транзитивно, так как если а – начальник b и b – начальник с, то а – начальник с.

Вопросы для самопроверки и упражнения:

1. Составить матрицы отношений, заданных в примере 3, определив произвольно множество M, R Í M ´ M таким образом, чтобы по матрице можно было бы судить о свойствах отношения, и назвать эти свойства.

2. Какими свойствами характеризуются следующие отношения на M ={1, 2, 3, …, 9}:

а) R ₁={(a, b): (a – b) – четное};

б) R ₂={(a, b): (a + b) – четное};

в) R ₃={(a, b): (a +1) – делитель (a + b)};

г) R ₄={(a, b): a – делитель (a + b), а ¹1}.