Теоретические основы выбора альтернатив

2.1. Понятие бинарного отношения. Способы задания бинарных отношений

Бинарным отношением R на множестве X произвольной природыназывается подмножество R множества : . Если пара входит в R, то есть , то принято обозначать . Бинарные отношения задаются следующими способами:

1. Перечисление всех пар элементов (x,y), которые содержатся в R.

2. Задание отношения матрицей смежности.

Пусть X состоит из n элементов, R - бинарное отношение на X. Занумеруем элементы X целыми числами от 1 до n.

 Матрицей смежности бинарного отношения называется квадратная матрица , элементы которой формируются по следующему правилу:

          

3. Задание графом.

 Под графом бинарного отношения понимается схема, в которой элементы множества X изображаются точками на плоскости, элементы  такие, что пара  соединяются стрелкой, направленной от x к y, пары  изображаются петлей вокруг точки x.

  4. Задание сечениями. Данный способ задания бинарного отношения, в отличие от способов 1-3, пригоден для задания отношений и на бесконечных множествах.

  Верхним сечением элемента  элемента  называется множество элементов таких, что : .

Аналогично определяется нижнее сечение: .

 Отношение R полностью задано, если для каждого задано либо множество , либо множество .   

Отношение R называется пустым (Æ), если оно не выполняется ни для одной пары .

 Для Æ справедливо: 1) ,  ; 2) граф G(Æ) не имеет дуг; 3)  для любого .

 Отношение R называется полным (U), если оно выполняется для всех пар . 

 Для U справедливо: 1) , ; 2) в графе G(U) дуги соединяют любую пару вершин; 3)  для любого .

Отношение R называется диагональным (E), если оно выполняется для тех и только для тех пар, которые состоят из совпадающих элементов: .

Для E справедливо: 1)  2) в графе G(E) присутствуют только петли при вершинах, других дуг нет; 3) , .

Отношение R называется антидиагональным (), если оно выполняется для тех и только для тех пар, которые состоят из несовпадающих элементов: .

 

Примеры

1.  – диагональное бинарное отношение.

2.  – пустое бинарное отношение.

  3.   – антидиагональное бинарное отношение.

Операции над отношениями

1. Вложение (включение).

Отношение   вложено (включено) в отношение , если множество пар, для которых выполнено , содержится в множестве пар, для которых выполнено .

, если , .

2. Дополнение.

Отношение  называется дополнением отношения R, если оно выполняется для тех и только для тех пар, для которых не выполняется отношение R, т.е. .

Справедливо: =1- ; в графе G() присутствуют те и только те дуги, которые отсутствуют в графе G(R).

3. Пересечение.

Пересечением отношений  и  называется отношение .

4. Объединение.

Объединением отношений  и  называется отношение .

5. Обращение.

Обратным к отношению R называется отношение , определяемое условиями: .

Справедливо: ; граф  получается из графа  изменением направления дуг, ,  (см. задачу № 6)

6. Переход к двойственному отношению.

Отношение называется двойственным к отношению R, если .

7. Произведение.

Произведением  и  называется отношение , определяемое следующим образом: , если существует , для которого и .

8. Сужение.

Отношение  называется сужением отношения  на множество , если и .

9. Изоморфизм.

Отношения  и  называются изоморфными, если существует взаимно-однозначное отображение  такое, что .

 

Примеры

1. Для отношений , справедливо: .

2. 1) Если , то .

2) Если , то .

3.  Если , , то .

4. Для  и  из примера 3: .

5. 1.Если , то .

2. Если , то .

6. 1.Если , то .

2. Если , то .

7. Пусть , , где Z – множество целых чисел. Пара , если существует  такое, что , . В качестве такого z можно выбрать . Таким образом, = .

8. Отношение  является сужением отношения  на множество целых чисел Z.

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

1. Отношение R называется рефлексивным, если . Другими словами, если для любого  выполнено: .

Для рефлексивного отношения R справедливо: ; в графе G(R) в каждой вершине имеется петля; , , .

2. Отношение R называется антирефлексивным, если Æ (или ). Другими словами, если , .

Для антирефлексивного отношения R справедливо: ; в графе G(R) петли отсутствуют; , , .

3. Отношение R называется симметричным, если , т.е. если , то , .

Для симметричного отношения R справедливо: ; в граф G(R) вместе с дугой  входит дуга ; .

4. Отношение R называется асимметричным, если Æ, т.е. если , то , .

Для асимметричного отношения R справедливо: ; в граф G(R) дуги  и  одновременно входить не могут; для любых  и сечение  не содержит x.

5. Отношение R называется антисимметричным, если , т.е. ,   только тогда, когда .

Для антисимметричного отношения R справедливо: , если ; в граф G(R) дуги  и  при  одновременно входить не могут; для любых  и  () сечение  не содержит x.

6. Отношение R называется транзитивным, если , т.е. если , , то .

В матрице  транзитивного отношения R длялюбых i, k: ; в графе  существует дуга (x, y), если существует путь от x к y; для любых  и  справедливо .

7. Отношение R называется отрицательно транзитивным, если  транзитивно.

8. Отношение R называется сильно транзитивным, если оно одновременно транзитивно и отрицательно транзитивно.

9. Отношение R называется ацикличным, если Æ, , то есть из , , …,  следует .

10. Отношение R называется связным (полным), если для любых элементов   выполнено  или .

 

Связи между свойствами бинарных отношений

1. Если отношение  рефлексивно (симметрично, антисимметрично, асимметрично, транзитивно), то  – рефлексивно (симметрично, антисимметрично, асимметрично, транзитивно).

2. Если отношение  рефлексивно, то  – антирефлексивно и если  антирефлексивно, то  – рефлексивно.

3. Отношение  асимметрично тогда и только тогда, когда  связно.

4. Если отношение  асимметрично, то оно антирефлексивно.

5. Оъединение и пересечение произвольного числа рефлексивных (антирефлексивных, симметричных) есть отношение рефлексивное (антирефлексивное, симметричное).

6. Отношение   отрицательно транзитивно тогда и только тогда, когда  транзитивно.

7. Если бинарное отношение антирефлексивно и транзитивно, то оно асимметрично.

8.  Если отношение   асимметрично и отрицательно транзитивно, то оно транзитивно.

Примеры

1. Отношения «быть не старше», «быть похожим»,  являются рефлексивными.

2. Антирефлексивными являются следующие отношения: «быть моложе», «быть родителем», .

3. Отношения: «быть родственником»,  симметричные.

4. Отношение  асимметрично.

5. Отношение  антисимметрично.

6. Отношения: , ,  являются транзитивными.

Отношение «выиграть футбольный матч» транзитивным не является.

7. Отношение , заданное графом:

1             2

3,

 

является ацикличным.

Отношение , заданное графом

2

1 3,

 

 ацикличным не является, так как , , .