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

Отношение – характеристические связи между элементами множества, между множествами.

Отношения:

Ð унарные (отношения элементов имеет определенное свойство)

быть желтым (св-во) лимон (эл-т мн-ва) ящик (мн-во)

R a M

a Î R, R Í M

Ð бинарные (подмножество пар (а, в), декартово произведение множества)

(а, в) Í М₁ ´ М₂ (М₁ – область определения; М₂ – область значений)

aRb

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

1. Перечисление пар элементов обладающих свойствами:

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

2. Матрица:

1. Рефлексивность – бин. отношения, обладающие свойством "а Î М, aRa (н-р, парал. прямые)

Антирефлексивность – бин. отношения, обладающие свойством "а Î М, (н-р, отн. >,<)

2. Симметричность – бин. отношения, обладающие св-вом "а, в, если aRb Þ bRa (н-р // прямых)

Антисимметричность – бин. отношения, обладающие св-вом "а, в, если aRb и bRa Þ а = в (н-р, > < отношения)

3. Транзитивность – для "а, в, с, если aRb, bRc Þ aRc.

Рефлексивность по матрице – на главной диагонали только 1

Антирефлексивность – на главной диагонали только 0.

Симметричность – 1 и 0 симметричны относительно главной диагонали.

Отношением эквивалентности называется бинарное отношение, обладающие свойством рефлексивности, симметричности, транзитивности. (// прямых)

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

Отношением строго порядка называется бинарное отношение, обладающие свойством антирефлексивностью, антисимметричностью, транзитивностью.

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

Отношением строго и не строго порядка называется отношение порядка.

Множества, которые они применяют называются упорядочными.

Если для отношений порядка на множестве М и некоторых различных элементов а и в из множества М выполняется хотя бы одно отношение aRb и bRa, то элементы а и в называются сравнимыми по отношению к порядку.

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

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

Примеры: Отношение эквивалентно – разбиение на группы

Отношение строго порядка - >,<

Отношение не строго порядка - £, ³

Полностью упорядоченным – упорядочение по алфавиту

Частично упорядоченным – частичное упорядочение.