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

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

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

Так как отношения из А в В задаются подмножествами, следовательно для них определены те же теоретико-множественные операции, что и над множествами:

1) Объединение.

2) Пересечение.

3) Разность.

4) Дополнение.

Заметим, что операции объединения, пересечения и дополнения бинарных отношений удовлетворяют законам идемпотентности, коммутативности, ассоциативности, поглощение, инволюции и законам де Моргана.

Над отношениями могут также осуществляться другими алгебраические операции:

5) Обратное отношение.

6) Произведение (композиция) отношений

.

7) Степень отношения.

Заметим, что:

1), где сложение элементов матриц осуществляется по правилам 0+0=0, 1+1=1+0=0+1=1.

2), где умножение матриц осуществляется поэлементно с обычными правилами умножения чисел.

3), где умножение матриц производится по обычному правилу умножения матриц.

4), где символ T означает транспонирование матрицы.

Пусть задано отношение на множестве А, т.е., тогда отношение R называется:

рефлексивным,	если
антирефлексивным,	если
симметричным,	если
антисимметричным,	если
транзитивным,	если
полным или линейным,	если

Для указанных отношений справедливы следующие утверждения:

R рефлексивно	Û
R антирефлексивно	Û
R симметрично	Û
R антисимметрично	Û
R транзитивно	Û
R полно	Û

Заметим, что:

в матрице рефлексивного отношения все диагональные элементы равны единице, а антирефлексивного – нулю. Для симметричного отношения справедливо. В случае антисимметричного отношения матрица имеет все элементы вне главной диагонали равные нулю. Для транзитивного отношения верно утверждение.

Отношение R называется отношением эквивалентности, если R рефлексивно, симметрично и транзитивно. Это отношение обозначается символами E и ~(тильда): aEb или a ~ b. Важное значение отношения эквивалентности состоит в том, что оно определяет признак, по которому происходит разбиение исходного множества на непересекающиеся подмножества, называемые классами эквивалентности. Пусть E – эквивалентность на множестве А. Классом эквивалентности элемента называется множество. Классы эквивалентности Е называются также Е – классами. Множество называется фактор-множеством множества А по отношению к Е. Множество является разбиением множества А. Обратно, если - некоторое разбиение множества А, то можно задать соответствующее ему отношение эквивалентности Е по следующему правилу: для некоторого i.

Отношение эквивалентности характеризует одинаковость объектов. Однако существуют ситуации, в которых требуется оценить сходство объектов. Этой цели служит отношение толерантности. Отношение, удовлетворяющее свойствам рефлексивности и симметричности, называется отношением толерантности.

В ряде случаев требуется указать старшинство, важность, “первичность” и другие подобные свойства объектов. Для этого служат различные виды отношения порядка.

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

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

Отношение строгого порядка (полного или частичного) обозначается символом <, а отношение нестрогого порядка -. Отношение порядка в общем случае обозначается знаком.

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

Дата добавления: 2014-01-11