Отношение антирефлексивно тогда и только тогда, когда ни одна из вершин графа не имеет петлей

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

Свойства бинарных отношений

Свойства матриц бинарных отношений

Доказательство.

2.

1.

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

С помощью матриц.

Решение.

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

Пример 2. Построить граф отношения:.

Рассмотрим два конечных множества и и бинарное отношение. Введем матрицу бинарного отношения Р следующим образом:

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

Частные случаи:

· Матрица тождественного отношения представляет собой единичную матрицу:

· Матрица полного квадрата представляет собой матрицу, все элементы которой равны 1:

Для бинарных отношений обычным образом вводятся теоретико-множественные операции объединения и пересечения.

Def :Обратным к P отношением P^-1 называется множество.

Def: Композицией (суперпозицией) бинарных отношений и называется множество

Пример 3. Если,, то

Теорема 1. Для любого бинарного отношения выполняются следующие свойства:

3. (свойство ассоциативности композиции)

Матрица любого бинарного отношения обладает следующими свойствами:

1. Если и,, то;, причем сложение элементов определяется по правилам: 0+0=0; 1+0=0+1=1; 1+1=1, а умножение – почленно обычным образом, то есть по правилам: 1*0=0*1=0; 1*1=1; 0*0=0.

2. Если,, то и матрицы умножаются по обычному правилу умножения матриц, но произведение и сумма элементов при перемножении матриц находится по правилам п.1.

3., где - матрица обратного отношения.

4. Если, то, где,.

Пример 4. Пусть,.

Пусть и.

Def: Отношение P называется рефлексивным на А, если, то есть.

Замечание 1. Вместо записи часто используют более простую:.

Пример 5. Отношение делимости на множестве целых чисел, отношение включения на булеане непустого множества.

Отношение P рефлексивно тогда и только тогда, когда все вершины графа имеют петли.

Def: Отношение P называется симметричным на А, если.

Пример 6. Отношение равенства на любом числовом множестве, отношение параллельности на множестве всех прямых плоскости.

Def: Отношение P называется антирефлексивным на А, если.

Пример 7. Отношение неравенства на любом числовом множестве, отношение перпендикулярности на множестве всех прямых плоскости.

Def: Отношение P называется антисимметричным на А, если

.

Пример 8. Отношение неравенства на любом числовом множестве, отношение включения на булеане непустого множества.