Виды бинарных отношений.

Пусть - бинарное отношение.

Определение. Отношение - рефлексивно тогда и тогда, когда .

В теории предиката мы договорились под таким предложением по­нимать: - истина, слово «истина» опускаем, но всегда его подразу­меваем.

Определение. Отношение - антирефлексивно тогда и только то­гда, когда .

Определение. Отношение - симметрично тогда и только тогда, ко­гда .

Определение. Отношение - антисимметрично тогда и только то­гда, когда .

Определение. Отношение - транзитивно тогда и только тогда, ко­гда .

Пример. Определить вид отношения на

	рефлек.	антирефлек.	симметр.	антисимметр.	транзитив.
на	+	-	-	+	+
Отношение перпендикулярности на множестве прямых плоскости	-	+	+	-	-

1) - истинное высказывание, следова­тельно, отношение рефлексивно на .

2) - ложное высказывание, следовательно, отношение не антирефлексивно на .

3) - ложное высказывание, следовательно, от­ношение не симметрично на .

4) - истинное высказывание, следова­тельно, отношение антисимметрично на .

5) - истинное высказывание, следова­тельно, отношение транзитивно на .

Изображение бинарных отношений графами.

Определение. Граф – это фигура на плоскости, состоящая из конеч­ного числа точек – вершин графа и линий – рёбер графа, соединяющих не­которые из вершин. Ребро графа – это линия, соединяющая какие-либо две вершины графа.

Линии могут быть кривыми и прямыми. Точки пересечения некото­рых рёбер графа могут не являться вершинами графа.

Определение. Ориентированный граф – это граф, на котором ука­заны стрелками направления всех его рёбер.

Пример. Пусть - некоторое конечное не пустое множество, - би­нарное отношение на множестве , .

Э лементы множества представим точками на плоскости. Каждой паре при подставим в соответствии ориентированное ребро, идущее от точки к точке .

П аре поставим петлю с фиксированным направлением обхода, напри­мер, против часовой стрелки.

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

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

Пример. 1) Бинарное отношение задано как множество пар:

Изобразим бинарных отношений графом:

b

d

e

a

c

2) Бинарное отношение задано своим графом.

c

m

k