Спирина, М.С. Дискретная математика

Рис. 1.16. Графики прямых и обратных бинарных отношений: а — у = six и у = х?; б — у = s inx и у = arcsinx Свойства бинарных отношений. Приведем характерные свойства бинарных отношений, причем заметим, что каждое конкретное отношение может обладать или не обладать некоторыми из ука­ занных свойств. 1. Рефлективность: aRa. Например, «быть не больше» на К. 2. Антирефлективность. Имеет место, когда отношение не об­ ладает свойством 1 для любых а, например «быть больше», «быть младше» и др. 3. Симметричность любых двух элементов. Отношение R на мно­ жестве М называется симметричным, если для любых a, b е М од­ новременно справедливо aRb и bRa (т. е. R = R~l). Симметрична параллельность прямых, так как если а || Ь, то b || а. Симметрично отношение «быть равным» на любом множестве или «быть взаим­ но-простым» на N. 4. Антисимметричность. Если для несовпадающих элементов оф Ь верно отношение aRb , то ложно bRa. Антисимметричными явля­ ются отношения «быть больше», «не меньше» на R, «быть делите­ лем» на N и др. 5. Транзитивность. Если aRb и bRc, то aRc для любых a, b, с е М. Транзитивны отношения «быть больше», «быть параллельным», «быть равным» и др. 6. Антитранзитивность. Имеет место, когда отношение не об­ ладает свойством 5. Например, «быть перпендикулярным» на мно­ жестве прямых плоскости ( a J. b, b ± с, но неверно a l e ) . 7. Асимметричность. Ни для одной пары а и b не выполняется одновременно aRb и bRa. 8. Связность. Для любых а и Ь, если а * Ь, то aRb или bRa. Некоторые свойства конкретных бинарных отношений приве­ дены в табл. 1.6. Рассмотрим основные виды бинарных отношений. Отношение эквивалентности. Бинарное отношение R называется отношением эквивалентности, если оно одновременно обладает 40