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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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