Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


—войства отношений




ќчевидно, что произвольные бинарные отношени€ изучать в общем плане не особенно интересно, о них можно сказать очень мало. ќднако, если отношени€ удовлетвор€ют некоторым дополнительным услови€м, относительно них можно делать более содержательные утверждени€. ¬ этом разделе мы рассмотрим некоторые из основных свойств бинарных отношений.

ќпределение 3.1. Ѕинарное отношение a на множестве X называетс€ рефлексивным, если дл€ любого элемента a X выполн€етс€ условие a a a:

( a X) a a a.

≈сли отношение представлено с помощью графа, то рефлексивность этого отношени€ означает, что в каждой вершине графа об€зательно имеетс€ петл€.

ƒл€ отношени€, заданного с помощью булевой матрицы его рефлексивность равносильна тому, что по главной диагонали этой матрицы (идущей из ее левого верхнего угла в правый нижний) сто€т только символы 1.

ќпределение 3.2. Ѕинарное отношение a на X называетс€ антирефлексивным, если ни дл€ одного a X не выполн€етс€ условие a a a:

( a X) .

ќбозначим через Ix отношение на множестве X, состо€щее из пар вида (a, a), где a X:

Ix = {(a, a)| a X }.

ќтношение Ix обычно называют диагональю множества X или отношением тождества на X.

ќчевидно, что отношение a на множестве X рефлексивно, если диагональ Ix €вл€етс€ подмножеством множества a:

Ix a.

ќтношение антирефлексивно, если диагональ Ix и отношение a не имеют ни одного общего элемента:

Ix a = O.

ќпределение 3.3. Ѕинарное отношение a на множестве X называетс€ симметричным, если из a a b следует b a a:

( a, b X)(a a b b a a).

ѕримерами симметричных отношений €вл€ютс€:

Ј отношение перпендикул€рности на множестве пр€мых;

Ј отношение касани€ на множестве окружностей;

Ј отношение "быть похожим" на множестве людей;

Ј отношение "иметь одинаковый пол" на множестве животных.

ќтношение " x брат y " на множестве всех людей не €вл€етс€ симметричным. ¬ то же врем€ отношение " x брат y " на множестве мужчин симметричным €вл€етс€.

¬ графе симметричного отношени€ дл€ каждой дуги из вершины x в вершину y имеетс€ дуга из y в x. ѕоэтому симметричные отношени€ можно представл€ть графами с неориентированными ребрами. ѕри этом кажда€ пара ориентированных ребер xy и yx замен€етс€ одним неориентированным ребром.

Ќа рисунке 8 представлено отношение

a= {(a, b), (b, a), (b, c), (c, b), (d, c)}

с помощью ориентированного и неориентированного графов.

–ис. 8. ѕредставление симметричного отношени€ с помощью
ориентированного (a) и неориентированного (b) графов

ћатрица симметричного отношени€ симметрична относительно главной диагонали.

“еорема 3.1. ќбъединение и пересечение любого семейства симметричных отношений снова €вл€ютс€ симметричными отношени€ми.

ќпределение 3.4. Ѕинарное отношение a на множестве X называетс€ антисимметричным, если дл€ любых различных элементов a и b услови€ a a b и b a a не выполн€ютс€ одновременно:

( a, b X) (a a b & b a a a = b).

Ќапример, отношение "делитс€" на множестве натуральных чисел €вл€етс€ антисимметричным, так как из a b и b a следует, что a = b. ќднако на множестве целых чисел отношение "делитс€" антисимметричным не €вл€етс€, так как (-2) 2 и 2 (- 2), но

-2 2.

ќтношени€ "выше", "т€желее", "старше" антисимметричны на множестве людей. ќтношение "быть сестрой" на множестве всех людей антисимметричным не €вл€етс€.

¬ графе антисимметричного отношени€ две различные вершины могут быть соединены не более чем одной дугой.

ќпределение 3.5. Ѕинарное отношение a на множестве X называетс€ транзитивным, если дл€ любых трех элементов a, b, c X из a a b и b a c следует a a c:

( a, b, c X) (a a b & b a c a a c).

ѕримерами транзитивных отношений служат:

Ј отношение "делитс€" на множестве действительных чисел;

Ј отношение "больше" на множестве действительных чисел;

Ј отношение "старше" на множестве людей игрушек;

Ј отношение "иметь одинаковый цвет" на множестве детских игрушек;

д) отношение "быть потомком" на множестве людей.

‘еодальное отношение "быть вассалом" не €вл€етс€ транзитивным. Ёто в частности подчеркиваетс€ в некоторых учебниках истории: "вассал моего вассала не мой вассал".

ќтношение "быть похожим" на множестве людей не обладает свойством транзитивности.

ƒл€ произвольного отношени€ a можно найти минимальное транзитивное отношение b

такое, что a b. ћинимальность отношени€ понимаетс€ в том смысле, что дл€ любого транзитивного отношени€ g из a g следует b g. “аким отношением €вл€етс€ транзитивное замыкание отношени€ a.

ѕример 3.1. “ранзитивным замыканием бинарного отношени€ на множестве людей "быть ребенком" €вл€етс€ отношение "быть потомком".

—праведлива теорема.

“еорема 3.2. ƒл€ любого отношени€ транзитивное замыкание равно пересечению всех транзитивных отношений, включающих в качестве подмножества.

ќпределение 3.6. Ѕинарное отношение a на множестве X называетс€ св€зным, если дл€ любых двух различных элементов a и b имеет место a a b, либо b a a:

( a, b, c X)(a b a a b b a a).

ѕримером св€зного отношени€ €вл€етс€ отношение "больше" на множестве действительных чисел. ќтношение "делитс€" на множестве целых чисел св€зным не €вл€етс€.

»нвариантность отношений

¬ этом параграфе мы перечислим некоторые случаи, когда те или иные свойства отношений сохран€ютс€ при выполнении над ними операций [1].

“еорема 4.1. ≈сли отношени€ a и b рефлексивны, то рефлексивны и следующие отношени€:

a b,b a, a-1, a∞b, .

“еорема 4.2. ≈сли отношени€ a и b антирефлексивны, то антирефлексивны и следующие отношени€:

a b, b a, a-1.

“еорема 4.3. ≈сли отношени€ a и b симметричны, то симметричны и следующие отношени€:

a b, b a, a-1.

“еорема 4.4. „тобы произведение a∞b симметричных отношений a и b было симметрично, необходимо и достаточно, чтобы отношени€ и коммутировали:

a∞b =a∞b.

“еорема 4.5. ≈сли отношени€ a и b антисимметричны, то антисимметричны и следующие отношени€:

a b, a-1

“еорема 4.6. ≈сли отношени€ a и b транзитивны, то транзитивны и следующие отношени€:

a b, a-1, .

ƒругие интересные свойства отношений описаны в [1, 2].





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-05-06; ћы поможем в написании ваших работ!; просмотров: 643 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

„то разум человека может постигнуть и во что он может поверить, того он способен достичь © Ќаполеон ’илл
==> читать все изречени€...

692 - | 616 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.019 с.