Математика и информатика. Филимонова Л.В - 20 стр.

                                   20

том же месяце, что и Петя, то же самое можно сказать и о Пете: Петя
родился в том же месяце, что и Таня. С учетом введенных обозначе-
ний можно записать: если ТаняρПетя, то ПетяρТаня. Иначе дело об-
стоит с другим отношением δ: если Таня ростом выше Пети, то невер-
но, что и Петя ростом выше Тани.
       Таким образом, различные отношения могут иметь и различные
свойства. Рассмотрим основные из них.
    Опр.3.4 Бинарное отношение (БО) ρ, заданное на множестве А, на-
зывается рефлексивным, если любой элемент этого множества нахо-
дится в данном отношении с самим собой, т.е. ∀а∈А: аρа.
    Опр.3.5 БО ρ называется симметричным, если из того, что пара
(a,b) находится в отношении ρ, следует, что и симметричная ей пара
(b,a) тоже находится в этом отношении, т.е ∀a,b∈A: aρb ⇒bρa.
    Опр.3.6 БО называется антисимметричным ,если
    ∀a,b∈A: aρb ∧ bρa ⇒ a=b.
    Опр.3.7 БО называется транзитивным, если ∀a,b,c∈A:
    aρb ∧ bρc ⇒ aρc.
       Примерами рефлексивного и транзитивного отношения является
отношение равенства, не симметричного – отношения «больше» или
«меньше» на множестве действительных чисел.
             БИНАРНЫЕ ОТНОШЕНИЯ (ОПРЕДЕЛЕНИЯ)
              БО ρ, заданное на              Если выполняется
           Множестве А, является:           Следующее условие:
         Рефлексивным                 ∀a∈A aρa
         Симметричным                 ∀a,b∈A aρb ⇒ bρa
         Антисимметричным             ∀a,b∈A aρb ∧ bρa ⇒ a=b
         Транзитивным                 ∀a,b,c∈A aρb ∧ bρc ⇒ aρc
    Опр.3.8 Бинарное отношение, обладающее свойствами рефлексив-
ности, симметричности и транзитивности, называется отношением
эквивалентности (или просто эквивалентностью).
       Бинарное отношение ρ можно задать перечислением всех пар из
А×А, принадлежащих отношению, указанием характеристического
свойства, которым обладают все элементы отношения, а также с по-
мощью так называемого ориентированного графа. Для этого элемен-
ты множества А изображают в виде точек и вводят соглашение: если
xρy, то от точки x проводят стрелку к точке y. Если xρх, то начало и
конец стрелки совпадают, такую стрелку называют петлей. Выполнив
указанные построения, получим фигуру – ориентированный граф.
Точки, соединенные стрелками, называются вершинами графа, а сами
стрелки – ребрами графа.
       Пример 3.3. Пусть на множестве М={2,3,4,5,6} задано отноше-
ние ρ - кратности элементов, т.е. xρy, если x M y (x делится на y без ос-
татка). Построить ориентированный граф данного бинарного отноше-