13. Бинарные отношения.

бинарным отношением называется подмножество декартова произведения двух множеств. В частности, бинарным отношением на множестве называется множество упорядоченных пар элементов этого множества.

Характеристическое свойство некоторого подмножества Р декартова произведения ExF (т.е. РExF) называется бинарным отношением f между элементами множеств Е и F и обозначается afb, где а єЕ, b єF. Если же E = F, то f называется бинарным отношением во множестве Е.

Областью определения  (внизу f) бинарного отношения f между элементами a єE, b єF называется подмножество множества Е, каждый элемент a єE связан бинарным отношением f хотя бы с одним элементом b єF

Областью значений  (внизу f) бинарного отношения f между элементами a єE, b єF называется подмножество множества F, с каждым элементом b єF связан бинарным отношением f хотя бы один элемент a єE

 (внизу f) ={ a єE | b єF: afb }

 (внизу f)= {bєF| aєE:afb}

Бинарное отношение f между элементами множеств Е и F

Множества Е и F могут совпадать. Тогда мы можем элементы множества Е обозначить точками, то есть ввести бинарные отношения во множестве Е

бинарные отношения на чертеже обозначаются линиями со стрелками, эти линии называются графами.

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

Бинарные отношения могут обладать различными свойствами, такими как:

1). Рефлексивность – бин.отн.рефлекс.,если оно удовлетворяет условию рефлексивности,т.е.для а из множ-ва М справедливо утвержд. аfа.Пример:отнош-я ≤ и ≥ рефлексивны,т.к.имеют место условия:а≤а;а≥а) 2). Иррефлексивность (антирефлексивность) – бин.отн.антирефлексивно,если условие аfа ложно.Пример:отнош. < и > антирефл.,т.к. а>a и a<aложны.

3). Симметричность – бин.отн.симметрично,если справед. услов. симм-ти аfb bfa.Пример: f-отнош.равноправия.Если а имеет те же права,что и b,а b-те же,что и а,это озн.,что отн.f сим.

4). Антисимметричность-бин.отн.антисим.,если вып.усл.асим-ти:аfb & bfa=>a=b.Отн.≥и≤ антисим.,т.к.а ≤ b & b≤a=>a=b;a≥b & b≥a=>a=b.

5). Ассиметричность-бин.отн.ассим.,если вып.усл.ассим.: afb=>¬bfa.Пример:отн. < и > ассим.,т.к. a<b => ¬b>a; a<b => ¬b<a

6). Транзитивность-бин.отн.транз.,если оно удовл.усл.транзитивности: afb & bfc => afc.Пример: 1)f – отнош. «быть старше».Оно транзитивно,т.к. если а старше b, а b старше с, то а старше с. 2)f – отнош. «быть знакомым»,оно нетранз: (а знаком с b) & (b знаком с с) => (а знаком с с).

15.Отношения эквивалентности и порядка.

Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Если в некотором множестве задано отношение эквивалентности, то элементы этого множества разбиваются на классы эквивалентности. Произв-й элемент а, отн. к этому классу называется представителем класса эквивалентности. [a]f Множество всех классов эквивалентности называется фактором множества. (M|f)

Бинарные отношения f во множестве E называется отношением некоторого порядка или отношением строгого порядка если , если оно рассмотрено, или иррефлексивно (соотв. 1му и 2му), антисимметрично (нестр.), или ассиметрично (по отношению к стр.), транзитивно (и к стр. и к не стр.)

Отношения ≥, ≤ дают нестрогий порядок. Отношения >, < дают строгий порядок во множестве вещественных чисел.

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