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

Пусть Е – бинарное отношение в множестве А. Определим общие свойства таких отношений, которые должны выполняться для всех. Говорят, что:

1. Рефлексивно, если (R – тождественное отношение, т.е. оно всегда выполняется между объектом и им самим ().

Содержательными примерами рефлексивных отношений могут служить отношения «быть похожим на», «иметь общий признак с».

Рефлексивные отношения всегда представляются матрицей, у которой на главной диагонали стоят единицы. В графе, изображающем рефлексивное отношение, каждая вершина имеет петлю.

2. Антирефлексивно, если, т.е. может выполняться только для несовпадающих объектов: из следует (строгое неравенство, отношение строгого порядка).

Матрица, представляющая антирефлексивное отношение, имеет на главной диагонали нули, а в соответствующем графе петли непременно отсутствуют.

Пример антирефлексивного отношения приведен на рис. 3 д).

3. Симметрично, если, т.е. при выполнении соотношения выполняется и соотношение.

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

Пример симметричного отношения приведен на рис. 3 б).

4. Асимметрично, если, т.е. из двух соотношений и по меньшей мере одно не выполняется. Если отношение асимметрично, то оно и антирефлексивно.

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

Например, отношение строгого включения «», «быть преподавателем в конкретной учебной группе» и др.

5. Антисимметрично, если, т.е. оба соотношения и выполняются одновременно только тогда, когда.

Для матричных элементов это приводит к утверждению:, если.

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

Примерами таких отношений могут служить нестрогие неравенств,, нестрогие включения,.

6. Транзитивно, если, т.е. из и то следует.

В матрице транзитивного отношения для каждой пары единичных элементов, один из которых расположен в i-м столбце и j-й строке, а другой в j-м столбце и k-й строке, обязательно существует единичный элемент, расположенный в клетке на пересечении i-го столбца и k-й строки (наличие единичных элементов на главной диагонали не нарушает транзитивности).

Граф транзитивного отношения покажем на примере.

При исследовании учебного плана и построении структурно-логической схемы выделена цепочка учебных дисциплин: философия, математика, физика, теория информации и надежность и эксплуатация АСУ. Обозначим это множество соответственно. Зададим между элементами этого множества отношение «обеспечивать знаниями». Тогда граф транзитивного отношения имеет следующий вид (см. рис. 5).

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